<br />
<b>Warning</b>:  session_start(): open(/tmp/sess_080159ebfcac8382fde5469fd770b79a, 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 />
======2020/08/22 -- 2020/08/28 周报======

======团队======

2020.08.25 [[.hdu_2020_3|2020杭电多校第三场]]

2020.08.28 [[.hdu_2020_4|2020杭电多校第四场]]

======个人======

=====todolist（补题）=====

2020牛客暑期多校训练营（第一场）CJY G XX C

2020牛客暑期多校训练营（第二场）**Finish**

2020牛客暑期多校训练营（第三场）CJY J/K ZRX I

2020牛客暑期多校训练营（第四场）CJY E XX G

2020牛客暑期多校训练营（第五场）CJY G/J

2020牛客暑期多校训练营（第六场）CJY F XX I ZRX D

2020牛客暑期多校训练营（第七场）CJY E ZRX A

2020牛客暑期多校训练营（第八场）XX J ZRX B/C

2020牛客暑期多校训练营（第九场）ZRX L

2020牛客暑期多校训练营（第十场）CJY G XX B ZRX F

2020加赛1 CJY **A**/E XX B/C ZRX D

2020加赛2 CJY E

2015ICPC北京 ZRX E (B/F/H)

2020杭电多校第一场 ZRX C

2020杭电多校第二场 CJY B/**D** ZRX K (C)

2020杭电多校第三场 CJY B/**H**/**J** XX A ZRX C (K)

2020杭电多校第四场 CJY **I** XX F ZRX J (A/H)


=====CJY=====

====专题====

大质数分解
====比赛====

Codeforces Round #665 (Div. 2)
====题目====

ecr 94 F
=====ZRX=====

====专题====

平衡树专题

拓扑排序与2-sat专题

====比赛====

2020.08.25 [[.hdu_2020_3|2020杭电多校第三场]]

2020.08.28 [[.hdu_2020_4|2020杭电多校第四场]]

abc 176

====题目====

cf 1791g

=====XX=====

====专题====

后缀自动机与广义后缀自动机：添加一道典型题目，添加map实现后缀自动机的写法

AC自动机：添加两道题目

FFT：添加模板，添加两道题目
====比赛====

Atcoder Beginner Contest 176
====题目====

Codeforces 1383/C 1389/F 1392/F

hdu多校第二场 H
======本周推荐======

=====zrx=====

**题意**

序列里有k种不同的数，你每次可以询问l~r，可以得到其中众数是多少，这个众数出现了多少次，最多询问4*k次。

**思路**：

如果这个众数大于len/2，那么能确定[r-l+1,l+r-1]的区间里是众数

4*k很容易想到线段树

每次在线段树上询问，如果能确定的话，就询问剩下两个区间，否则询问l，mid和mid+1，r

算一下最坏情况也是4*k

**评论**：

4*k的操作数可以想线段树

一个数如果在区间出现次数大于len/2，那么能确定[r-l+1,l+r-1]的区间里是它

=====cjy=====

ecr 94 F

**题意** 

有一个由1-9组成的字符串，定义x-prime串为该串所有数字之和等于x并且不存在连续字串使得和是x的真约数。

求最少删多少字串可以使得不存在x-prime。($x\leq20$，$|S|\leq1000$)

**思路**：

直接状压dp是不太可能的，如果能细心一下，可以发现所有不合法的x-prime串实际上在字典树上的节点个数非常少，因此我们可以在AC自动机上

dp，这样就能通过这道题。

**评论**：

本题巧妙在于它存储状态是采用了AC自动机来存储，而不是状压，这个题可以好好琢磨琢磨。

=====XX=====

====[SCOI2012]喵星球上的点名====

来源：SCOI

算法：广义后缀自动机

**题意**：每一个人的名字由两个字符串构成，如果询问串为某个人的某个串的子串，那么这个人即被点到。对于每一个询问串，输出点到了几个人。全部询问结束后，输出每个人被点到的次数。

**思路**：

对名字建广义后缀自动机。

询问一：预处理每一个节点会被多少个人的名字包含。枚举每一个人的名字，对于每一个节点，向上跳fa，对其所有后缀的sz进行更新。对每一个询问，找到对应节点，输出sz即可。

询问二：对于每一个询问串，对其所在节点vist更新。全部询问结束后，枚举每一个人的名字，对于其中每一个节点，向上统计其所有后缀的出现次数。


**评论**：

在广义后缀自动机上的统计问题要注意利用自动机的性质。