zhangxixi的博客

Prüfer / Prufer 序列 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132090250 ​ 快速跳转 P6086 【模板】Prüfer 序列 OI-wiki 结论：一个完全图的生成树个数为 nn−2n^{n-2}nn−2 注意，生成树是指无根树 构造过程 从小到大枚举叶子节点（指度数为1的点），记录其父亲。 最终为｛2，2，3，3，2｝ 考虑树如何线性建。 12345678910111213141516void sol1() ...

AC自动机小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818609 AC自动机是一种多模匹配算法。 常见操作 查询一个串的子串 任何一个串的子串都可以表示成他的一个前缀的后缀 他的前缀可以在Trie树上查询 后缀相当于其在fail树上的所有祖先 例1 ： HDU4117 接上。首先AC自动机要学会离线。 对于每个点查询祖先复杂度很大。但其实可以每个祖先计算其对子树的贡献。 而这个过程可以对fail树的dfn序建线段树维护 例2 ：HDU4787...

Kruskal重构树+AC自动机+树状数组：Gym - 104542F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132818179 https://vjudge.net/contest/579844#problem/F 看到连边和没有强制在线，考虑Kruskal重构树 看到判断子串，考虑AC自动机+线段树 然后要非常大胆地把两个结合起来。 然后就是大码量了。 具体总结一下流程： 先建出Kruskal重构树 对Kruskal重构树处理...

根号重构AC自动机：HDU4787 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132812068 https://acm.hdu.edu.cn/showproblem.php?pid=4787 每次重构AC自动机复杂度非常大，但其实可以根号重构 维护两个AC自动机，一个大，一个小，然后对操作序列分块 小分块维护当前块的AC自动机，每次操作都重构 大分块维护之前的AC自动机，每 q\sqrt qq​ 次操作重构 对于任意不支持修改数据结构，都可以根号重构 ...

离线建AC自动机维护子串+线段树维护AC自动机：HDU4117 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132804430 https://acm.hdu.edu.cn/showproblem.php?pid=4117 离线处理 AC自动机每次插入都要重构，但其实可以先离线建好，再进行操作 AC自动机理解——维护子串 每个子串都可以表示成一个前缀的一个后缀。 任意一个前缀是Trie树上的一个点，然后其对应后缀就是fail树上的祖先 fail树本质是一个...

贪心问题丢树上-＞利用决策唯一+贪心完后缩点为一个子问题：0909T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132795053 不考虑上树，就是个经典的贪心，也就是按 b/ab/ab/a 排序。 丢树上，要求父亲必须比儿子先选，也就是多了一种限制条件。 但此时先从全局出发，对于某个节点若其 b/ab/ab/a 为全局最大，那么 选完父亲后必须选他 ，因为选择走其他地方必然没有走这里更优。 然后此时对于这个父亲节点，他现在的 决策唯一 然后我们就可以...

超长序列计数从值域入手（判定转状态）+分析dp状态数量：arc146_e 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132794937 https://atcoder.jp/contests/arc146/tasks/arc146_e Trick1 超长序列从值域入手（判定转状态） 通过绝对值的条件，其实我们可以从小到大放每个数。 对于两个相邻的同样数 iii ，他们之间必须放 i+1i+1i+1 因此可以设计 dp[i][j][0/1/2]dp[i][...

类欧笔记存档 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132792181 电子版： https://blog.csdn.net/zhangtingxiqwq/article/details/132718582

回文自动机PAM小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132136120 https://www.luogu.com.cn/problem/P5496 类似AC自动机，维护两个指针，nxt和fail nxt表示当前回文串开头末尾都接a转移到哪 fail表示当前串最长broder PAM关键点：一个回文串的broder一定也是回文串，而且所有回文子串（末尾相同）都可以用此方法构造 然后转移和AC自动机类似。 几个理解上的易错点： fail...

异或和大小比较类问题——抓住最高位：CF1863F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132629186 https://codeforces.com/contest/1863/problem/F 因为有等于，所以考虑异或和为0的合法区间，它可以随意切 现在考虑切开后左边大于右边，可以发现左右边最高位可以互相抵消，似乎不太可做？ 此时可以换个考虑，考虑大区间的异或和的最高位，这一位在左右两个区间 恰好 有一位为1，而为1的那个区间就是...