思考流程

IMPORTANT

严格执行！

不会了就赶紧换思路
- 反向思维想过了吗：写下完整的思路句子，然后翻转每个词
- 三种思维方式：推理、构造、猜
- 三种思考方向：情况、性质、方法
- 直觉 ⇐> 分析
- 读题
- 有思路到没有进展，多看这个笔记
- 已经没有思路了，则考虑之前被排除的思路里，有没有想当然的
- 如果会，并且一开始想的是错的然后换了思路，那么不要用任何之前推出来的结论或者方法
- 重新观察较为原始的式子
- 没有进展的时候，多猜
  - 应该花费尽量多的时间证明猜的结论。
  - 证不出来，蒙一下也是好的
- 请往简单了想，删掉一些情况，然后证明这些情况不存在。
- 及时排除不可能的情况，来简化问题
- 遇到实现极其复杂或者超时的情况，不要一直写，试着从各种角度考虑删掉一些设计，尝试化简逻辑
- 分类讨论/先进行某种操作，然后情况会有所变化
  - 不知道进行什么操作，可以模拟前几步
  - 解决完一步之后从头开始重新想
    - 解决完两三步之后情况有所变化（2049E - Broken Queries，825G - Tree Queries）
  - 多个满足条件，先随便解决一个，看看别的条件能不能被推出来（792E - Colored Balls）
转化题目的式子（化简）
- 操作的实际意义是什么
- 观察操作序列本身的性质
- 不要空想，把式子都写下来，图都画出来
- 拆一下括号
- 观察差分、前缀和序列的性质（2006C - Eri and Expanded Sets,GYM105631G - General Checksum Calculation，739C - Alyona and towers）
  - 第 $i$ 位 $\to$ 前/后 $i$ 位
- 如果分析满足某性质的情况太复杂，找到第一个不满足的（最小表示法）
- 恰好 $k$ 个 ⇒ 所有数减去最小值，至多/至少 $k$ 个
- 平均值的意义
  - 平均值是 $m$ ⇒ 每个数减 $m$ ，总和为 $0$
- 顺序的意义
  - 一个数组的顺序可以由 $n - 1$ 对相邻元素的顺序来描述。
- $x^{2}$ 的意义
  - $x^{2} = 1 + 3 + 5 + \dots + (2 x - 1)$
  - $x^{2} = (x 1 + 1 + \dots + 1) \times (x 1 + 1 + \dots + 1)$
- $k + 1 = k + 1$
- 目标有多个不同的式子结合构成，考虑容斥
- 数形结合
  - 两个变量 ⇒ 二维平面
  - 一个数组 ⇒ 二维平面
- 多个相同的东西拼接
  - 展开成两个
  - 只一个首尾处理
- 乱七八糟的数
  - 找通项
- 最小交换次数
  - 随便交换 ⇒ 置换环
  - 相邻交换 ⇒ 逆序对
- 二维问题
  - 观察边界
  - 先确定一维的范围，再确定另一维的，看起来独立但是实际上可以框出矩形范围（2002F1 - Court Blue (Easy Version)）
  - 矩阵/二维图（2034F1 - Khayyam’s Royal Decree (Easy Version)）
  - 右下角一点暴力（2002F1 - Court Blue (Easy Version)）
- 同余 ⇒ 相等，可拆（2023C - C+K+S）
- 计数问题，考虑贡献
- MEX ⇒ 讨论有没有 $0$ （2066B - White Magic）
- 数组长度为 $n$ ，值域为 $m$ ，则出现次数最少的数至多出现 $\frac{n}{m}$ 次（1922F - Replace on Segment）
- 关键点/路径 ⇒ 虚树
- 排列计数
  - 分治（ARC186B - Typical Permutation Descriptor）
  - 从左往右维护状态（1909F1 - Small Permutation Problem (Easy Version)）
  - 二维坐标 $(i, p_{i})$ （1909F2 - Small Permutation Problem (Hard Version)）
- 一对点
  - 异或哈希
  - 栈（1876D - Lexichromatography）
- 容斥：不需要讨论所有的，只除去第一个（AT - Grid 2，P4178 - Tree）
必要条件有哪些
- 操作完之后是什么样（小红的数组操作，771D - Bear and Company）
- 答案/不好弄的必要条件能否从简单的必要条件推出
- 概率问题，可以只关注需要关注的点，求出这种情况下的概率
- 最优问题，获取答案上 / 下界
  - 用两种方法表示某个量，令它们相等
充分条件有哪些
- 假设不必要，那么有没有子条件是必要的
暴力
- 暴搜
  - 暴搜过程中维护信息（1975F - Set）
- 小情况下的暴力解法能否导出更好的性质？
  - 暴搜（算不出来复杂度也没关系）
  - 暴力 DP
- BITSET
- 启发式合并
- 取 LCM
- meet in the middle ：前一半和后一半暴力枚举，然后合并
  - 交叉两组的数据可以使得总的搜索规模减小
- 观察一下比较少的量
贪心
- 可以用反证、递推、调整法等常用思路来证明正确性
- 有一个备用条件时可以反悔贪心
- 不特殊的点也可以设一个为特殊的点
- 情况很多的时候，从最坏的情况出发进行观察
- 及时排除不可能的情况，来简化问题
枚举
- 从大到小（分治）、从小到大、从左到右（1998E2 - Eliminating Balls With Merging (Hard Version)）
- 枚举所有的小情况
- 枚举倍数
- 图论问题计算贡献，枚举点、枚举边
  - 二次贡献：先写出按一种方式计算的贡献，然后根据写出的式子，用另一种方式计算贡献。类似线段树 DP
- 枚举所有不同的量，看哪种复杂度最低
分类讨论（分别解决每种情况）
- 开桶归类，能否证明每个桶之间互不影响？
- 众数是否出现次数超过一半（1943D1 - Counting Is Fun (Easy Version)）
反向思维
- 正着操作 ⇒ 逆过程（2059E1 - Stop Gaming (Easy Version)）
- 找没有出现在当前思路（包括超时的）中的量（线性基 → 不在线性基中的元素，不变量 → 变的量）（959F - Mahmoud and Ehab and yet another xor task，744C - Hongcow Buys a Deck of Cards）
- 过程（移动）是相对的（611F - New Year and Cleaning）
- 添加哪些边 ⇐> 删除哪些边（1994F - Stardew Valley）
- 数填到什么位置 ⇒ 位置拿什么数（1893D - Colorful Constructive）
分治
- 构造题，先考虑当前区间，然后递归子区间
- CDQ 分治
  - 模型：统计合法点对/区间数量
  - 设计函数（不一定是区间），维护（可能多个）分治信息（1982E - Number of k-good subarrays）
  - 转化成二维偏序/三维偏序（848C - Goodbye Souvenir）
- 区间查询 ⇒ 维护区间信息 ⇒ 线段树的区间合并
  - 线段树区间合并也支持修改（739C - Alyona and towers）
离线
- 对问题的查询进行离线
- 如果问题本来不是一堆查询，但是你的算法里有一些查询，可以离线自己想进行的查询
差分
- 区间加法只对差分序列的两个位置产生影响
- 求一段的和可以求两个前缀和之差，就像数位 DP 一样
DP
- DP 思维。多用 DP，多试 DP
- 填表法与刷表法: 往后转移
- 遇到难以转移的情况，就增设状态，这并不代表复杂度更高
  - 把 $k$ 的多少倍 / 模 $k$ 的值放进状态里
  - 带环的 DP，设未知数
- 二维 DP 在滚动数组之后，会完全变成一维 DP
- 尤其是博弈论和概率论。能不能直接设 $d p_{i}$ 表示某个量 $n = i$ 时的结果然后暴力转移？？
- DP 思维。后面的是否与前面的差别较小？
  - 可不可以维护一个东西，之后发生的变化可以对它进行区间修改之类的？
- 直观 DP。 DP 值表示的意义直接通到答案。
- 状态机：有特殊情况的时候多设几个状态
- 区间 DP
- 图上 DP ：一般用 Dijkstra 或者 BFS 实现
  - Dijkstra 的实质也是 DP
  - Floyd？？
  - 树形背包的复杂度
- 计数问题，可以先取定一个方案，然后把它泛化到只跟值、下标之类的量有关，从而构造 DP
- 斜率优化
- Slope Trick：观察要维护的数组能否用一些直线表示。
- 简化转移
  - 如果有的量之后全都会算进去（而不是可能只有一部分算进去），那么就不用考虑
  - 组合数优化
  - 状压，假设转移顺序就是添加顺序
- 前缀 DP：
  - 一般 DP 设前 $i$ 个元素有什么性质的代价，但可以设满足什么性质的最小前缀长度
  - 可以设 $d p_{i}$ 表示结果序列的第 $i$ 个前缀具有的性质的值（操作完之后是什么样？）
    - $d p_{i}$ 表示凑出长度为 $i$ 的前缀的方案数（756D - Bacterial Melee）
- 矩阵优化 DP：如果状态机 DP 只取决于当前位置的值和上个位置的 DP 值，考虑把转移方程表示成（广义）矩阵乘法
- DP + 计数（期望） ⇒ DP 套 DP
  - LIS/LCS 计数（P4484 - [BJWC2018] 最长上升子序列）
- 考虑交换下标和值能否使得复杂度更低（1922F - Replace on Segment）
随机化
- 反向：先发现一个好的性质，然后证明随机选一些点满足这个性质的概率很大
- 正向：想一想有没有什么性质，有很多点（比如超过一半？）都满足
- 不会算正确概率的也可以随机
Hashing 判相等
- 异或哈希
- 最短路计数，用来确定是否是最短路的必经点（567E - President and Roads）
- 哈希存（不一定合法）括号序列的前缀状态
括号序列
- 栈（不一定合法也行）
- 括号树
- 折线图
概率
- 可以设概率是多少，然后根据概率不变来列式子
- 生成函数（1948F - Rare Coins）
归纳
- 假设已经构造出一组符合条件的方案。接下来应该怎么做？
- 先解决规模小的子问题
  - 自顶向下，只需要证明边界情况以及可以转移
位运算
- 拆位
- 线性基
- MEX ⇒ XOR
建图
- dfs生成树
- 欧拉回路（把一般图转化成欧拉回路的方法，建立虚点，向所有奇顶点连边）
- 拆点
- 树上的构造/贪心题
  - 从叶子开始删/配对
    - 霍夫曼树：用堆，每次删除权值最小的叶子
  - 直径遍历的套路
- 矩阵和图的关系
  - 对称矩阵是邻接矩阵（632F - Magic Matrix）
  - 看到矩阵想到把每一行建一个点，每一列建一个点，然后每个格子就是连边了
- 二分图可以染色
- 多条链 ⇒ 虚树复杂度（1929E - Sasha and the Happy Tree Cutting）
- 路径查询 ⇒ 树上莫队，倍增，点分治（1902F - Trees and XOR Queries Again）
网络流
- 一切都可能是网络流
- $1 e 4$ 也可以正解是网络流
质因数
- 枚举gcd
- 质因子的个数尽量多 ⇒ 质因子的值域很小
- 质因子的种类尽量多 ⇒ 质因子的个数很少
- 质因子的种类很少
- 最小公倍数可能很小
二分查找 / 二分答案
- 注意到 $2^{n}$ 这类条件，可以按位二分
- 双指针优化二分
- 凸函数的和是凸函数
根号算法
- 大情况和小情况用完全不同的策略
- 把大情况用小情况解决
- 一般分块：构建长度至少为 $n$ 的连续段
- 看见题目中/自己推出的含有向上取整、向下取整的式子，或者含有 $mod$ 的式子，考虑数论分块
- 明确区分根号分治和分块是两个不同的算法
- 总和为 $O (n)$ ，则不同的取值只有 $O (n)$ 种（666C - Codeword）
莫队的思路，但是不一定离线
鸽笼原理
- 观察题目中是否有重复的量。
二选一问题
- 并查集
- 2-sat
多个操作同步化，比如有两种可能产生不同步的操作，可以按照共同的某个时刻来分段
猜
- 猜的结论可能是对的！
- 直接贪心就是答案（1893D - Colorful Constructive）
  - 放弃之前，试一试
- 小情况可以覆盖所有情况
  - 不用多次操作，永远只需要一两次操作（Dial 最短路）
  - 如果不能永远只需要一两次操作，也许只需要三四次操作（2049E - Broken Queries）
  - 通用方法不正确，可能对于 $n$ 较小的时候（比如为 $3$ 或者 $4$ 或者 $5$ ）需要额外讨论（ARC192B - Fennec VS. Snuke 2）
- 简单方法可以解决一些特殊情况，看看剩下的情况是不是才更特殊
  - 从情况出发得到方法
  - 从（构造）方法出发得到能解决的情况
- 答案不太大
  - 操作次数有限，直接暴力
- 奇偶性归约
- 抽屉原理
- 单调栈
  - 后面和前面的所有东西有关时，考虑单调栈
  - 可以操作它左边满足某个性质的元素 ⇒ 尝试单调栈找到左边第一个不满足的
- 构造题
  - 打表
  - 简单贪心
- 转换成其他进制
字符串题
- KMP 在线，Z 函数离线
期望的计算方法
- 按定义，求每个值的概率
- 概率 DP ，设当前状态通到答案的期望
  - 高斯消元
  - 设一个未知数表示初始状态的值，然后消掉转移过程的环
- 贡献法
- 等概率选取 ⇒ 方案计数（2034F1 - Khayyam’s Royal Decree (Easy Version)，P4484 - [BJWC2018] 最长上升子序列）

对于想法的每个点，进一步思考
图不要抽象，把图具体画出来
复杂度不要想当然，否则一定会错过正解
- 严格证明复杂度再排除，求出循环次数的和式
- 证明复杂度可以用贡献法
- $lo g (x) \approx \sum_{i} [2^{i} < x]$ （根号分治优化子集和）
区间 DP 的常数大概是 $\frac{1}{4}$

注意事项

LCM 别忘了开 long long
$1$ 不是质数
组合数如果涉及浮点数，可以用对数算防止爆精度
多项式快速幂时间复杂度是 $O (n lo g n)$

Subscript

探索

备忘

思考流程

注意事项

关系图谱

目录

反向链接