7/17
7/19
因为不知道前天要写啥所以就写了个标题
今日 \(AK\) \(AC\) 自动机
写个知识点阶段性总结。
\(AC\) 自动机
一句话就是通过把 \(tire\) 树和 \(KMP\) 结合起来实现快速匹配多个模式串。
其中有一个优化是连成 \(tire\) 图。\(tire\) 图上囊括了很多信息，所以几乎单独成了一个考点。
时间复杂度是 \(O(文本总长度 + 文本段个数 * 字符集长度 + 文本串长度)\)，一般给出的数据范围为 \(1e6\) 左右。
还有一个优化是连成一个 \(fail\) 树，这时可以和其他的数据结构联系起来。
一些例题
板子。
稍微修改一下询问适配时候的语句即可。
\(fail\) 树优化，其他部分同上。
背单词
\(fail\) 树 \(+\) 线段树优化求最大值。
对于 \(tire\) 图的应用。在 \(tire\) 图上能找到一个环说明有无限长的串。
从此题后应该了解到在 \(tire\) 图上 \(dp\) 时，\(tire\) 图的节点也可以作为一维。因为它可以包含所有的状态，而且处理出了最长前缀，有很多有用的信息。
同上。
一看那个神奇的数据范围，应该就能想到是矩阵快速幂。依旧是设的 \(tire\) 图上的点进行转移，还有就是如果算分子分母时位数太大可以考虑同乘或同除。
第一次做 \(special\) \(judge\)。
弄到类似于这种构造题的时候首先要找规律。
7/20
今日模拟赛-\(CSP\) 模拟 \(1\)
都是神仙。
\(T_1\) 大神 \(Rreally\) 提出了倍增解法。
核心思想就是因为每个数的乘法、余数之间是相互独立的，所以可以分步递增处理。
本来还兴致冲冲地以为所有的分步处理都有新思路了，结果发现只有前后无影响的才可以。
总之，就是一种值得保留的思路。
原根做法留坑，循环矩阵是啥呀
\(T_2\) 一种换根 \(dp\)，就是推一推式子。
用到了类似于 游走 的系数计算，我自己想出来的！
\(T_3\) 据说会卡特兰数一眼切，可是我不会呀。
稍微学习了一下，感觉那个等效和数形结合的思路挺强。
还有就是，注意某些部分分的数据范围，不同的约束条件范围可能不同。
\(T_4\) 又是一个非常厉害的思路。
还是注意到 \(dp\) 数组要能够体现所有的状态。
7/21
大雨
今日，\(dp\) 又一次展现了其极限。
7/29
连着改了一周的题，于是就连着咕了一周
要把我们 \(CSP\) 模拟 \(2-8\) 的题都写到这大抵是不可能了，所以只简略地说一说。
开始前说一句，今天又改了一天的题，浪费了很多也收获了很多
改完所有的题之后真是长吁一口气啊……
\(D_2-T_2\) \(dp\) 维护每种颜色的出现次数和上一种颜色，采用填颜色的思路而不是转颜色的思路，树状数组求逆序对，深化滚动数组应用。
\(D_2-T_3\) 考虑组合意义转移的方法，或者直接用两个 \(dp\) 数组维护（ \(dp\) 牛皮！），前缀和相减。
\(D_2-T_4\) 学到一种 \(min\) 等函数拆开的方法，注意用树状数组不要用线段树，常数太大。
\(D_3-T_3\) 加零构造统一序列，树上 \(dfs\)，记得加 \(break\)。
\(D_3-T_4\) 一种二叉树的构造处理，提高码力，构造方法详见此，大概是构造一棵可以快速查出覆盖情况的树。
\(D_4-T_4\) 和 \(D_2-T_2\) 相似？\(dp\) 转移时提前算上内部交换的费用。
\(D_5-T_3\) 数位 \(dp\)，今天改了一下午和半个晚上，现在还有点懵，总之就是维护上下界太难了，\(dp\) 里面设是否压紧上下界。
\(D_5-T_4\) 奇怪的转移？留坑。
\(D_6-T_2\) 感觉跟数位相关的构造挺有意思……
\(D_6-T_3\) 双指针扫一遍，分情况，分治，或者扫描线加线段树。但是场上想的线段树是假的。
\(D_7-T_3\) 根号分治，并且考虑两种常用构造数列的方法。
\(D_8-T_4\) 吉司机线段树，今天早上想了半天终于弄懂了。
其他小事记
\(D_4-T_3\)，\(xuany\) 的假二分跑得比正解快并且 \(AC\)，这正是：假作真时真亦假。
\(D_2-T_4\) 线段树常数太大导致过不去，\(Flandre\) 的小工具也不管用了。
\(D_3-T_3\) \(Flandre\) 卡过去了，数据加强也不管用。
\(D_3-T_4\) 码力 \(+3\)
\(D_4-T_1\) 想出了与题解不一样且更好理解的办法！！！
\(D_4-T_2\) 正着设不行就反着设嘛。
\(D_5-T_1\) 什么鬼贪心啊，为什么能过啊。
\(D_6-T_4\) 数据真的水……题解真的水……最后还是靠自己……
\(D_8-T_1\) \(curly\) 直接以埃氏筛 \(n loglogn\) 的复杂度暴打 \(n logn\)的标算！！！（虽然并没有快多少并且因为常数问题好像还慢了）
\(D_6-T_3\) \(curly\) 以为自己想到了正解狂打两个半小时，最后果不其然拿到了 \(36pts\) 的赛时最高分！！比别人暴力整整多了 \(16pts\) ！！并且直到现在还是所有未 \(A\) 做法的最高分！！（小丑一个）
总结
赛时能拿到的分越来越多了，的确是有一直在进步的感觉。虽然今天没能推知识点有点遗憾，但是改题也带来了一些收获。