Trick 整理

发表于 分类于

对于经常出现又难以独立发现的思维中间产物，如果系统性不够被称为知识，我们会称之为技巧、模型，或者”套路“。 ——zx2003

该笔记收录了一些，在写题过程中出现过的 trick。出现次数不够频繁而不能归入一般化的思维。但是又真切的存在于自身的神经网络中。

解释思维的方法，无非就是，要么分析性质，要么根据经验，要么灵光一闪吧。本文章旨在记录一些比较偏僻的经验。

通用

  1. 关注不变量

  2. 能离线的要离线

  3. 跳出动态过程（什么样的状态下），研究静态结构（存在什么）：双栈序列

  4. 构造不出答案时，考虑维护答案。

  5. 考虑不同主体的贡献。

  6. 分类讨论（分治）

  7. 正序贪心难做，考虑倒序贪心（菜肴制作，ICPC睡觉）

  8. 先考虑下限，然后证明一定能到达下限。（构造单峰）

  9. 将决策顺序看作序列。（移动蓝球红球）

  10. 拆分贡献的时候，不要使用“事件触发”型贡献，把每个点剥离开来。（分段 mex 求最大和）

  11. 如果操作单点困难，考虑按照值域批次处理（构造单峰）。

  12. 想象状态空间，状态与状态的转移。

  13. 失败了不要慌张，思考最多失败多少次（最大三角形周长）

    DP

  14. 具有阶段性考虑 DP。

  15. 决策集合具有单调增减性，可以优化。

  16. 数位DP，用mask表示0~9中哪些数出现过

  17. 小区间变到大区间——>区间DP。

  18. 计数DP 转移时考虑合法集合的具体样子。

  19. 状压 dp 转移时，如果顺序不影响，可以只考虑 lowbit。

  20. 双字符串想 dp

  21. 代价存在某种不对称性，即在前面用和在后面用，代价不一样。考虑贪心，正反dp。

  22. 证明 DP 正确性：

    1. 收敛形dp：归纳法做
    2. 刻画答案的样貌

  23. 图上游走考虑矩阵加速 DP。

  24. 定义状态时人为添加约束，前提是约束与题目大约束不冲突。（邦邦的大合唱站队）

  25. 单调栈退栈时做转移（CF1407D 跳跃大楼）

  26. “质变点 + 不变段”的 DP：使用数学方法压缩不变段（添加逆序对 k）

  27. 子序列本质上是一种顺序约束，当顺序与题目无关时，就不需要考虑子序列的约束了（分段 mex 求最大总和）

  28. 正反 DP 枚举断点（f(A)表示连通块数量）

  29. 序列个数计数，考虑 DP。

  30. 真正会产生不同序列的位置，是不能被前面的序列所唯一确定的。(要/不要填mex的序列计数)

  31. 如果记录具体值行不通，尝试记录数量(要/不要填mex的序列计数)。

  32. 背包问题，涉及到多少种花费/价值，就往维度上放多少种。

  33. 排列计数 DP，如果约束只关注相对大小（最大值，大于），则状态也只考虑相对大小。

图论

  1. 虚点，超级源点，超级汇点
  2. 点的状态很少考虑分层图
  3. 染色：找出主体的不同状态，用边表示状态的异同。
  4. 二分图完美匹配 ＆ 替换边：交替环
  5. DAG 从入度为 0 的点出发 dfs 能到达图上所有点。
  6. 构造序列，交替出现，构造二分图跑欧拉路径。
  7. 特殊图：
    1. 树形结构
    2. 完全图：输入量很少
  8. 连通性：并查集、搜索树
  9. 可行性：并查集、二分图染色
  10. 有向图：缩点
  11. topo 最小顺序：正着原图字典序 or 反着反图字典序
  12. 瓶颈路考虑 MST。
  13. 删边，离线做并查集加边。

树

  1. 子树查询考虑 dfs 序
  2. MST：
    1. 一般使用 kruskal
    2. 完全图、稠密图、通过公式生成边权，使用 Prim

图论建模

  1. 图论建模的时候，如果发现把 x 当作点，y 当作边难做，可以尝试把 y 当作点，x 当作边。

  2. 什么时候考虑图论建模？

    1. 二元关键字：数对 (a,b)

      1. 将 a、b 看作两个点，(a,b) 表示这两个点之间有边相连（CF2110E、单词接龙）
      2. 将 (a,b) 本身看作一个点

    2. 出现与图论结构相似的代数结构时考虑建模：

      1. 树的结构：只有一个父亲 —> 每个点只能被淘汰一次（选两个删一个）；n - 1 条边 —> n - 1 个二元关系
      2. 边权结构：f(u) = f(v) + w —> 状态之间的转移代价
      3. 最短路结构：三角不等式
      4. 二分图结构：两种选择、奇偶性、见 2 思二分图
      5. 并查集：同一类、一种关系（食物链）

    3. 偏序关系：大于小于、放入、移动、嵌套

  3. 排列建图成多个不交环。

  4. 保留关键点优化建图

  5. 同余最短路：本质是通过取模来缩小状态空间，或者约束本身带有取模性质。关键词：无限次。常见形式：d[i]：mod x = i 的最小数（牛场围栏/类货币系统/跳楼机）

树上问题

  1. 算贡献，将贡献拆到 边 or 点 上
  2. 匹配问题，两个贪心方向：
    1. 尽量在子树内完成匹配
    2. 尽量不要与子树内的匹配

区间相关

经典例题

看到区间问题，就想到排序！！！

  1. 按右端点排序：

    1. 区间最少选点：CSP-S 2024 T2，维护上一个点的位置
    2. 最大不相交区间：会议安排，维护上一个区间的右端点

  2. 按左端点排序：

    1. 区间最少分组：廊桥分配，维护每个组的右端点
    2. 最少区间覆盖：维护 nxt 数组，下一个跳到的位置。可以不是覆盖成一个区间，多个点也可以：P4064 加法
    3. 区间合并：将相交的区间合并。维护当前区间。

以上问题都可以倍增优化。

经典形式

  1. 区间计数/最优区间：枚举端点，另一端考虑双指针、二分
  2. 区间修改：将操作映射到差分数组上（konbi 01序列问题）

线段树

  1. 考虑节点与节点、节点与标签、标签与标签之间的合并。
  2. 考虑节点与节点的合并时，分类讨论至少两种情况，答案落在左/右区间，答案跨越左右区间。
  3. 遇到难维护的操作，考虑操作最多能进行多少次。区间每个数取模/开方，最多进行 log 次。
  4. 若维护的信息没做过，有两种方法：
    • 拆分成好维护的
    • 直接研究操作影响

二分答案

  1. 处理 子段和/平均值/01分数规划 问题时要想到二分答案
  2. 最大值最小/最小值最大 考虑二分答案
  3. 单调性 考虑二分答案
  4. 寻找第 k 大，考虑二分答案：2026.8.19深圳模拟赛 T1

数学

  1. 值域取模裂成两类小值域。
  2. 有效取模最多进行 log 次
  3. 多重集排列数：n! / （相同字符出现次数! 之积）
  4. 整除 = 取模后为 0

数形结合

  1. 数对，不同属性之间比较：区间相交/并
  2. 数对，相同属性之间比较：二维平面

贪心

临项交换

交换论证

S1：断言存在一个最优解，符合某种结构。
S2：找到一个任意的最优解，找到它与结构矛盾的地方，调整。
S3：若调整后不劣，且调整的次数有限，证明成立。

解集是决策的集合。
常见技巧：分组、找到第一个不满足的地方

  1. 批量按值层处理，而非按位置拆贡献：（假山拍照，构造单峰）

反悔贪心

一种思想，非常灵活。通常由三个部分组成：

  • 历史决策集合
  • 替换时机（发现更优/不满足限制）
  • 替换规则（替换的代价/价值是多少）

常见特征是，有一个很自然很平凡的贪心，会带来一些问题，此时不要放弃，尝试反悔贪心来调整。思维的出发点是朴素贪心。
常见应用：股票买卖、选了它就不能选它的互斥选择、分队

mex

  1. 序列拆分，求最大 mex 总和：累加出现次数的前缀最小值。
  2. 刻画mex时，想象一个格子条，mex就是这个格子条里，最左侧的，未标记的格子。

序列

  1. 构造一个严格增序列 {a1,a2…ai}，等价于构造一个不严格增序列 a{a1,a2+1,…ai+(i-1)}.
  2. 将操作顺序视作序列。
  3. 严格增 or 不严格增的约束，可以通过操作差分序列来解耦。
  4. 生成任意序列，意味着可以改变序列的每一项而不影响其他项（konbi 01序列问题）

杂项

  1. 股票买卖经典转化之，“i 买 k 卖 = i 买 j 卖 j 买 k 卖”。

  2. 括号序列经典性质之，“一个括号序列合法，当且仅当在任何时刻，左括号数量 >= 右括号数量，且整体数量相等”

  3. 拼数：按 A+B 和 B+A 的大小排序，可以证明构成偏序

  4. 字典序相关构造：枚举每一位，考虑这一位填什么（逆序对为 x 的字典序第 k 小排列）

  5. 字典序考虑贪心。

  6. 对角线相关：研究 x+y，x-y 的奇偶性、不变性。（V 填色）

    1. x-y 不变：处于同一主对角线上（充要）
    2. x+y 不变：处于同一副对角线上（充要）
    3. V 字型上 x-y / x+y 的奇偶性相同

  7. 满二叉：叶子交换到最左边所需要的边数，等价于它编号中 1 的个数（中/后缀最小字典序）