一些 trick

MatrixGroup · 2023-08-18 11:35:01 · 算法·理论

老早之前想开的坑了。现在先放着。

1. 三维偏序的判定可以使用二维偏序做。例题：ABC309F CF1187D

2. 如果符合要求的形如一段区间可以对区间进行 dp。例题：P5813（加强） CF1852D P6891

3. 为了优化有边界情况的 dp，考虑 镜像法。

4. 交换值域与状态。例题一大堆。

5. 如何更好的计算容斥？。

6. 对于集合的相等判定问题，考虑 xor hashing。

7. 若 dp 中贡献有加有减，考虑用差分贡献使贡献不降。

8. 若贡献关于排列中的邻项，考虑 连续段 dp。

9. 如果值域太大而条件只是互不相同等等，考虑映射到一个小值域。例题： Codechef CONNECT CF1641D P7450

10. 对于“不少于一半”类问题，考虑 随机化。

11. 求一些序列的前 k 大可以把每个序列最大的放到堆里，每次弹出一个，改为它所在序列中的下一大。例题：P5283 P1631

12. 对于“有多少种存在合法方案问题”，建 NFA，把“NFA 中能达到的状态集合”作为状态转 DFA，发现状态数不多转移即可。例题：麻将题，THUPC 决赛 2024 L，AT_mujin_pc_2018_h

13. 判断合法性的同时尝试判断需要增加还是减少即可二分出合法区间。

14. 对于相邻 00 或 11 的操作考虑奇数位反转。

15. 树的拓扑序最优化考虑树上邻项交换。

16. 二分分数不会 S-B 树可以先二分实数然后构造方案求精确解。例题：HDU8053。