zhangxixi的博客

判定转状态+序列问题上树形dp：0909T3 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132796834 考虑没有括号怎么做。 对于这类+*表达式求值问题，正常思考的dp是状态 O(n)O(n)O(n) ，总共为 O(n2)O(n^2)O(n2) 的 但其实可以对于每个dp记录两个值，分别为答案dp，和后面的乘积和g 如果接乘号，就是 [j](dp,g)→[j](dp+g(i−1),gi)[j](dp,g)\to[j](dp+g(i-1),gi)[j]...

生成树、Prufer序列的计数问题：0912T1 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132839073 看到生成树计数，很容易想到生成树计数 然后发现每个点有度数限制，我们可以先考虑枚举每个点的度数（也可以是Prufer 序列中的出现次数） 假设出现次数为 aaa ，可以得出其生成树方案为 n!∏(ai−1)!\frac{n!}{\prod {(a_i-1)!}}∏(ai​−1)!n!​ 然后后面是个组合数的形式，然后需要推一堆式子 巧拆阶乘...

Cayley 公式 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132832172 nnn 个点的完全图生成树个数为 nn−2n^{n-2}nn−2 如何理解 一个生成树和其prufer序列是唯一对应的 所有生成树和所有Prufer序列形成一个双射关系 而Prufer序列长度为 n−2n-2n−2 ，值域为 nnn ，所以方案为 nn−2n^{n-2}nn−2

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][...