OI trick or idea.
数论
二进制性质1
在二进制下$gcd(2^k, m)$$kin mathbb{Z}^+$所得到的数在二进制下至多可能产生一位。若存在必定为 $lowbit(m)$ 。CF1748D
拆解max,min
拆解 $\max, \min$ 。
如果要符合 $c>\max(a, b)$ 情况下。我们可以拆成一个且条件： $c>a 且 c>b$ 如果是小于的话的可以拆成一个或条件：$c<a 或 c<b$ 。正确性显然
同理可以得到 $\min$ 的性质
观察大小
如果 $n$ 与 $10^{18}$ 大小差不多时。可以考虑$\sqrt[3]{n}$ 的东西，并且可以带一个 $\log$ 。而且 $\log$ 可以比较大。支持map。
矩阵乘法
如果发现要求一段区间的值，同时数据量很小的时候，而且转移与上一项有关。应当考虑 矩阵乘法。
标准矩阵乘法
可以解决k步问题。
矩阵乘法通常可以加速递推。递推式比较一致的情况下。
通常可以删掉一个 $n$ 但会加上 $\log n$ 再乘以一个矩阵乘法的复杂度。通常是 $k^3$ 。k是矩阵大小
广义矩阵乘法
$c_{i,j} += a_{i, k} * b_{k, j}$
中更改 + 和 * 的符号。但是仍然符合矩阵乘法的结合律的 称之为 广义矩阵乘法。
常用的有
$(max, +)$
$(max, -)$
以上可以解决最长路最短路并且符合矩阵乘法的结合律。
矩阵优化技巧
- 美食家
- 容斥
图
联通分量
可以先观察是否可以缩点。缩点后的性质会很好。
有向图缩点后是一个DAG。
无向图双联通分量缩点后是树。（或者建圆方树）
树
树的直径
有些情况下需要考虑树的直径的性质。待补
构造同构
此时我们应当先观察要求构造的这颗树具有什么性质 然后再进一步考虑树的性质对题目的要求。
点边权互换
点权拆成边权 边权拆成点权。CF915F（点权最大值 + 并查集）
是否同构
判断路径权值和是否相同可以使用hash。
欧拉序应用
对于一棵树的欧拉序上可以找到连续的x, y表示x->y在树上的一一段必经路经。
树的距离
算(a,b)和(a,c)的重叠长度 就是 $\frac{(dist(a,b)+dist(a,c)-dist(b,c))}{2}$
最短路树
考虑最短路树 可以通过 分析 最短路树 分析到所有最短路的性质。
线段树
多线段树
对于区间操作有且互相不怎么干预的明显的特征的可以考虑开多棵线段树维护不同方面的权值。相关练习题也比较多。
数组/数列
差分交换性质
差分等价于 $a_{i-1}+a_{i+1}-a_i$ 。[NOIP2021T3]
括号序列
括号序列可以赋权处理。
( = +1
) = -1
如果这样赋权。必定能转换成一个序列。这个序列是否合法的标准是 $a_n = 0$ 且整个序列均 $ > 0$
搜索
- 若要考虑记忆化时，若其影响的范围区间较小，且在靠后的位置。可以考虑其偏移量变化的影响，减掉一维极大的变化量。Luogu P3953逛公园.
DP相关
期望DP
在一些影响不大的情况下，可以利用 期望的线性性 将DP转化成 概率DP。有可能更方便题目的理解。
时间复杂度相关
调和级数
调和级数 $\sum_i^n\frac{n}{i=1} 与 n\log n$ 同级 参考 Luogu P7960 报数。
观察
其实观察都是一些很基础的东西，需要对一些东西的本质有理解。有很多性质应当被发现。
数据量
当某一数据量太大以至于影响太大时应当仔细观察其影响。洛谷P9838
阶乘
应当注意到阶乘对数据量的影响是巨大的。
转移式
如果发现要求一段区间的值，同时数据量很小的时候，而且转移与上一项有关。应当考虑 矩阵乘法。
相等
判断两个数是否相等可以 调整弱化条件到 判断两数模 $p$ 是否相等。同时性质是两个 $\% p$ 相等的东西 至少相差 $p$ 。
同时，如果考虑到题目有相等的要求时，应当直接 / 间接的考虑 哈希。包括但不限于 同构 / 区间要求 / 等。
注意观察 hash的性质。