技巧
2026-04-24
数论
- 对于一个形如 ∑f(x) 的东西,如果 f(x) 具有递推公式,则可以将其在内部展开,经过拆解,添项转换为 f(x),f(x−1) 之类的,经过消项之后可以得到新的式子。
CF1548C
DP
- 如果出现状态数与答案范围差距较大,可以考虑交换状态和答案。
- 如果状态与进制有关,且每一位相互独立,可以试试开拆高低位。
3579.晚安。 - 遇到状态无法放入 DP 的转移,可以考虑贡献延后计算。
P14364 [CSP-S 2025] 员工招聘
线段树
- 如果需要用线段树分治+可撤销并查集,可以合并 x→y 时 w[x]←w[x]−w[y],撤销时 w[x]←w[x]+w[y]。
CF1814F Communication Towers - 对于给定一些区间,求合法区间个数等的问题可以:
- 把询问离线,按照右端点排序。
- 枚举右端点,用数据结构维护左端点。
P4747 [CERC2017] Intrinsic Interval
树形 DP
- 树形 DP 中如果子树不好考虑可以考虑全局贡献。
- 如果子树内状态不好转移,可以考虑转换为 DFS 序上的转移。
字符串
- 遇到字符串替换问题可以将原串与替换串压缩。
P14363 [CSP-S 2025] 谐音替换
