博弈论
- 按照博弈状态建图跑拓扑排序判断先后手赢。
组合计数
-
等比数列。\(\sum^n_{i=1} p^i=\dfrac{p^{n+1} - p}{p - 1}\)
-
观察到一个数列有关于
1 3 3 1，1 4 6 4 1，就应该想到binomial了。 -
组合计数不一定为 dp，优化不了考虑一个式子算答案。
树
- 将树分成大小为 \([B,3B]\) 的若干连通块，直接分。多余的点抛给父亲。e.g. prob。
并查集
- 当经过一些对边的贪心处理（e.g. 边权从小到大排序）后，如果要维护的信息可以再两颗树合并时维护，考虑并查集。
哈希
- 集合判相等，考虑集合哈希（赋随机权然后异或）(权值 \(\le n\) 着重考虑，如果否也可以离散化。e.g. prob。
DS
线段树
树的直径
LCA
- 一些区间满足（一个点 / 一条线要求在区间中），考虑通过画图，转换为扫描线。e.g. prob。
杂项
-
多劳多得。
-
仔细检查 ez 题边界条件：越界，0，爆
ll。 -
爆搜 + 剪枝。
-
爆搜优化成 DP 仍然不可行，考虑贪心。