各类题目解法总结
一、DP
性质：
-
最优子结构，可拆解并且子问题最优，父问题最优
-
子问题重复性，一个子问题可能会影响多个不同的下一阶段的原问题 (可以从数位DP中清楚地理解)
-
无后效性，即此时的之前状态无法直接影响未来的决策
1.1 区间DP
常见数据范围&解题方法：
| 数据范围 | 类型 | 解题方法 | 复杂度 | 例题&练习 |
|---|---|---|---|---|
| \(50\sim 100\) | 三个区间的合并 | 区间DP枚举两个中间点 | \(O(n^4)\) | |
| \(400\) | 三个区间的合并 | 区间DP+单调队列优化 | \(O(n^3)\) | P4805 [CCC2016] 合并饭团 |
| \(400\) | 两个区间的合并 | 区间DP枚举一个中间点 | \(O(n^3)\) | P1880 [NOI1995] 石子合并 |
1.2 树型DP(DAG上DP)
常见数据范围&解题方法：
树型DP较为灵活，可以和图论、树剖等结合，出难题较为容易
一般优化方法：树链剖分、换根、数论、期望
1.3 计数DP
常见数据范围&解题方法：
| 数据范围 | 类型 | 解题方法 | 复杂度 | 例题&练习 |
|---|---|---|---|---|
| \(50\sim 100\) | 三个区间的合并 | 区间DP枚举两个中间点 | \(O(n^4)\) | |
| \(400\) | 三个区间的合并 | 区间DP+单调队列优化 | \(O(n^3)\) | P4805 [CCC2016] 合并饭团 |
| \(400\) | 两个区间的合并 | 区间DP枚举一个中间点 | \(O(n^3)\) | P1880 [NOI1995] 石子合并 |
1.4 状压DP
- 可能是压一行，也可以压两行
- 熟练掌握位运算
常见数据范围&解题方法：
| 数据范围 | 类型 | 解题方法 | 复杂度 | 例题&练习 |
|---|---|---|---|---|
| 有一维是\(~10(n)~\)以内，另一维较为正常 | 普通状压 | 将少的一维状压成一个数 | \(O(n^2\times m)\) | P2704 [NOI2001] 炮兵阵地 |
| 有一维是\(~3\sim 5(n)~\)，另一维非常大(例如\(~10^{18}(m)~\)) | 矩阵加速优化 | 矩阵加速优化 | \(O( 单行状态数^2\times log_2m)\) | 三行骑士共存求方案数 |
1.5 数位DP
常见数据范围&解题方法：
| 数据范围（数的位数） | 类型 | 解题方法 | 复杂度 | 例题&练习 |
|---|---|---|---|---|
| \(\leq10^6\) | 板子 | 普通数位DP(一般是类似记忆化搜索) | \(O(k\times n)~~k为一个100左右较大常数，n为位数\) | P2602 [ZJOI2010] 数字计数、P4124 [CQOI2016]手机号码、P2657 [SCOI2009] windy 数 |
| 非常大 | 转移方式固定 | 矩阵加速优化 | \(O(100\times log_k)\) 题不同前面的系数不同 | P2106 Sam数、U281339 特别长的密码、U281338 分书 |
| 非常大 | 转移方式不固定 | 数学 | 具体题目具体看 | P3286 [SCOI2014]方伯伯的商场之旅、P2481 [SDOI2010]代码拍卖会（巧妙的拆分） |
二、数学
2.1 GCD&EXGCD
- 备好板子，自己多推几遍
- 本质上是让
gcd中，所有的ax+by = 1
2.2 扩展欧拉定理
当\(~a,m\in \Z~\)时有：
\[a^b\equiv \begin{cases} a^b&b<\varphi (m)\\a^{b~mod~\varphi (m) + \varphi(m)} & b \geq\varphi(m)\end{cases} \]2.3 Lucas定理
\[\binom n m \equiv \binom {\lfloor \frac n p\rfloor}{\lfloor \frac m p\rfloor} \times \binom {n\%p}{m\%p}\mod p \]2.4 CRT&EXCRT
对于CRT，我们有更加清楚的认识，就是通过所有数的GCD来构造出一个解
对于EXCRT，就是通过进行两两合并，然后将模数变成lcm，同余的数用同余方程构造、exgcd求解
三、图论
3.1 联通分量部分
考虑即为dfn和low数组的灵活应用，然后得到了许多同种类的联通块
3.2 二分图匹配
考虑可以用网络流，但是谁会去这样做啊！！
匈牙利算法实质：就是让匹配过的去找其他匹配，换了一种方式寻找增广路
复杂度：\(O(nm)\)
3.3 网络流
全都是一遍搜索(bfs或者是SPFA优先跑出分层图，然后再进行网络流上的真正的填流)
dinic 复杂度：\(O(m\sqrt n)\)
常见建模：
最大流、最小割：
- 最大权闭合子图问题（例题为太空计划问题），本质上是一侧如果流过就选，另一边流过就不选，然后答案即为所有的正权减去最小割
费用流：
- 餐巾计划问题 巧妙的建图，你需要尽力保证你的建图之后得出的答案是题目中想要的答案
- 负载平衡问题 流变成了物体（物体的运入运出变成了流的运入运出）
有（无）源汇、有（无）上下界、可行（最大）流：
- 还只做了模板题QAQ
3.4 图论基本操作
四、字符串
还需要多做一点题QAQ
4.1 KMP字符串匹配
- 考虑就是跳
fail就是最长的后缀等于前缀，相当于失配之后跳到哪里
4.2 AC自动机
trie上KMP，需要记一点结论一个节点的儿子等于他的fail对应的那个儿子
4.3 Manacher
- 就是通过对称的性质减少检查回文串的次数
4.4 后缀数组
- 忘了，待补
4.5 回文自动机
- 同上