旧试题

复习计划

旧试题

多回顾以前会的算法来形成自己的体系. ---zzs

较熟练:

6.19 SAM
6.17 SA
基础李超树
splay
Min-Max 容斥
分治NTT

较生疏:

数据结构(图)
6.17 左偏树
6.14 K-D TreeP3769 [CH弱省胡策R2]TATT
6.10 动态点分, 边分(三度化)BZOJ2870.最长道路tree
6.15 笛卡尔树
6.15 斯坦纳树
6.14 (混合图)欧拉回路

LCT(维护子树信息)P4546 [THUWC2017]在美妙的数学王国中畅游
长链剖分(k级祖先)[POI2014]HOT-Hotels 加强版
点双,边双,双强联通分量相关
prufer 序列(运用,转化)
二分图最大权匹配-KM算法

数学
6.13 (ex)CRT
6.15 线性基(第k大, 离线删除)总结
6.14 任意模数NTT
6.15 杜教筛, 线性筛法
6.15 (线性)高斯消元[BJOI2018]治疗之雨可能还要看看的题解
6.16 Miller-Robin
6.18 容斥UOJ390.【UNR #3】百鸽笼
6.18 反演(子集反演, strling反演, Mobius反演, 最值反演, )总结
6.18 数论相关(狄利克雷卷积, 数论函数及其性质)
6.19 Burnside(Polya)
6.19 原根相关
6.19 多项式相关 (求逆, 求ln)
6.19 (ex)BSGS

(ex)LUCAS
strling数(CF961G), 组合数, Bell数, Catalan数的trick
Pollard-Rho
"十二重计数法"

其他
6.15 差分约束
6.17 带修莫队, 树上莫队, 回滚莫队
6.19 半平面交
6.19 旋转卡壳
6.19 CDQ分治
6.19 整体二分

DP 优化 (单调性, 斜率, 四边形不等式)
网络流, 费用流模型
KMP, AC自动机的运用
回文自动机
Manacher
博弈论(SG, NIM..)总结

完全不会:

610 Segmenttree beats BZOJ4695.最假女选手
6.19 圆方树(仙人掌)

线性代数相关(常系数齐次线性递推, BM, C-H定理, 特征多项式相关, 矩阵树定理)
可持久化平衡树
插头DP
树套树
wqs二分
Min_25 筛
多项式相关 (exp, 开根, 快速差值, 求值)
带花树算法
二次剩余

考试总结(复习)

6月

1. test20200616旅行(AGC023D): 正难则反! 在时间上从后往前考虑会很简单
2. test20200613干扰: \(n\) 个点的凸包, 任取三个相邻的点构成的圆, 这些圆中最大的那个一定包含了所有的 \(n\) 个点.
3. test20200612Three: 每个区间的贡献是前三大的数的积, 算所有区间的贡献和: 将每个区间的贡献在最小的数处算, 然后从大往小插入数字.
4. test20200611行走: 相同个起点终点, 求不相交的路径总数: 容斥->行列式(LGV定理).
5. test20200611蚯蚓: 如果有加点, 删点操作, 可以考虑 trie 树; 每次暴力重构 trie 的时间复杂度是对的.
6. test20200609数列: 给定一个数列然后一个数一路模过去的题, 考虑最小的数放在哪, 然后相当于可以随便选; 考虑将所有数从大到小排序然后依次确定每个位置填啥数, 某些数如果当时不填后面就没用了.
7. test20200608matrix: 贡献分开考虑(计算), 如果一起考虑的话可能并不是很好算, 但是确定了左右端点之后贡献就只需要管完全相同的部分即可.
8. test20200606sequence: 正确识别考场上给出的 NPC 问题, 不要做徒劳的思考.
9. test20200606仙人掌: 学会考虑计数的意义, 不要无从下手.
10. test20200605要换换名字: 正确观察性质
11. test20200605获取名额: 学会用数学工具解决问题, 对于连乘的形式, 可以把它去对数变成连加的形式.
12. test20200605动态半平面角: 牢记区间 LCM 的拆贡献算法, 在树上用 LCA 搞搞即可.
13. test20200603排序: 排列问题, 直接设状态高斯消元搞不得, 于是想到用轮换去计数, 这样划分数就挺小了.
14. test20200603机器人: 树上联通块问题, 每次覆盖一条路径, 有多少个联通快等价于有多少个点到父亲的边没有被覆盖.
15. test20200601染色问题: 同样是 NP-Hard 问题, 那么只能通过缩小问题规模解决. 由于保证了m-n<=5, 那么把所有二度点和三度点都缩掉, 可以将数据范围降智 n<=10 且 m<=15. 缩边的时候对于每条边记录一下这条边两端颜色相同/不同时的方案数.

5月

1. test20200529盗梦空间: 考场上适当分析难度, 认为最简单的题不一定真的是最简单的题; 虚树, 有多个点的时候可以考虑求出每个点的管辖范围.
2. test20200526骨牌: 注意区分 插头 和 轮廓线 的区别. 这道题用 插头 可能会很麻烦.
3. test20200525梦批糼: 三维问题考虑降维; 矩形面积的差分算法.
4. test20200525等你哈苏德: 注意可以用到网络流模型; 混合图网络流的解法.
5. test20200521图: 经典染色计数原理, 对于一个点如果和它颜色不同的点的颜色互不相同则可直接乘法原理.
6. test20200518s3mple: 转移时用到多项式卷积的, 可以考虑转成点集运算在转回来 应该是一个烂大街的技巧了.
7. test20200518s1mple: 状态数太多可以考虑合并相同的状态(枚举划分之类的...)
8. test20200516栈: 直接做不好做考虑转化顺序, 比如扫描时间线之类的.
9. 五一集训

• 通过导数算两次的方法来求一个多项式的 \(n\) 次幂.
• 学会分类讨论, 通过不变量计数.
• 线性基的 \(O(\log)\) 离线删除操作(拟阵, 类似最大生成树), 以及在线删除操作.
• 适当的根号分治优化, 在涉及 GCD 的问题上考虑质因子及其次幂的贡献, 学会按照套路将式子化成好维护的形式.
• 学会往费用流方面想, 并看能不能模拟.
• 用 FFT 处理关于通配符的 字符串匹配问题.
• 计数(概率,期望)问题每个元素分开考虑
• 涉及 DP 优化时, 如果要求单调性看能不能将 DP 值取个 前缀 max.
• 要理解一些排序的原理.
• 莫队算法注意如果询问和修改次数不一样要平衡.
• 考场上大胆猜想+打表.
• 学会适当的放松一些条件来计数.
• 涉及到在自动机上走的问题(DP), 看能不能倍增或者轻重链优化.
• 计数但是不用模数输出的题, 往往精度不要求做到完美.

数学

组合数拆成多项式

贡献是组合数的时候考虑将其拆成多项式来维护.(如果底数比较小的话)(下降幂多项式)

广义二项式定理

牛顿二项式系数 \({r \choose n}\), 设 \(r\) 为实数, \(n\) 为整数:

\[{r \choose n}= \begin{cases} 0， & n<0\\ 1， & n=0\\ \frac{r(r-1)\cdots (r-n+1)}{n!}， & n>0 \end{cases} \]

广义牛顿二项式定理:

\[(x+y)^{\alpha}=\sum_{n=0}^\infty{\alpha \choose n}x^{n}y^{\alpha-n} \]

其中 \(x，y，α\) 为实数，且 \(\mid\frac{x}{y}\mid<1\).

数论函数常见等式

• \(\phi*I=id\)
• \(\mu *I=e\)
• \(\mu *id=\phi\)

邻接矩阵行列式的计算

考虑其"几何意义", 相当于把所有排列的贡献求和. 注意到一个排列有贡献当且仅当全是 1. 那么原图中点 i, p[i] 就必须有边. 这样下来原图相当于被分成了若干个环(或者匹配). 考虑算逆序对数, 由于一个连通块可以通过交换 sz-1 次变为升序, 而交换一次必然会改变逆序对的奇偶性, 所以这个排列的贡献就是 \((-1)^{\sum (sz_i-1)}=(-1)^{n-cnt}\), 其中 \(cnt\) 为联通块数.
test20200606仙人掌.

常见泰勒展开公式

在 \(x_0\) 处展开:

\[f(x)=\sum_{i=0}^{\infty}\frac{f^{(i)}(x_0)\cdot (x-x_0)}{i!} \]

对于精度误差要求在 \(10^{-8}\) 左右的题目一般取前 15-22 项来算即可.
「THUWC 2017」在美妙的数学王国中畅游:展开后用 LCT 维护.

test20200605获取名额:直接维护可能会爆精度, 需要根据 \(x\) 的大小分类讨论一下.

自然数幂和的处理问题

\[\sum_{i=1}^{n}{i^k} \]

设 \(f(n)\) 为这个值, 可以证明 \(f(n)\) 是一个 \(k\) 次多项式. 于是求出前 \(k+1\) 项的和作为点值插值即可.

区间 LCM 问题

问题描述: \(n\) 个数 \(a_i\), \(Q\) 次询问区间 \([l,r]\) 的 \(LCM\pmod {MOD}\), \(N,Q,a_i\leq 10^6\).
考虑将区间挂在询问右端点上, 然后从左到右扫数列, 将质数的贡献分发到它的每个幂次上去. 具体来说就是对于每个 \(p^k\) 记录它上次出现的位置, 然后加入一个数的因子 \(p^k\) 的时候就将 \(p\) 所有不大于 \(k\) 次幂的贡献搬到这个位置. (其实好像就相当于给每个质数维护一个单调栈, 然后差分一下?)
强制在线, 把树状数组换成主席树即可.
test20200605动态半平面交.

不相交路径计数

.
test20200611行走.

对 任意划分的 \(\prod_{i=1}^{k} x_i\) (其中 \(\sum x_i\) 为定值 \(p\)) 求和的技巧:

反过去考虑插板法的组合意义,相当于插板完成后在每一组都任意选择一个代表球的方案数。那么列方程的时候变成两个变量,表示选的代表球之前的数目和之后的数目. \((X_1+Y_1)+(X_2+Y_2)+\dots+(X_k+Y_k)=p-k\). 类似的, \(\sum\prod\binom{x_i}{k_i}\) 也可以这么考虑.

子集反演

首先有一个结论:

\[\sum_{T\subseteq S}(-1)^{|T|}=[S=0] \]

于是乎

\[F[S]=\sum_{T\subseteq S}{G[T]}\Leftrightarrow G[S]=\sum_{T\subseteq S}{(-1)^{|S-T|}F[T]} \]

二项式反演

\[\sum_{i=0}^{n}{(-1)^i\binom{n}{i}}=[n=0] \]

参考, 参考:

\[f_n=\sum_{i=0}^{n}{\binom{n}{i}g_i}\Leftrightarrow g_n=\sum_{i=0}^{n}{(-1)^{n-i}\binom{n}{i}f_i} \]

min-max 容斥

\[\max(S) = \sum_{T\subseteq S, T \neq \varnothing} (-1)^{|T|-1}\min(T) \]

\[\max\ _{k}(S) = \sum_{T\subseteq S, |T| \geq k} (-1)^{|T|-k}\binom {|T|-1}{k-1} \min(T) \]

裴蜀定理拓展

方程

\[a_1x_1+a_2x_2+\dots+a_kx_k=y \]

有整数解的充要条件是 \(\gcd(a_1,a_2,\dots,a_k)|y\).

多项式相关

基础求导运算法则:

• \((fg)'=f'g+fg'\)
• \(\left( \frac{f}{g} \right)'=\frac{f'g-fg'}{g^2}(g\neq 0)\)

序列求前缀和相当于乘上 \(\frac{1}{1-x}=\sum_{i=0}^{+\infty}{x^i}\).

经典线性高斯消元

在树上时, 如果 \(f[u]\) 的值和与它相邻的节点有关, 可以设 \(f[u]=A_uf[fa[u]]+B_u\)(类似待定系数, 需要注意的是它要能够这样表示), 然后推式子发现 \(A_u,B_u\) 只和 \(u\) 的儿子有关, 于是可以从下往上递推. 例如「PKUWC2018」随机游走.
同理, 在序列上时, 若 \(f[i]\) 的值和 \(f[i+1],f[i-1]\) 有关, 可以根据具体性质, 设 \(f[i]=A_if[i-1]+B_i\), 然后想办法求出 \(A_i,B_i\) 的值. 例如「SHOI2017」分手是祝愿.

斐波那契 GCD

结论: \(\gcd(f[n],f[m])=f[\gcd(n,m)]\).

关于杨辉三角

test20200526二分图

用杨辉三角的前 \(n\) 行, 在每一行中选择一段连续的前缀, 使得前缀大小不降, 然后将选择的数加起来, 可以凑出 \([0,2^n-1]\) 中的所有数, 贪心从下往上构造即可.

多元二项式定理

\[(x_1+x_2+\dots +x_k)^p=\sum_{c_i\ge 0,\sum{c_i}=p}{\binom{p}{c_1,c_2,\dots,c_k}\cdot \prod_{i=1}^{m}{x_i^{c_i}}} \]

库默尔定理

设 \(n,m\) 为正整数, \(p\) 为素数，则 \(\binom{n+m}{m}\) 含 \(p\) 的幂次等于 \(m+n\) 在 \(p\) 进制下的进位次数.

排列相关

排列问题可以考虑按照置换, 将相同的归为一类来减少状态数.
test20200603排序.

图论

树直径

• 距离树上任意一个点最远的点一定是树直径的一个端点之一.
• 若干条树直径一定相交于中点(边).

树上联通块问题

(若干条连并成的)树上极大联通块, 可以考虑给每个联通块选择深度最浅的点作为关键点, 转化成求有多少个点被标记而其到父亲的边未被标记.
test20200603机器人.

平面图的欧拉定理

设 \(v,e,f,c\) 分别为平面图的 点数, 边数(\(e\le 3v-6\)), 面数, 联通块数, 则 \(v-e+f=c+1\).

竞赛图的性质

例题.

字符串

关于回文串

以任意一个位置 \(r\) 结尾的所有回文子串 \(s[l_1..r],s[l_2..r],s[l_3..r],\dots,s[l_k..r]\) 的左端点按照从大到小排序后的序列 \(l_1,l_2,l_3,\dots,l_k\) 可以被划分成 \(O(\log n)\) 段, 使得每一段都是等差数列.

求 区间本质不同的回文串个数 就要用到这个引理.

字符串首尾添加, 删除字符的问题的 trick

可以考虑转化成 trie 树, 删除操作直接向父亲走.
AC 自动机上一个点 fail 树的子树中的所有点都是这个串的超串, 于是统计子树和即可.[NOI2011]阿狸的打字机.
如果首尾都有删除, 则可以维护两颗 "对顶" 的 trie 树. 若出现一颗 trie 被删完的情况, 暴力重建, 将根节点选在正中间即可. 可以势能分析出它的复杂度是 \(O(N)\) 的. test20200611蚯蚓.

杂项

swap 调用 STL 的复杂度问题:

????????????,??????,??????,?????????? 调用复杂度：\(??(1)\)
但是在开启 \(??++11\) 的情况下这三种容器 ???????? 的复杂度可以做到 \(??(1)\).
????????????????_??????????,??????????,?????????? 调用复杂度：\(??(??)\)
另外, 对两个数组进行 swap 的操作也是 \(O(n)\) 的，无论开不开 \(c++11\) 都一样
.

看上去很详细的OI知识汇总图

附: 常见泰勒展开公式
在 \(x_0\) 处展开:

\[f(x)=\sum_{i=0}^{\infty}\frac{f^{(i)}(x_0)\cdot (x-x_0)}{i!} \]