小技巧Trick-思路-个人总结

### 难以想到的算法： 分治！ 随机化！ ### 遇到不会的判断条件，尝试转化它，写出来成立的充要条件，考虑优化 ## 求解概率、期望的几个常用技巧 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)$ $Q(x)/(1-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表快速求可重区间询问。 区间询问：离线扫描线！ # 数据结构 二进制分组 **分块！！！**