- 字符串
- 计算一个字符串 \(S\) 的 border 的时间复杂度是 \(O(|S|)\) 的，且与模板串无关。在更换模板串时，不需要重新计算 border。对于两个字符串集合，两两匹配的时间复杂度从 \(m\sum |S|+n\sum |T|\) ，降低到了 \(\sum |S|+n\sum |T|\)。（2.16 A 60pts）
- 动态规划
-
有些题目可以先考虑贪心策略，再在贪心策略的基础上 dp。例如你发现最优策略一定满足选择的是一段区间（但是不知道是哪个区间），就可以使用 dp。（2.17 B 50pts）
-
有些图论问题，最后的答案只与其中的一些量有关（比如 距离），那你在 \(O(m\log m)\) 的时间复杂度内求出 距离，这道题就和图没有关系了。
-
有些题目由多个并列约束组成，最后的方案要满足所有约束，一般是确定一个序列，且序列的前缀要满足某些条件，一般是最优化问题。这种问题可以把约束放在坐标系的折线上，考虑折线上的转移关系。
-
对于一些局限影响的题目，先考虑影响周期。例如一个排列有几个条件，条件本身只基于四个东西的顺序，那你实际的顺序个数只有 \(4!\) 种，可以方便 dp。
-
有一些数据范围不好用 dfs 枚举，但是也是指数级别的，考虑用状压 dp（这个过程可以用 dfs 枚举来转移）。
- 贪心
- 如果一个决策你人类思维下是对的，而且可以过样例，就去写写试试。就比如说，有多个优先级相同的事件，ddl 不同，你肯定优先做 ddl 靠前的任务。
- 数据结构
-
敏感发现 单调性 和 不可逆性：如果一个东西的状态 \(S\) 转移到 \(S'\) 后就再也无法转移回 \(S\)，那可以考虑时间轴上做数据结构。（2.16 C 85pts)
-
只跟排名有关的带修题目，可以通过树状数组维护，典型例子是逆序对。你可能需要离散化，或者将树状数组改成 map 实现（2.17 C）
-
用数据结构维护带修哈希。
- 杂项
-
对于若干个区间 \([l_1,r_1],[l_2,r_2],\cdots,[l_n,r_n]\) 的交，答案是 \([\max^n_{i=1} l_i,\min^n_{i=1} r_i]\)（如果区间不合法则无交集）（2.16 C 50pts）
-
对于一个题目，如果出现了本应该同阶，但实际上出现了（哪怕是部分分）不同阶的情况，考虑离散化。（2.16 C 65pts）
-
双集合题，考虑将其中某一个集合 \(S\) 约束为 \(|S|=1\) 后怎么做。以及，这个集合 \(S\) 中的贡献关系是什么。（2.17 A）
-
定长区间问题，可以通过增量式修改减小常数，在 bitset 硬莽题有用。
-
枚举子串问题，尝试通过约束子串长度降低复杂度。如果只有 \(len\le 10\) 的串会产生贡献，则时间复杂度就是 \(O(10n)\) 级别的。（2.17 C Sub 6、7）
-
如果你能在搜索时，将目前搜索的状态唯一的表示出来，而这个状态可以转移到另外一个状态，就相当于在 dp 里的转移关系。
例如在 2.19 A 的 40pts 做法中：我们的 dfs 内容可以用唯一的四元组 \((n,k,t,l)\) 表示出来。分别表示 将 \(n\) 分成 \(k\) 份，使得最长的一段是长度为 \(l\) 的方案数，目前的这一段长度是 \(t\)。对于一个 \((n,k,t,l)\) ，他代表的情况是唯一的。然后你枚举对于新的数 \(n\)，是切段另起一段还是不切。对于每种情况你有 \(2\) 种选择，看似时间复杂度是指数的，但实际上因为每一个转移情况只会被算一次，所以时间复杂度是四元组 \((n,k,t,l)\) 的数量，也就是 \(O(n^4)\)。
然后其实，你在 \(1s\) 之间内可以计算至多 \(3\times 10^8\) 次搜索，就算把结果全部记录下来也就是 1144 MB，反正你不可能全部存下来，所以写 dfs 搜索的情况下，可以全部记忆化。
然后还有一种更加不优美的，就是对于一个状态你可以对他状压，就比如说最后状压大小是 \(998244353\)，然后每个状态依赖的一定在这 \(998244353\) 种情况里，最优化题目，哈希冲突的情况正好在最优化路径中的概率非常小。
-
有些题目的基本变量被赋值为 \(0\) 时，基本一定有简单做法（不然这个变量没啥意义）。这个 Subtask 就算被排列在比较靠后的位置，也要考虑去完成。如果人类思维无法理解这个 Sub 怎么做，可以考虑打完暴力找规律。
-
有些题目数学意义上的答案应当是个整数（是个浮点数），但是允许给出接近的浮点数（整数）答案。这种过程是丢失精度的，说明这道题需要一些不确定做法。然后，一眼丁真的不可做题也可以当作是随机化题做。
-
如果转移是两个 bool 数组的运算，那可以通过 bitset 使得时间复杂度降低到 \(O(\frac n w)\)。然后，在 dfs 里面，bitset 维度数越低越好；同时，如果可以钦定一些答案必然是相同的，就可以让常数减小一些。
-
学会读样例文件，你发现一个答案上界是 \(10^{12}\) 的题，实际答案只有几十几百个，你就可以思考答案为什么这么小，和随机数据/弱数据的性质是否有关系。
-
如果是关于子集的题目，而且子集之间存在贡献。那么这道题就可以理解为维护 \(S\) 所有子集的子集 这样的题目，可以通过下列算法在 \(O(3^n)\) （而不是 \(O(4^n)\)）的时间复杂度里计算。
for (int m = 0; m < (1 << n); ++m)
for (int s = m; s; s = (s - 1) & m)
证明：对于每一位只有 \(s,m\) 都有，\(s\) 无 \(m\) 有，\(s,m\) 都无 三种情况。
-
如果你发现满足要求的子集一定满足某一个要求，那么上文的 \(O(3^n)\) 就可以转化成 \(O(n\times 2^n)\)。
-
一些要求连续性的序列，随机情况下连续长度是 \(log_{值域}\) 级别的，所以可以有一些基于连续长度的做法。