trick 整理
始于 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 ,然后凑一下,大概率能凑出来,不然这题做不了。