trick 整理

Others · 2023-10-19 20:43:13 · 个人记录

始于 2023.10.19

前言：再不记记这东西就寄寄了。

• 数联通块数量可以选一个关键点，然后数关键点的数量。

• 数联通块数量可以数最小生成森林的边的数量以及点的数量。

• 中序遍历 99% 外面有递归（分治结构）。

• 区间做与原来值无关的操作一般是差分。

• 可以离线直接想扫描线只赚不亏。

• 如果是对括号序列计数的话，可以考虑分成多个块，来递推。

• 求路径可以分段按不同的策略搞。

• 数连通块可以用欧拉定理。

• 数矩形可以数全局 2\times 2 的小方格里有 1 个或 3 个符合条件的格子的小方格数量

• 构造联通块的时候，可以从重心或生成树的中心开始找。

• 状压状态太多的时候可以考虑不状压，直接暴力存状态，然后做类似于 hash 之类的东西。

• 线段树线段长度总数很少。

• 当你需要暴力重构区间信息时且区间下标变化量线性，可以从中点分开维护，这样就可以线性暴力了。

• 可以用双栈来做插入两端插入删除元素且维护不可删信息的操作。

• 树上可以确定父子关系来转化相邻点关系。

• 对于构造染 4 种颜色，可以先二染色，然后相同染色的拿出来再二染色。

• 求绝对值最优的时候可以拆成一个正一个负并且规定只取一个，可以发现直接取最优的就行了。

• 整体二分可以不作为求解工具，有时候可以作为预处理工具

--“WD的地图”

• 遇到计数且去重的题可以猜没有重复的。

• 正常 dp 的第二维很大的时候可以考虑交换两维，然后矩快。

--“1 2 3 4 ...”

• 如果一道题一点不会，不妨想想 dp。

• 如果树形 dp 遇到对父亲的限制，不妨想想当前先不管对父亲的限制，转移父亲的时候再管。

• 遇到自变量连续求和的可以考虑差分。

• fail 树不好维护的时候就去维护 border 集合

• dp 方案数和直接 dp 期望的式子本质相同，但是期望带的那一坨分母可能会使式子更好处理，也可能会出现莫名其妙的逆元，看情况处理。

• 所有点都被操作的期望步数=E(\max\{t_i\})=\sum(-1)^{|T|-|S|}E(\min\{t_i\})=每个点期望被操作多少次的和

• dp 顺序与初值方向不符时，例如 dp_0=0,dp_i=fvck(dp_i+1,dp_i+2,...,dp_n)，可以令 f_i=dp_n-dp_i，然后凑一下，大概率能凑出来，不然这题做不了。