各种科技与套路的小本本

chen_hx · 2021-10-28 16:22:49 · 个人记录

• 如果你要算所有点的贡献，但是点之间具有对称性（比如两个点只是编号不同），那么你可以算一个点的贡献，然后直接乘以点的个数
  [ABC284G] Only Once

• 树上距离某个点最远的点一定是直径的两个端点之一

• 一些特殊的断环成链的位置可以带来一些 ex性质
2022-11-15联测 rainbow

• 对于 LIS 的问题可以往 Dilworth定理 上想

• 想题真的可以仔细往子问题上想：（限制相同，规模更小）

• 对于给树上从某个节点一直向上跳所构成的路径加一个等差数列可以考虑使用倍增维护

• 树上对于每个点计算别的点对他的贡献，如果贡献与两点距离有关，那么可以考虑点分治

• 整体二分或者决策单调性分治的时候可以考虑使用类似于莫队的方法可以去掉数据结构的 \log_2

• 二维数点具有决策单调性

• 两棵树上弄来弄去的可以考虑参考cdq分治一样，先对第一棵树分治，然后对第二棵树统计

• 当遇到奇怪期望的式子（尤其是什么期望最大值）的时候，往往都是我们如果能通过不断调整来模拟求解，就可以适当考虑结果的形式，如凸包等
  P5155 [USACO18DEC]Balance Beam P

• 当需要统计的状态需要 dp 求出来的时候，就大概率需要 dp套dp
P4590 [TJOI2018]游园会

• 当遇到需要统计有多少种情况是合法的时候先考虑给定一种情况能否判断其合法，然后通过其判定合法的方法来计数，一般就可以直接判定/生成，否则可以考虑dp套dp，记住判定合法的dp状态即可

• 看到取模直接想环

• 树上点对统计除了大力启发式合并，还可以点分治
  CF715C Digit Tree

• 遇到 一大坨 且限制 尽管大力容斥

• 带权统计考虑计算单点贡献

• 【异或不等科技】
  CF1720D2 Xor-Subsequence

• 当遇到有的算法的若干个部分的复杂度很不均衡，那么就想办法平衡复杂度
  CF1185G2 Playlist for Polycarp (hard version)

• 如果元素的贡献与区间最小最大值有关，那么考虑使用 min-max分治 ，使每个元素在其左右端点不在同一块的地方被统计，min-max分治 不仅可以计数，也可以求最优化
  P3592 [POI2015] MYJ

• 询问区间的子区间的问题基本都是线段树维护历史版本或者莫队

• K-nim 结论：

  先手必胜条件：存在某一位的 1 的个数不能被 k+1 整除

• 一旦遇到动态图直接线段树分治+可撤销并查集

• 在一个二维平面中如果将距离为 整数D 的整点连边，那么一定能构成一个二分图

• 当无法直接使用组合数或者斯特林数直接优化的时候，可以适当考虑组合意义比如：平方可以认为是在某一个范围里头顺序相关选择两个元素等
  AT2371 [AGC013E] Placing Squares
P1758 [NOI2009] 管道取珠
[UER #6] 逃跑

• 两个数异或起来的 highbit 是同一棵在 01trie 的 lca

• 序列划分的新结论：合法的划分段数数是连续的

• \sum C^{2i+1}_{n} = \sum C^{2 i}_{n} = 2^{n-1}

• 一个单调递增的序列的差分数组至多有根号值域种不同的值

• 多把未知问题归纳为已知问题
  CF1665E MinimizOR —— 暴力trie树做法

• 当贪心做决策的工作比较难完成的时候不妨考虑倒过来做，然后就可以把一些选择性的决策变成必要性的决策。类似地，在做dp决策的时候如果正序状态难以描述那么可以将其变成倒序
  CF505E Mr. Kitayuta vs. Bamboos

• 当直接计数很难实现的时候可以考虑合并结果，统计贡献

• 要求给点分配权值，给出若干个限制要求某几个点之和不超过某个数是网络流模型

• DP具有无后效性的体现：构成DP的每一步决策都只与当前的状态有关，不与前后有关，就比如说给一堆限制，然后可以将这堆限制分类，然后每一类DP，保证在符合之前所有类的限制的情况下满足当前这一类的限制，可以看做是一种分部处理“且”限制的手段
  P5369 [PKUSC2018]最大前缀和

• 考虑生成一个排列的办法：状压目前使用了多少位，枚举下一步拓展谁

• 在一个图中选择一个点集使得每个边都恰好被一个端点覆盖，那么这是一个二分图染色问题

• 一个二分图，性质就是不存在一个大小是奇数的环，把一个不是二分图的图变成二分图的办法就是把所有的奇环都断掉

• 一个无向图中的 dfs 生成树只有返祖边，没有横叉边；而且无向图的简单环都在 dfs 树上体现为一条返祖边

• 树形结构很常见，可以用来dp
  SP3734 PERIODNI - Periodni

• 对于小球撞来撞去还反弹的题目有一下基本结论：
  每个小球的相对位置是不会改变的
如果速度相同，相撞等价于直接传过去，而交换编号
CF652F Ants on a Circle

• 对于树上任意非祖先两点的都会对其lca产生限制，就直接按照dfs下去即可，设计状态的时候直接就是f[i]表示以i为根的子树中，本身已经满足限制的状态，合并的时候考虑不同子树对于根的限制即可

• 最优化dp 转移的决策（转移路径）不一定要存在直接转移，只需要保证存在最优（复合）路径就够了，就是冗余转移优化
  P4762 [CERC2014]Virus synthesis

• 坐标上的点可以通过以原点为中心旋转45度来简化限制

• 如果若干个集合两两之间的关系要么包含要么不交，那么集合的包含关系可以构成一棵树 CF494C Helping People
P8252 [NOI Online 2022 提高组] 讨论 【罗神的集合划分树】

• 不断跳 kmp[i] 的过程本质上就是在遍历等于前缀的后缀

• 计数题要考虑如何把问题分组，做到不重不漏，比如可以考虑以最大编号或者最原始祖先来区分等等，就是类似于至少=恰好\times至少这种，反正选出来的代表要具有 唯一代表性 ，即可以唯一代表一类情况，且分类重不漏
  P7105 「C.E.L.U-01」门禁 【差一点想出来的题】
CF512D Fox And Travelling【自己想出来的题】

• 权值是乘在一起然后开根的，可以把开根看做在指数上除，然后就变成分数规划问题

• 多发现题目的性质，从而下手

• dp 的有效状态实际上是很少的，可以利用上
  CF1584F Strange LCS

• 有时题目给的限制很不直观，可以思考一下违背限制时或者符合限制时的情况，将其直观化

• 对一个单调不减的序列可以通过ai=ai+i变换成严格单调递增的序列

• 对于序列的操作可以通过对序列进行变换来简化
  [ARC120]C 把 ai 变成 ai-(n-i+1) ，这样swap就变成在变换后的数组上直接swap

• 注意把问题转换成模型

• 注意把一些普通结论转换成二级结论

• 要善于通过更改顺序来取消限制

• 如果一些情况使得某一位非常小，某一维非常大（只能接受log），那么可以考虑矩阵乘法

• 定长度区间反转类的问题，可以考虑构造这个长度的剩余系，把下标(i%len)的值相同的归为一类， 这样每次区间反转，剩余系的每个元素刚刚好被多操作一次，奇偶性是相同的！ CF1630D Flipping Range

• 01背包的合并具有决策单调性

• 有些题目不能完全预处理，那么就可以先预处理出能预处理的，然后把不能直接预处理出来的用已经预处理的算出来，差不多就是部分预处理 P4133 [BJOI2012]最多的方案

• dp 转移可以通过更改顺序来消除一些限制

• 合理地在树上使用一些数据结构（dfn序是好东西）
  CF1110F Nearest Leaf

• 多用μ少用φ

• 矩阵快速幂符合欧拉定理

• 计数类问题考虑加乘法原理 emiya家的饭↑

• 定区间询问考虑差分

• 当 i,j 取遍 1 ~ n 时, gcd(i,j) 才具有连续性

• 相邻交换想逆序对（交换一次减少一个逆序对） P1966 [NOIP2013 提高组] 火柴排队

• 位运算可以考虑拆位（毕竟才log_2n位嘛）

• 异或可以考虑trie树

• 若限制两个元素相同，可以考虑使用并查集，要求集内元素都相等，状态过多考虑倍增（拆位） P3295

• 简化DP状态很重要！！
  P5322 [BJOI2019]排兵布阵

• 期望dp强调期望的阶段性，即把期望看成状态来推下一个期望，用期望更新期望
  比如绿豆蛙

• 在做矩阵乘法定义矩阵的时候只需考虑往下一维转移的方法，结合时的合法性本身由矩阵乘法决定而不由状态转移方程决定

• 背包问题决策具有无向性
  P4095[HEOI2013]Eden 的新背包问题

  正着做一次，倒着做一次，之后因为无向性就可以把正着做和倒着做的结果合并！！

• 背包问题中交换物品的顺序对结果不影响
  P4141 消失之物

• 是否转边为点，考虑转移的限制条件

• 生成函数的每个因式的构造取决于这个状态的选择，有点类似于分组背包，在同一因式（同一状态）中多选一，并且不同的状态之间要求相互独立，同一状态内不同的选择要求相互独立，独立的选择之间用加法连接

• 通过差分把区间问题转换成点的问题

• 因为E(x+y)=E(x)+E(y)，所以计算目标状态的期望可以考虑把目标状态拆开算期望然后求和
  CF280C Game on Tree

  其实可以考虑每个点的贡献，每个点会在自己祖先没染色的时候产生贡献 ，考虑求出每个点的贡献后加起来

• 思考序列中加入元素的顺序来看看能不能套到经典dp上

P3205 [HNOI2010]合唱队 : 思考人进队的顺序然后套到区间dp

• 对于要求元素不重复的dp，设计状态时可以考虑一个一个的插入元素，过程类似背包

• 对于字符串中的交换字符这类问题，可以对结果字符串dp，求出结果字符串或者统计交换的代价

2021.10.7成都外校联测 T2 s

• 把dp转移需要的条件写进dp状态里

• 对于斜率优化dp而言，在没有证明严格单调 前一定要特判X(i)=X(que[tail])的情况

• 要求两个限制同时成立可以把这两个限制压成一个限制对，然后转换成一个限制，多个限制同理:

  ch_1 = ch_2 && ch_3=ch_4 <-> (ch_1,ch_3) == (ch_2,ch_4)

• 计数dp在设计状态的过程其实是在把情况分类的过程，要注意分类的情况之间相互不包含或重叠，以免在统计时把部分情况算重

• 多考虑条件是否必要或充分
  CF1494E A-Z Graph

• 对于dp中的序列问题，如果每个元素的贡献只与其相对的大小关系有关，那么可以把元素换成康托序，同时一个排列与康托序是一一对应的

• 对于树上的问题，如果每个节点的贡献只与其相对先后遍历顺序有关，那么可以转换成dfn序
  CF1062E Company

• 某些限制可以被压缩，比如要求禁止出现奇数长度的回文串可以压缩成禁止出现长度为三的回文串（aba），可以通过转换限制来做题

• 在让gcd最大的问题里的一种dp的阶段性：把最大的质数作为阶段来拓展

• 多个模式串匹配且长度不定的dp可以把模式串放到AC自动机上，接着dp状态就转变成匹配到AC自动机上的某个点时的状态

• 有些题目中“等待”操做可以考虑提前到开头