some tricks

some tricks

0. 多从宏观角度想问题，别被微观困住了
1. 十进制快速幂 防止写高精
2. 树的重心在树的dfn序列上的带权中点的到根的路径上
3. 组合数：\(\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}\)，可以 \(O(m)\) 计算
4. 集合划分问题考虑最大权闭合子图（最小割）
5. 选一点（可在边上）使树的最大距离最小，这一点一定在树的直径的中点处
6. 一般图问题考虑圆方树
7. manacher可以考虑DP \(f_i=f_{i-2}-2\)
8. 区间和转前缀和转图论，如 \(sum_r-sum_{l-1}=a \Rightarrow sum_r=sum_{l-1}+a\)，是否能表示一段区间和等价于图是否连通
9. \(\dfrac{a\times(10^x-1)}{9}=aaa…aaa ,(count(a)=x)\)
10. 阶乘可以拆成 \(\lfloor \dfrac{n}{p} \rfloor,\lfloor \dfrac{n}{p^2} \rfloor,…,\lfloor \dfrac{n}{p^3} \rfloor,\lfloor \dfrac{n}{p^c} \rfloor\) 处理贡献
11. 树状树组维护矩形加
12. 二分哈希十分实用
13. 枚举线性基外的数，线性基里找方案即可 \(O(2^{size})\) 找出一个数的所有异或方案
14. 想一想前缀和
15. set并不需要根据准确的值来维护，只用维护相对关系即可 hill walk
16. 对于没有交点的若干条线段，可以直接用 \(y=kx+b\) 全局 \(x\) 维护 \(y\) 值相对大小关系 hill walk
17. 线段区间问题多想扫描线
18. 矩阵可以优化递推
19. 曼哈顿距离绝对值可以拆开讨论取得最近/最远
20. 曼哈顿转切比雪夫且可以分 \(x,y\) 轴讨论
21. 连通的方块可以考虑生成树
22. 字符串多想想SA
23. 倍数、整除的题不妨大胆设 \(k\)，最后发现 \(\lfloor \dfrac{n}{k}\rfloor\) 直接整除分块，可以找到最值，题
24. \(a_i=i\times k\mod p\) 取循环节为 \(L\) 则对应元素相差 \(\Delta=k\times L \mod p\)
25. 树上倍增的一个 trick：若一个运算满足 \(a \oplus a = a\)，则我们称这个运算（例如 \(\max、\min、\gcd\) 等）满足 ” 可重复贡献 “ 性。则可用4次操作得出答案：

原文地址：http://www.cnblogs.com/Quick-Kk/p/somtricks.html