这里记一些从 7.15 开始做的 NOI 篇或者让人眼前一亮的题目/trick。
（哦，前面的题可能忘了某些细节了。）
- P3452
求补图连通块个数。
- P4555
首先看到回文串，先上马拉车。
然后发现马拉车双回文不好做，考虑拆成两部分。
大概就是维护一个以 \(i\) 为左端点/右端点的最长回文串。
然后枚举分界点取个 max 就行了。
- P2375
根据 KMP next 数组的定义，发现这个字符串的公共前后缀一定是形如 \(ne[ne[j]]\) 这样的形式。
题目要求前后缀不重叠，所以判断长度是否超过二分之一就行了。
- P10641
需要长链剖分，然后用堆维护前 \(k\) 大的链即可。
- accoders 10469
求区间 LCA，因为 LCA 是可以两两之间结合的，所以拿树剖维护下 LCA 就行了。
- P3455
把原式化成 \([gcd(i,j)==1]\) 的形式，然后就可以莫比乌斯反演了。
之后是套路的枚举约数之后整除分块了。
- P3649
回文自动机（PAM）板子题。
简单说一下。
首先有两个根：奇根和偶根，表示回文串长度是奇数的信息存在奇根下面，偶数同理。
然后树上每个点走到根再走回来就是原字符串。（边权是字符）
回文自动机的 \(fail\) 指针指的是这个节点表示的字符串的最长后缀。
- P2398 & P1447
这两个题其实可以放到一起说，核心是求 \(\sum_{i=1}^n \sum_{j=1}^m gcd(i,j)\)
有一个欧拉函数的性质：
\[\sum_{d|n} \phi(d)=n \]然后就好做了。
- P3488
Hall 定理的题。
首先根据 Hall 定理：二分图左部点的任意 \(i\) 个点一定可以和右部至少 \(i\) 个点匹配。
然后列不等式，化简发现右边是定值，左边是一个区间和，所以线段树维护最大字段和就行了。
- P2387
写的歪解：动点 SPFA。
考虑如果边只有一个权值是好做的，跑最短路就行了。
现在新加了一个边权，所以想到对一个边权排序，然后每次把所有相同边权的边加进去，跑 SPFA，再统计答案。
- accoders 9003
圆方树板子。建圆方树，对圆方树树上差分，然后统计圆点的经过次数就行了。
- accoders 2334
差分约束纸张题，但是我调了小半天，因为没有 STL。
- P4111
矩阵树定理板子。
简单说一下。
首先说一下拉普拉斯矩阵。
对于任意的 \(i\)，矩阵的 \(a[i][i]\) 为点 \(i\) 的度数。
对于任意的 \(i,j\)，矩阵的 \(a[i][j]\) 表示 \(i,j\) 之间连边数量的相反数。
然后拉普拉斯矩阵去掉任意一行和任意一列所得的矩阵行列式就是最小生成树的数量。
做的时候把它消成三角矩阵，对角线乘积就是答案。
标签：记录,边权,矩阵,然后,暑假,就行了,任意,集训,回文 From： https://www.cnblogs.com/infinite2021/p/18313780