感觉自己综合解题能力还不够，于是刷刷吉老师做过的题。
完成程度：
只有一部分有题解……
-
P4404 发现移除下一次出现更靠后的答案不会更坏。贪心即可。用
pb_ds的优先队列更方便 - P4280 贪心好题。可以证明
-1单调不减，然后直接DP，时空复杂度均为 $O(nk)$ - P3565 直接DP，分别按照DFS序和BFS序转移。复杂度 $O(n^2)$ ，但常数极大，不明原因
- 有 $O(n \log n)$ 的长链剖分做法，有时间了看看
- P4503 hash后枚举不同位置。注意把完全相同的加回去。
- $6 \times 10^6$ 的范围，无论是
std::map还是std::unordered_map或者__gnu_pbds::gp_hash_table都过不了! 因为std::map带 $\log$ ，哈希表常数很大！所以说理论上 $O(nl)$ 的算法实际上没有 $O(nl\lg n)$ 的快排+双指针扫描快！
- $6 \times 10^6$ 的范围，无论是
- P3425 网络流点边转化要灵活！要看出经典模型！ 比赛看成边不好做，就换成点，转为二分图多重匹配，这样就是公平分配问题了。
- P4555 枚举回文中心后二分+hash，单独开一个Blog
- P2591 构造后找规律。（膜大佬题解)
- P1361 傻逼题，调了半天，该睡觉了……
- P4317 数位DP统计。对于每位用组合数算。
- P2151 矩阵快速幂。并没有想到DP方程……
- 其实DP方程不难。考虑到起点一定，可以不把起点丢进状态
- 考虑 $f(i, j)$ 表示：走了 $i$ 步在点 $j$
- 发现这样不能满足“不走过上一条边”的限制
- 考虑 $f(i, j)$ 表示：走了 $i$ 步在有向边 $j$ 的终点
- 这样信息量显然大于第一种定义，足够进行转移
- 转移到 $f(i+1, j’)$ 的方程显然是各个 $f(i, k)$ 的线性组合
- 直接用矩阵乘法表示
- 转移矩阵和 $i$ 无关，矩阵快速幂即可
- 总结：
- 矩阵快速幂优化 DP：
- 转移方程转移范围有限 $\to$ 矩阵大小有限
- （大多满足）转移矩阵和转移次数无关；（有时候满足）转移矩阵多次乘后有周期性，且周期较小
- P3311 直接建立AC自动机后进行数位DP，AC自动机没
get_fail过不了样例，get_fail里面 BFS 忘了Q.push(v)居然还有分……真是石乐志，AC自动机是真的不熟练啊……- 数位DP考虑清楚各种细节！
- P4047 贪心好题。利用MST切割性质。
- P2516 重复怎么办？ 第二步DP采用容斥，把多算的减出来即可
- P4292 著名神题，单独开一个题解
- P2149 初等图论好题。膜拜了题解。直接 Dijkstra 后找出两个端点丢在2个最短路的路径这个方法是错的。正确方法是建立出 2 个 $s-t$ 最短路图（显然是 DAG ），然后考虑两个人并排走还是相向走，显然最长公共路径连续而且只能是二者之一。保留两个 DAG 中的对应边后变为了 DAG 最长链，直接 DP。
- BZOJ3545 考虑 MST ，它也是任意两点路径最大边权最小的生成树。于是把边权排序，同时离线询问后按照 $x$ 排序，就是 [HNOI2012] 永无乡，直接启发式合并即可。
- BZOJ3439 倒序插入 Trie 后变为子树第 $k$ 小，在 DFS 序上用主席树解决。主席树写错了真是智障，一定要再写一遍模板！
- BZOJ3091 其实就是把 [HAOI2012] 高速公路给扩展到了动态树上…… 化式子即可。单独写个题解。因为翻转标记调试到死……一定要记住，翻转后任何涉及特定一边子节点的操作，必须考虑 $\text{rev}$ 标记！
- BZOJ3569 神题，同样坑一个题解
- BZOJ3561 推式子，注意莫比乌斯函数性质的应用。不一定要向整除分块化简……以及记住快速幂有个 $\log$ ！
- BZOJ2610 带权并查集，类似星球大战的离线。
- BZOJ2430 类似排序不等式，我们xjb猜测贪心：先切最大的。然后就发现这是对的。其实就是个基于交换的贪心。证明可以考虑整个操作序列的任何两个操作，讨论其位置关系和大小关系。
- BZOJ1978 挺好的DP，考虑以因子为下标维护一个 DP 数组，就可以转移了。
