难以想到的算法：

分治！

随机化！

遇到不会的判断条件，尝试转化它，写出来成立的充要条件，考虑优化

求解概率、期望的几个常用技巧

1.高斯消元。

2.将每个点的dp值表示为另一个点dp值的函数。例如树形期望，表示成关于fa的dp值的函数。对于dp的下标单调递增的期望，可以将所有的f表示为kf_0+b的形式。

3.生成函数。

生成函数

如果在GF里，要对一个常数次项多项式开根，可以手推出开根后系数的递推式。

递推式大概是：(n-1)a[n-1]-6na[n]-(n+1)a[n+1]-a[n-1]=-3a[n]

同理，我们可以快速求出G(x)=Q(x)^P：先求导，两边乘Q(x)得：

G'(x)=PG(x)Q'(x) 同理多项式除法可以手玩出递推关系。 ### 见到10进制位的乘积，意识到质因数只有2357！ ### 见到01状态，想到2-sat！ ### 如果在讨论情况时，发现情况过多，不妨建图解决 ### 枚举整数划分的好方法是DP：新加一个1，或者集体+1 环上的问题考虑断环成链（比如延长两倍接在后面、发现有一条边不会经过于是断开它） ### 直接算期望较困难时，不妨考虑每个点的贡献 ### 当若干数的和为N时，不同的数最多有$2\sqrt{N}$种 转换坐标，比如用新的基底表示空间。 遇到下标取模的问题，尝试分$a[i],a[i+n]$两种情况讨论 **插眼法：枚举长度，每隔len放置一个观察点** 如果一道题思路卡住了，不妨想想暴力如何写，尝试从暴力的基础上改动。 **可持久化二分答案** **可持久化扫描线** 推递推式时，如果发现每一项都是$i!$的倍数，不妨都$/i!

循环展开8层最快

如果题目中，某一个数的最大值比较小，可以尝试枚举这个数的值！

在思考时，对于一些贪心、Naive的思路不要轻易放弃，可能可以尝试证明一下，发现这样做就可以满足题目要求了

假如题目给你的限制条件很多，而你只会限制条件较少的情况，不妨容斥。

仔细画出图解，有助于发现题目中的隐含条件

把你要求的东西写出来，或者玩几个样例，答案可能就出来了

要想减小复杂度，对每个产生复杂度的地方（对每个log），仔细想想能不能用一些题目特点去掉。

见到“最大值（或其他的值）=x”的概率，转化为\le x的概率

见到区间最小值，想到笛卡尔树

对于排名可能会变化且贡献与元素顺序有关的题（最小方差生成树），可以考虑枚举所有元素的顺序（在一些题里只有O(n^2)种）；或考虑每个元素在什么时候贡献。

遇到比值的题，除了01分数规划，还有一种可能是：只选其中最优的一个

因数个数不多！！！

子序列由于不连续，所以性质不太好维护，我们换一种思考方式——值域

类似“...和...是否全等”的问题，我们可以Hash！

遇到求“互不相同”的数量，往往从“相同”的条件出发，能够找到更多性质。

发现式子推不动了——从组合意义的角度去考虑！！！

填一个序列，除了从前往后填，还可以一种一种（从小到大）填，有时这样不容易算重！

CF936E：若题目条件：网格图，有黑白两种颜色，黑点和白点集合各自四联通——对每列（行）拆点！

见到“区间两两要么不相交，要么一个包含另一个”->建出关系树来！

树上路径->点分治

统计树上所有路径的好方法！

之前一直都是树形DP，在LCA处统计贡献或者维护子树内子树外的信息。我们可以直接以边为单位，表示从有向边(u,v)开始的，所有路径的信息！（例题：LOJ迷失的字符串）

好方法（APIO2019T1）：根号重构！ 把操作每sqrt个分成一块，重构时不加入这块中被修改的边，这样每次操作就只有加边了。

用平衡树维护相对关系是一个常用的技巧。

DP优化方程

有的DP优化方式不是那么显然的，对于这种情况，我们应该写下转移方程，为了发现一些神奇的性质，可以设j<k，找出i从j转移由于从k转移的条件

贪心构造题/位运算题：从高到低位确定

两条链(a,b),(A,B)的链并长度的两倍等于两条链的长度+dis(a,A)+dis(b,B)

见到填最大值，不要总是想着从小往大/从前往后填。我们可以限制最大值的大小，直接枚举最大值的位置！

遇到奇怪的字符串相等问题，可以尝试交叉写下字符，找回文串。

我们需要统计形如“一个点到根的链”编号在[l,r]的点的权值和。一个简单的方法是离线在树上DFS，这样我们只有n次插入和很多查询，分块即可做到每次O(1)查询。

若干数和为n，则本质不同的数最多有\sqrt n个

树上选联通块，点分治，dfs序树形依赖背包的做法的核心思想是：我们合并两个DP数组很困难，但是我们可以通过更改顺序，使得操作变成了每次加入一个物品，这就比较方便了。

容易遗忘的算法

2-SAT

决策单调性DP、四边形不等式（遇到一些非常复杂难以使用数据结构的DP）

随机化

交换下标

矩阵乘法（动态DP！）

整除分块

二分

网络流

wqs二分

霍尔定理

遇到复杂的题：打表找规律！！！

倍增！ ST表快速求可重区间询问。

区间询问：离线扫描线！

数据结构

二进制分组

分块！！！