算法竞赛trick

其他优秀的trick总结

洛谷tricks以及这篇文章引用的其他文章

对于输入特别简单的题，可以打表找规律，可以是输出单个数值的规律，也可以是输出的方案的特点。

翻转或奇偶性转化成异或问题，相关的操作约束可建模成异或方程组。P16225。

使用 bitset 维护少数几个点到其他所有点的可达情况。ABC453E。

从特殊情况出发，比如图是一棵树怎么做，树是一条链怎么做，有可能会受到启发。

把 $n$ 拆成若干个不同的正整数之和，至多拆成 $O(\sqrt n)$ 个。P1295 可以利用这个事实发现每个 DP 值计算时的转移次数是根号级别的（非正解但可过，数据增强见 P10977）。

求代价第 $k$ 大的方案的代价，可以转化为二分代价大小，然后看有多少个方案不超过这个代价。P10838。

圆外一点，向圆做切线，两个切点的极角组成区间 $[a, b]$ ；反过来，指定两个切点做切线，这两个切线也至多交在一个点。因此圆外的点可以转化成极角区间的问题。P3091。

$n$ 条线段两两有交，则必然存在一个点，被 $n$ 条线段同时覆盖。但如果是环上的 $n$ 条弧两两有交，则不一定存在这样的点，因为可以环的首尾交。

若干个字符串，选择一种拼接顺序得到字典序最小的字符串，只要排序即可，排序规则是看对于 $s$ 和 $t$ 这两个串，是 $s + t$ 小还是 $t + s$ 小。P12186。

把求是否能成功，转化成求成功的方案数。梦熊P14265。

想以每个位置作为起点做 DP，会有很多重复计算，可能可以考虑序列分治，计算中点向左向右的值并合并。ABC456F。

字符串相关的 DP 题，一种设状态的方式是，考虑了前 $i$ 个字符，目前末尾最长有 $j$ 个字符匹配到了（某个）模式，然后使用 KMP 自动机或者 AC 自动机，去看新加一个字符之后跳转到了哪里，并进行相应的转移即可，刷表实现。P16231。

对于类似 $\frac{i}{j}$ 的求和问题，如果固定 $i$ 枚举 $j$ 就是拆成根号段不同的值球盒，反之则是调和级数的复杂度的分段求值。P10390。

求恰好的个数，转化成求至少的个数，然后根据情况用（高维）前缀和得到恰好的个数，或者也可能广义容斥就可以处理出来恰好的个数。ABC458E。

预处理起点到其他点以及终点到其他点的某个信息（比如最短路），然后枚举要特殊操作的边。

建反图。

补图问题，

涉及从 $i$ 到 $j$ 恰好走 $k$ 条边的最短路问题，考虑倍增优化。

每个点有多种不同的状态，但状态数不多，可能可以建分层图。

DAG 上求从一个入度不为 0 的点出发，走到某个点的某个值，可以只初始化这个点的值为有意义的值，其他的点都是无穷大/无穷小，这样直到拓扑排序到这个点才算开始进行有意义的 DP。

基环森林上找环，可以建内向基环森林后拓扑排序得到环上的点，也可以 tarjan，求出的大小至少为 2 的 scc 就是环。

求某种性质的路径是否有必经点或者必经边，有一个思路是求起点到 u 的路径数，以及终点到 v 的路径数，二者相乘如果等于起点到终点的路径数（哈希），说明这就是必经的。这个用在最短路上比较多，但有一些一般性的路径判断连通性时也会用到。（感觉好像就是在求桥啊）

如果一个字符串 $s$ 是由某个 $t$ 拼接若干次得到的，则 $t$ 的最小长度是 $n - next[n]$ ，最后一次可以拼得不完整。P4391。

有一些算法写错了只影响复杂度，但对拍看不出来问题，比如树上启发式合并选错重儿子。