一些常见套路

· · 个人记录

  1. 二分：
    • maximize minimum 或者 minimize maximum 优先考虑二分
    • 二分性，答案取值范围的一段前缀/后缀合法，或者有单调性
  2. 计数 DP：
    • 考虑所谓的“不可划分的整体”，围绕这个整体划分子问题
      • 例如 CF888F，就是将两个直接相连的点中间的所有点作为整体
  3. 前面对后面有影响（即，正着做有后效性）？
    • 考虑倒着做
    • 例如 CSP-S 2020 T4，就是倒着考虑每一条蛇到目前的最终局面时是否还健在，如果是，则继续；否则，将目前最终局面改成它做决策时的局面
  4. 猜出了一个贪心策略？
    • 从最优性（是否可能存在一个更优的方案）和可行性（是否可以按照策略构造出一个最优方案）证明
  5. 相邻交换得到了一个含 \max/\min 的式子？
    • 分类讨论所有可能的大小关系，通过推导与/或关系来得到一个确定的全序关系
  6. 怎么搞都要 2^n 枚举子集？
    • 这个子集也许有性质，例如一定是连续区间
  7. 期望 dp？
    • 倒着设计状态和转移，已知推未知
  8. 所有子集的子集
    • 复杂度不是 O(2^n\times 2^n)，是 O(3^n)
  9. kth 相关
    • 二分答案转换成 0/1 最大子段和等问题
  10. 中位数相关
    • 二分答案转换成 -1/1 最大子段和等问题
  11. 图论题中有一个数非常小
    • 考虑利用它拆点
  12. 对所有排列考虑 / 将原序列重排
    • 原来的顺序没关系了，可以排序等等方式处理
  13. V - E 容斥
    • 对于每个点统计一遍贡献，再对每一个边统计一下贡献，两者相减后所有连通块的贡献只被算 1 次
    • 对于树上连通块交的相关计数很有用
  14. 重心只能在以根为链头的重链上
  15. 两点集直径在两点集各自的直径的 4 个端点中取一对点，点集中距离一个点最远的点一定是点集的直径的两个端点之一。
  16. 多个价值维度均合并为一项之后互相干涉并产生价值，可以把合并出的一项作为坐标建系，例如 P5540。
  17. “某些元素在某时刻消失”倒流变成“某些元素在某时刻出现”有时很关键。
  18. 竞赛图缩点后是一条链
  19. 不仅区间加/减可以考虑差分，矩形加/减也可以。
  20. 子段和 → 整体 - 前缀 - 后缀（Topcoder 14719）
  21. 后面覆盖前面 → 倒过来 → 只和第一次有关系
  23. 处理平方数的一种 hash：维护一个完全异或性函数，对于所有质数 p，f(p) 取任意值。
  24. 数据范围大也可以考虑最大流，特殊图最大流不好求可以转特殊图最小割，有一些可以用数据结构维护。
  25. DP 被卡空间了立刻考虑调换维度之后滚动。
  26. 奇怪的不能 FMT/FWT 的卷积形式可以考虑类似 karatsuba 的方式做到 3^n。
  27. 和时间有关的游走问题考虑建时间轴。（按理说这不是个很直接的暴力想法吗……为啥我想不到啊/kk）
  29. 根节点复制 k 份 -> 孩子独立
  30. 本质不同border形态数量是亚指数级别
  31. 离线数子区间：枚举询问右端点，线段树维护每个点作为目前扫到的多少个子区间的左端点
  32. 遇到 mex 的时候可以往二进制上想
  33. dfs 序背包：维护 dfs 序在当前点之前的信息，每次加入当前点信息并依次递归子树更新（EINOIP2022D1T4）
  34. 静态区间查询只能往一个方向加东西的时候考虑对称性（UNR#6 D1T3）

构造

  1. 差分约束/拓扑排序/高斯消元（省选2021 d1t2，某个 gym 题，CF1635E）
  2. 格雷码构造原理（某个洛谷月赛 C，某个联测 T1）
  3. 打表找规律（P3599）
  4. 观察/模拟样例（P5441，P8103）
  5. 强化/转化限制（CF1641B 转化为排序，P8282 改为最优化一个东西）
  6. 从特殊情况出发（CF1583F）
  7. 增量法（完全图构造先红后蓝哈密顿路那个题）

猜结论/性质

  1. 交 换 差 分/前缀和
  2. max/min 单调栈 -> 笛卡尔树，笛卡尔树上左链/右链一般比较有用
  3. 猜决策单调性（artistic partition）
  4. 调整/直觉（CF1442D 调整最后一个元素的位置 -> 只有一个不顶到头）
  5. 构造性的猜法（构造答案，部分依赖打表）
  6. 最优化问题简化限制：
    1. 它不合法，但是它同时不优于至少一个合法解，直接算进来也行（很多，比较有代表性的是 NOIP2017 宝藏）
    2. 分析最优性得到每一次选取的可能解集要么全部合法要么全部不合法，且可以快速判断（JOISC 2022 D2T3）

贪心

参考 https://www.luogu.com.cn/paste/8hnex65m

  1. 相邻交换
    • 树上相邻交换：
      • 先和序列上一样做。
      • 由于相邻交换本身的特性，其所针对的变换通常可以合并。
      • 如果儿子排在父亲前面，合并儿子和父亲。
      • 全部合并结束后按顺序选。
  2. 超级钢琴：答案候选集合中选出最大，然后分裂集合
  3. 反悔贪心（P2209）
  4. 利用贪心想法简化问题形式（CF1632D，转化为序列切分然后 DP）
  5. 限制/影响最小化的思想（CF1404C：删后面不影响前面 -> 每时刻删最后一个；U202373：前面影响的限制更多 -> 优先放后面）
  6. 差分相关有一些需要把操作 2 个位置转化为 1 个，但是有时候也需要把操作 1 个位置转化为 2 个
  7. 可能贪心找不到最优解，但是能用贪心把答案用一个很小的范围界住/把一个比较大的范围内的答案都确定为同一个值，然后用一些更暴力的东西（例如 dp）（某个联测 T2 的那个神秘 w\leq 300,v=1,C=10^{18} 多重背包）

ds

网络流

最短路/mst

dp

计数

数论

欢迎补充……