<br />
<b>Warning</b>:  session_start(): open(/tmp/sess_5cee404fcf0610956e0a72e0485f415d, O_RDWR) failed: No space left on device (28) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  session_start(): Failed to read session data: files (path: ) in <b>/data/wiki/inc/init.php</b> on line <b>239</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/auth.php</b> on line <b>430</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
<br />
<b>Warning</b>:  Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in <b>/data/wiki/inc/Action/Export.php</b> on line <b>103</b><br />
====== 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'<mlen[x]$。这样我们最后如果面对一个$[p_l,p_r]$，$mlen[x]\ge 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"，把两边都转成同一个简单状态。