====== Summer Tranning Week 2 ====== 2020/07/17 2015 ACM-ICPC Asia Beijing Regional Contest ''pro 7/7/10 rank 9/???'' 2020.07.18 2020牛客暑期多校训练营（第三场） ''pro 8/9/12 rank 49/???'' 2020.07.20 2020牛客暑期多校训练营（第四场） ''pro 5/6/10 rank 18/???'' ===== Max.D. ===== ==== 专题 ==== 广义后缀自动机 ==== 比赛 ==== 百度之星初赛1 TopCoder SRM 788 Round1 Codeforces 658 Div1 Codeforces 659 Div1 ==== 题目 ==== 无 ===== Hardict ===== ==== 专题 ==== 正在学习$O(n^{\frac{2}{3}})$的$min25$ ==== 比赛 ==== 百度之星初赛1 ==== 题目 ==== [[https://vjudge.net/contest/355433#problem/B|线性递推]] [[http://acm.hdu.edu.cn/showproblem.php?pid=6088|组合+卷积]] ===== MountVoom ===== ==== 专题 ==== 无 ==== 比赛 ==== 这周训练比较密集,摸了 ==== 题目 ==== 无 ====== 个人总结 ====== ===== 陈铭煊 Max.D. ===== 这次周四的I是个教训。提醒自己小心谨慎，以后口胡算法先仔细理解理解样例，然后写完代码七分钟之内不许马上提交，一定要好好造数据。 ===== 龙鹏宇 Hardict ===== 稳定的罚时机器，每题先WA一发才能过 以后要多在本地造几组数据 需要在字符串方面多加练习 ===== 肖思炀 MountVoom ===== 我，构造题废物，下周争取多做点构造题。 最近训练题数还行，就是做得有点慢以及罚时爆炸，需要注意罚时。 多练点题，提高想题速度。 ====== 本周推荐 ====== ===== 陈铭煊 Max.D. ===== === 来源： === CF 666E，[[https://codeforces.com/contest/666/problem/E|题目链接]] 这周的比赛中出现了一道广义后缀自动机的题，居然还是没反应过来，因此再找一道有挑战性的EX_SAM的题目来练练手。 === 标签： === 广义后缀自动机，线段树合并 === 题意： === - 给定一个字符串$S$，和$m$个字符串$T_1,T_2,...,T_m$， - 有$q$个询问，每个询问给出四个参数$l,r,p_l,p_r$， - 求$S$的子串$[p_l,p_r]$在$T_l,T_{l+1},...,T_r$中的哪个串出现的次数最多， - 如果出现次数最多的有多个串，取编号最小的， - 对于每组询问，输出编号和出现次数， - $1\le |S|\le 5\times10^5,1\le m\le 5\times 10^4,1\le \sum^m_{i=1}|T_i|\le 5\times 10^4,1\le q\le 5\times 10^5$，时限$6s$。 === 题解： === 假设已经有了一个$S$和$T_1,...,T_m$建立的广义后缀自动机。首先我们想找到$[p_l,p_r]$这个子串的对应节点，可以看做是$[1,p_r]$子串对应的节点，顺着自动机的树边（$lnk$指针组成的终止树）往根走找到，为了加速我们可以在这棵树上做个倍增。 假设我们找到的这个节点记载有记录出现的$T_i$的下标与次数的数据结构。我们所要做的，就是在这个数据结构里查找一个区间最值。 显然线段树是最合适不过了。在插入时我们只给新的$cur$指针上的线段树插入对应的$T_i$下标，最后我们从叶子往根走来做线段树合并，就可以得到每一个节点的记录线段树了。虽然不可能完整的开出线段树空间，但是考虑到我们插入和合并的次数不是那么多，用动态开点的方式就可以了。 这里要注意一个重要细节：对于字符串$S$，我们只需要在自动机上爬点，为什么也需要将$S$插入自动机呢？事实上，不插入不行。假设我们跟着$S$在自动机上走，$[1,p_r]$走到了一个点$x$，那么$x$对应了一个字符串长度范围$[mlen[lnk[x]]+1,mlen[x]]$，然而这个很可能$[1,p_r]$的$[p_l',p_r]$这一段才真正有匹配，且$p_r-p_l' p_r-p_l'\ge mlen[lnk[x]]+1$，这样我们找到的点也还是$x$，即使在$x$是没有对应匹配的字符串的。解决的方法就是插入$S$，使得总能找到完全匹配的等长节点。 本题其实没有卡暴力找父亲，不倍增好像还快一丢丢。当然一般不要有这种侥幸心理。 AC代码：[[https://codeforces.com/contest/666/submission/87769563|982ms]]，为了封装性写得有点略长。 === 评论： === 还算可以的题，其实思维难度一般，主要还是写起来比较锻炼。列表里面好多人很久之前都写过这道陈年老题，有点惭愧。务必要多学习算法知识。 ===== 龙鹏宇 Hardict ===== **来源:** 百度之星初赛[[http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=889&pid=1008|外部链接]] **标签:** 数论,积性函数 **题意:** $f(p^{a})=p^{a}+1,f(mn)=f(m)f(n),(m,n)=1\\\\ 求\sum_{i=1}^{N}f(i),N\leq 10^{12}$ **题解:** 一开始化解出$f()$表达式后发现形式和$min25$筛差不多 然后学习了下最新的$O(n^{\frac{2}{3}})$的$min25$筛，不过内存炸了 之后看题解才学习到了，整体思路是参考杜教筛的推导过程 取积性函数$g,h,s.t: f = g * h$ $h(1)=g(1)=1,f(p^{a})=\sum_{i=0}^{a}g(p^{i})h(p^{a-i})$ $F(n)=\sum_{i=1}^{n}f(i)=\sum_{i=1}^{n}\sum_{j|i}h(j)g(\frac{i}{j})\\\\ =\sum_{j=1}^{n}\sum_{k=1}^{\frac{n}{j}}h(j)g(k) =\sum_{j=1}^{n}h(j)G(\frac{n}{j}),G(n)=\sum_{i=1}^{n}g(i)$ //ps://在杜教筛中,我们目标函数是$G()$,选取合适的$h$并算出合适的$f$即可提取$j=1$项计算 注意到$f(p)=g(p)+h(p)$,考虑令$g(i)=\sum_{d|i}d=\sigma_{1}(i),h(p)=0$ $f(p^{2})=h(p^{2})+(1+p+p^{2})=1+p^{2},h(p^{2})=-p$ $a>2,f(p^{a})=1+p^{a}=1+p^{a}+\sum_{i=3}^{a}h(p^{i})g(p^{a-i}),h(p^{a})=0$ 设$r(n)=h(n^{2}),r(n)=\mu(n)n$ 又考虑积性,$F(n)=\sum_{i=1}^{\sqrt{n}}h(i^{2})G(\frac{n}{i^{2}}) =\sum_{i=1}^{\sqrt{n}}\mu(i)iG(\frac{n}{i^{2}})$ **评论:** 对于积性函数，除了直接套用各种模板性的现成公式 也可以学习模板推导过程，进行自己的推导 ===== 肖思炀 MountVoom ===== 构造题废物推荐一道构造题。 [[https://codeforces.com/problemset/problem/1381/A2|A2. Prefix Flip (Hard Version) : 构造]] 题意： 给定两个01串s和t，每次操作可以选择s的一个前缀进行翻转然后全部取反，比如0111->1110->0001。 需要在2n次操作以内把s串变为t串。 题解： 先说的一下我的做法，从后往前扫，如果s[i] = t[i]则跳过，如果s[i] != t[i]考虑s[1]，如果s[1] != t[i]直接翻转，否则先翻转s[1]再翻转前i位。这样做需要维护一下当前的s[1]和s[i]，开始想维护整段甚至想上splay(不至于不至于)。 然后在zzh鸽鸽的指点下，这种题先考虑操作是否可逆，即连着两次操作相当于没有操作。然后观察到我们可以在n步以内把一个串变成全0或者全1，那么顺着操作一下s再逆着操作一下t就完事了。非常的简单好写。 comment： 注意考虑操作是否可逆，这样可以考虑"meet in middle"，把两边都转成同一个简单状态。