La Finale

LSC666 · 2025-11-23 20:35:32 · 个人记录

考试策略

多虑怎么办：平和对待。

拔头发怎么办：着眼当下。

想唱歌怎么办：识时务。

T1 T2（2.5h）

• 脑子要转得快，代码要打得快，要有紧迫感。

• 不要卡在玩样例里出不来，没有主动思考，仅凭找规律是做不出来的，一定是先有一个想法再去玩样例验证。

• 想不到思路就先跳题，打岔一下再回来想，可能会有新思路。

• 想到思路后，先把程序主要流程写下来，评估复杂度；然后把程序拆成几个步骤，分别思考怎么处理出来。最后写代码。一定先把思路写好再动键盘。计算时间复杂度一定要严谨！注意 1e6 是卡双 log 的。

• 做法基本正确的题，不把复杂度优化到最优，会非常可惜，丢掉的分在之后很难再骗到。想思路的时候，要有想正解的决心，尽量优化到最优，不要想着糊弄过去。记住，正解一定是复杂度严格正确的。

• 写完一题的代码并通过样例后，最好再评估一下复杂度！注意多测的 memset 会不会增加复杂度！

• 对于一些优化思路，需要敢于证明。

T3 T4（2h）

• 把它看成是分值少一点的绿题，不要畏难，把该拿的部分分都拿到，CCF 给的部分分会很细。

• 想出初步解法之后，要看一看特殊性质。

• 对于只有一个测试点的特殊性质，一般是很简单的，尝试想一想。

• 最后留至少 10 min 检查。

Problem

• 贪心，不要想代码实现难度，只要是对的做法就去实现。

• 贪心题，一开始要多想几种思路/策略，先广度再深度。

• 看到数据量小的题目，直接考虑 DP，凭感觉设计状态，很可能就想到解法了。

• 有一些数轴上的区间包含相交关系的问题，其实并不一定有固定的模型，不要把它想得过于简单，要打开思路。

• 对于参数比较多的 DP：不要畏难，可能有多种状态设计方式，都试一试。

• 状压想不出来直接开搜。

• 对于有哈希/unordered_map，且数据造得比较水的题，先假设哈希/unordered_map 的时间复杂度是 O(1)，然后考虑最坏的情况（所有的东西都对应到了一个键），估计复杂度，不要太侥幸。

• 哈希冲突概率（同生日问题）：O(\frac{n}{\sqrt N})。其中 N 为值域，n 为键的数量。

Feature

普遍的

• 观察值域有没有特殊之处。

• 先试一些特殊点，有利于发现性质。

• 先考虑没有修改怎么处理，是解决带修问题的第一步。

• 思路不清晰时，把式子或者要求的目标列出来。

• 注意某些值的单调性，可能可以作为 DP 状态或者求值的抓手，如 gcd 只会越来越小等。

• 看到题目里有一个很小的参数：作为状态。

• 走投无路，尝试正难则反，如倒序 DP。

• 走投无路，尝试二分。

• 走投无路，尝试使用哈希。

• 对于异或运算，尝试按位考虑。

特殊的

无限次/多次操作问题

• 考虑操作的本质，是导致了什么量的变化。

• 找守恒量。

• 考虑初始的信息在最终答案中的体现，找出对答案的限制。

• 通过某种操作策略使当前局面汇集到一个简单的局面，它包含了原局面的所有信息。

贪心

• 贪心可能需要分类讨论，不要想当然。

• 贪心排序：考虑一个值比另一个值更优的条件是什么，如果具有传递性，就按这个条件排序。或者证明排序后，任选两个交换都会更劣。

• 贪心的原则：前面的决策一定最优，不要考虑前面的情况，只用考虑当下和未来。

• 突破“决策了之后就不能改了”的刻板思路，每次决策可以改变之前的决策。这貌似是反悔贪心思想，即不保证每次操作最优，但每次都能把前面做的不优的决策改正。

• 考虑贪了这个步骤最多会带来多少后果。如果贪了这里，得到的收益会和可能失去的收益抵消，那么贪心就正确。有的时候较优方案和较劣方案的收益或代价只会相差 1，此时就要想到贪心。

• 尝试反悔某一个值（需要证明最多只需要反悔一个）。先尽量选权值最大的那些，然后尝试把其中权值最小的换成一个更远的，看看会不会更优。

其他

• gcd = 1 往往意味着“可以通过错位来填满”。（裴蜀定理？）

• 对于排列问题：考虑排名视角。

• 构造题：可以把构造方案用代数较为普遍地表达出来。

• LIS 和 LDS 最多只有一个公共点。

• 把套娃关系转化成树形关系。

• 有一些限制条件时，尝试利用坐标系，定义横轴纵轴的维度，把图画出来（可能是一些线段，一段折线等等），会使思考更清晰。

• 不可能有两个同时超过一半。

• 二叉树性质：每一层的点的个数乘以 2，要大于等于下一层的点的个数。

• 看到除以二有关：想到二叉树建模。

Model

较普遍的技巧

• 顺序无关，大小相关：排序。注意这个排序标准是什么，需要具体分析。

• 定一个端点，然后扩另外一个端点，这种方法很有用，可以在打暴力的时候把复杂度的次数降低一次。

• 区间和问题，可以先用前缀和表示，列出公式，然后考虑怎么处理这个公式。

• 条件中有绝对值：分类讨论拆掉，把与 i 有关的放到等式一边，与 j 有关的放到另一边。

• 当要对每个 i 进行求值，而复杂度怎么想都会超，不妨试试更改遍历 i 的顺序（如排序）。

• 对于只有两种花费的情况，我们可以采取定一求一（定一变一）的办法。

• 对于带 max 或绝对值的式子，尝试把它拆掉。

• 动态更新，要先问自己一个问题：是到了用的时候再求，还是修改之后更新数据？

• 当所有的询问有着共同的参数，这表示需要预处理。

• “最大化最小值”或者“最小化最大值”，立马想到二分。

• 对于“最多前几个操作能使答案合法”的问题，用二分。

• 时间复杂度觉得会超，但没有更优的策略时：尝试按照均摊视角来考虑，有可能复杂度是正确的。

DP

• 数列值分半问题：背包 DP。

• 用数据结构优化 DP/求值：先把转移方程列出来。

• DP 优化思路：第一，有哪些情况能使答案真的增加，哪些情况对答案没有贡献？第二，我们关心的究竟是什么，有没有无效的状态维度？

• 最大子段和 DP：f[i] = max(f[i - 1] + a[i], 0);。

• 【经过 i 的上升子序列方案数】=【以 i 为结尾的上升子序列方案数】*【以 i 为开头的上升子序列方案数】。

• 什么时候要用“状态”的角度思考：所有 dp 和搜索。

• DP，按步数作阶段划分，可以防止重复统计（方格取数）。

• 两个排列的最长公共子序列：把第一个序列映射成递增，第二个序列按照这个规则映射，找 LIS。

• 单调队列优化多重背包：对价值做滑动窗口，当重量为 1 时很好做。重量不为 1 时，对重量 w[i] 取模来做。

• 方案数统计也可以用于“判定是否存在一种方案满足条件”问题，可以自己定义模数比较方案的不同。

• 对于某个数组重排的方案数问题：考虑从小到大（或按一定顺序）插入数字，考虑插入位置；或者从 a[1] 到 a[n] 插入，考虑 a[i] 在 a[1~i] 中的排名（插入 DP）。

贪心

• 二维要求（点菜）：让挑剔的人尽量选最贵的，把便宜的留给穷人；让穷人尽量选最难吃的，把好吃的留给挑剔的人。

• 经典贪心模型——要做 n 个工作，每个工作有一个时间和一个 deadline：按照 deadline 排序（推贪心比较公式），所有的工作都必须往前挤，一点休息时间都不要给。我们遍历到现在这个工作，如果即使前面的工作都往前挤也放不了这个工作，那么，我们考虑把前面用时最长的替换成这个工作，让这些工作能够再往前挤一点且完成工作数量不变，这样有利于后面放工作。

• 菜肴制作这种限制，表示的并不是字典序最小，而是反序列的字典序最大。

• SAM-Toy Cars 模型：优先选择下一次出现最晚的放回架子。

• Fair Shuttle G 模型：把区间按照右端点排序。每次尝试载这组牛，查询区间内大巴车剩余容量的最小值，然后把尽可能多的牛塞进去。

图论

• 如何加最少的有向边，使得 DAG 变得强连通？源点数和汇点数较大值。构造：先保证 DAG 进行加边，加不动了之后把源点和汇点尽量一一配对相连。

• 同余类问题，可以考虑取模后变成 mod 个点，跑最短路。

• 图上环上的最小/大边权问题：最大/小生成树，再遍历每个非树边，统计贡献。可以先把非树边排序，每次贡献时把树上路径缩起来，把复杂度优化到 O(n)。具体来讲，把两点路径上的每个点的父亲都设置为那个 LCA 点，这样保证了树形结构。

• 这个技巧也可以用于某类并查集题目：按照边权排序，每次当查询分布在两个待合并的并查集的时候，当前的边长就是这次查询的答案。

• 处理更新类问题时，如更新最小值，那就把要更新的操作从小往大排序，更新之后就并查集缩点（因为后面的更新不会对缩成的点中的点造成贡献）。

• 二选一限制问题：建图。

• 图论，计算答案（如最短路等）很复杂时：建一个超级源点，利用算法本身来帮我算。

• 建反图是一个很好用的技巧。

• 如果图上 DP 转移时出现环，尝试找到一个确定答案的点，对边进行排序，进行“松弛”（即状态传递），然后把这条边删掉（禁用）。

• 一个怪兽打了之后分裂成多个，或者几个药水能合成一个新的，这种题考虑图论建模 DP，用上面的技巧。

• 图论中减小需要加的边的数量的一种常用方法：新建一个中间节点。

• “有几次机会”类题目：分层图。

树上问题

• 无根树，考虑钦定根节点做树形 DP。当没有固定根节点（或遍历开始节点）时，尝试以题目中的特殊点作根。

• 子树统计问题：遍历子树后的答案减去遍历子树前的答案。

• 树上从高到低的路径，可以用二进制数表示，左 0 右 1。这样可以进行往下走的路径的合并。

• 树上单点修改，最后路径求和：从根节点到 u 的前缀和。路径修改，最后单点查询：差分，统计子树和得到原数组。

• 在一个树里面选一些点，统计方案数，可以用树形 DP。

• 树上求所有简单路径的【什么什么】，可以先以某个点为根，算所有以根为一端的简单路径的【这个东西】，然后跑换根 DP。

• 树上放点，可以控制一定距离内的点（将军令）：dfs，从下往上能不放就不放，不得已才放。需要维护：u 到它的子树内最近小队的距离，以及 u 到它的子树内最远未控制的点的距离。

• 树上路径异或值：异或两次就为 0，所以路径异或值就是：u 点到根节点路径异或值，异或上 v 点到根节点路径异或值。

• 树上，如果每条边最多能走两边，意思就是一定要按照深搜的顺序走。

• 利用后序遍历把树“压”成线性，类似树链剖分，但实现起来更容易。适用于“子树中如果根节点不能选，那么整个子树都不能选”的 DP。按后序遍历的编号遍历，具有如下性质：

  • 已经遍历到的点构成森林。
  • 每次遍历到的点 u 一定是森林中某棵树的根。
  • 这棵树中的点编号是连续的，即区间 [u - size_u + 1, u]（size_u 表示这棵树的大小）。

• 基环树 DP：尝试断开环上的一条边转换成树形 DP，然后对这条边的限制做特殊判断（如一条边两个点不能同时选，那么就在做树形 DP 后，做答案统计时加一个限制：断开的那条边两个点不能同时选）。

数据结构

• 使用扩展域并查集求解 2-SAT 问题：用于双向条件（比如，如果 p 为真，q 就为假；如果 q 为假，p 就为真）。否则，就要用强连通分量。

• 二维动态求和问题：别忘了还有二维树状数组这个工具。

• 可撤销并查集：不能做路径压缩，用启发式合并。

• 区间第 k 小问题：权值树状数组 + 树状数组上二分。

• 字符串前后缀比较要想到字典树。

数学

• 因数问题转为倍数问题，调和级数。

• 选 n 个数，要保证不下降，且值域在 1 ~ len 之间，求方案数：插板法。

• 取模之后其实也可以支持除法：用逆元。

• 组合数求和问题——范德蒙德卷积：https://oiwiki.com/math/combinatorics/vandermonde-convolution/

• 数论分块，解决求 \sum_{i=L}^R \lfloor\frac{n}{i}\rfloor 的问题。每一个分块的左端点 l 是上一个分块的右端点加一，右端点是 n / (n / l)（向下取整）。同一个分块中的 \lfloor\frac{n}{i}\rfloor 是一样的。时间复杂度 O(\sqrt n)。

• 组合数学问题中，隔板法很常用。

• 从区间 [0,L] 中取 n 个非负整数，要求所有非零数严格递增，则方案数为 C_{L+n}^n。见题解。

• 两个互质的数 x, y，不能表示的最大整数是 xy - x - y。

• 区间 [l, r] 内（设长度为 r - l + 1 = n）取 c 个点，且不能相邻，方法数：C_{n - c + 1}^c。证明：要取 c 个点，就有 n - c 个空位，现在要在这些空位之间插入 c 个选择的点（插板法），且不能插在同样的间隙中，因此方案数为 C_{n - c + 1}^c。

数轴上的线段、区间、扫描线等问题

• 区间的离散化（如果原坐标轴代表的是【格】而不是【坐标点】）：把区间转化为左闭右开，把左端点和右端点加入关键点列表，按关键点把全区间做切分。

• 在一个很长的数轴上的问题：尝试把没用的区间压缩掉。

• 线段覆盖问题：在数轴上有一些点，要选择最少的点，使得满足所有要求，要求形如：在区间 [a, b] 要出现 x 个点。解法：先按右端点排序，确保重叠的部分尽可能多。对于每一个要求，先统计在这个区间里面已经填充的点有几个。如果已经满足要求，就不用再填充。否则，从后面开始加点直到满足这个要求为止。如果这个位置已经有了点，那么应该跳过这个位置。或者用差分约束，就是 n+1 个前缀和的大小关系。注意隐藏条件，相邻只能加一。

• 一生之敌 - 区间覆盖模型 - Another Version：给定一些区间，每个点都有一个要求，要被至少几个区间覆盖。问最少要选择几个区间？解：对区间按左端点排序，遍历 i 作为扫描线，把【左端点在 i 及以前的区间】的右端点加入大根堆，然后对于 i，算出还需要被几个区间覆盖（设为 k 个），从堆里面选择右端点最右的 k 个（这样最优）区间，并进行区间修改（这个区间内的点被覆盖次数++，用树状数组维护）。

• 询问有多少个贡献区间和询问区间相交：R 之前的所有区间开头数（包括 R），减去 L 之前的所有区间结尾数（不包括 L）。或者：按照左端点排序，贡献加到右端点，每次查询右端点在 [L, R] 范围内的贡献区间数。

• 询问区间内包含了多少个贡献区间：离线，扫描右端点，统计左端点在 [L, R] 内的区间数量。

• 区间不互相包含，意味着如果按其中一个端点排序，那么另一个端点也会排好序。

• 对每个元素 l，预处理出右边第一个满足要求的元素 r（这里是异或和为 x）。这是“区间找点对”或“区间中找最长子区间”问题的一种常用的思想。 然后判断区间 [L, R] 是否包含任意一个[l, r]。

• A 和 B 是两个数组，线性计算 \sum_{x \in A, y \in B} min(x, y)：排序，单调性枚举，统计贡献。

棋盘网格图问题

• 空地的四连通，可以转化为障碍物的八连通。

• 当 n 和 m 不一样的时候，尝试利用那个更小的值降低复杂度。

• 网格中统计特殊图案/子矩形：记录往上下左右拓展的最远距离。

• 移走最多 K 个障碍物问题：转化为两个点之间最少经过多少个障碍物才能相互通达，跑 BFS 最短路。

统计问题

• 求两两之积的和：动态维护前缀和。或者用这个公式：一个数组两两之积的和，等于数组的（和的平方 - 平方和）除以 2。

其他模型

• 相关联的开关问题：建图。

• 判断括号序列是否合法：左括号 +1，右括号 -1，全程不能出现负数（相当于栈）。

• 给定序列 a[1 ~ n]，每次操作需要选出 k 个正数，并将它们都减去 1，问：能否进行 t 次操作？判断方法：砍掉大于 t 的部分，剩下的求和，看这个和是否不小于 k * t。

• 动态维护中位数：对顶堆。设集合大小为 s，维护一个大根堆 A，存放前 s/2 小的元素，再维护一个小根堆 B，存放后 s/2 小的元素。中位数就是两堆的堆顶取平均。插入元素时，如果它小于等于 A 堆顶，那就插入 A；否则插入 B。当一个堆大小超过 s/2，那就弹出堆顶并推入另外一个堆。对顶堆，用于动态维护一个序列上第 k 大的数，k 值可能会发生变化。

• 有很多和“黑箱”的待选池，只能支持访问其最大值以及弹出最大值之后得到次大值，现在问所有待选池中的数的第 K 大：把所有待选池的最大值 push 进堆，每次区堆顶所在待选池，得到其次大值之后再 push 进堆，执行 K 次。不一定要从最大值推到次大值，有时候需要从头开始推次大值。

• “灭绝树”（灾难）：按照拓扑序遍历。归纳，假设我们现在有一棵树，它有一个性质：某个点灭绝会导致它子树内的点灭绝。考虑怎么加点，维护这棵树的性质。一个点要灭绝，必须要求它在图上的所有前驱都灭绝。也就是说，这些前驱在树上的 LCA 要灭绝才行。因此，可以把这个点加入树，直接连到这个 LCA 下面。

• 一个工作做完后可能影响其他工作能否做：推贪心比较公式，一般是按 deadline 排序。

• 链上均分纸牌（相邻传递操作）：处理出和平均值的差值，然后做前缀和，前缀和的每个值的绝对值之和就是答案。

• 环上均分纸牌：一定有两个位置间不交换。所以可以枚举一个位置 k，最小代价就是 \sum_{i=1}^n |sum_i - sum_k|。

• 折半查找：枚举超集和枚举子集结合，比如 2^{20} 拆成前 10 位超集，后 10 位子集。

• 括号问题：转化为 +1 -1，很可能需要用前缀和进行约束。

• 平面几何的“连成一片”问题，可以进行图论建模。

• 01 分数规划：二分答案。

其他 trick

• 统计三元组：枚举中间的一个。

• 单峰函数，用“导数二分”找峰值。

• 带修问题，修改时把某个物品禁用，且修改不保留：维护前缀、后缀答案。

• 让模 2^k 同余的数都在某一个子树里面：把二进制数倒过来，左 0 右 1。

• 区间异或和的一些 trick：

  • 前缀和；
  • 前缀和 sum_i \oplus sum_j 有 i > j 这个限制，考虑利用异或运算可逆性，将这个限制解除，也就是将表格中的三角转成全表格；
  • 01 字典树。

• 别的点到一个点的带权距离比较问题：尝试拆距离表达式，排序。

• 合成问题：可能可以对合成后的物品再开一个数据结构（栈、堆等），保证一定的单调性或者其他性质。

• 构建 k 叉 Huffman 树：补充一些权值为 0 的点使其能够刚好合成完，即每个点都有 k 个子节点。

• 平移操作，要看看下标是否重要，如果不重要，想想可不可以用 multiset 代替。

• 有 n 堆东西，大小记为 a[1~n]，现在要尽可能配对，只能在不同堆内配对。如果 a 中最大的数大于其他所有数之和，那么总的不能消化的点的数量就是（a 中最大的数 - 其他所有数之和）。否则，可以证明一定可以配对使得落单的点的数量是 0 或 1（依奇偶而定）。

• 带有乘并取模的修改操作，要做大小比较，可以使用对数。

• 对于有负数乘法的运算求极值：要考虑到负负得正的情况，既要维护最小值也要维护最大值。

• 看到环，就立马想到破环成链。

• 信息的了解与否，在概率、期望问题中尤为重要。

Algorithm

Tarjan

• 判断一个点是不是割点的条件：存在至少一个儿子 v，使得 low[v] >= dfn[u]，即不能回到祖先，那么就是割点；对于遍历的起始节点要特判，如果有至少两个儿子才是割点，否则不是。到未遍历的点就是树边，否则就是返祖或前向边。

• 边双根节点判断标准：low[u] == dfn[u]。其父亲边就是割边。不用对遍历起始节点进行特判。

• 割点同属于多个点双。两个点双最多有一个公共点（割点）。否则这两个就会被合并为一个点双。如果不把割点计入点双，那么会把一个图切分成割点和很多个连通块。下面是求点双要注意的点：

1. 判断标准：low[v] >= dfn[u]
2. 出栈一直到 v 而不是到 u
3. 最后要把 u 加到点双里面
4. 要特判独立点（fa == 0 and cnt_son == 0）
5. 不用特判根节点且子节点数为 1 的情况，这种情况下根节点是会被算进一个点双里面的

• 点双意味着从任意一个点到另外一个点，没有哪个点是必经的，也就是说从任意一个点到另外一个点有至少两条【中间点完全不同】的路径。

• 边双意味着从任意一个点到另外一个点，没有哪条边是必经的，也就是说从任意一个点到另外一个点有至少两条【经过的边完全不同】的路径。

其他图论算法

• 一个图的两个边集合并，其最小生成树一定在两个边集的最小生成树的边中取。

• Dijkstra 最短路可以不用 vis 数组，只需要出队时判断堆顶的 dis 是否大于 dis[u]，如果大于，就说明已经作废，continue 掉。需要注意的是，这种情况下松弛操作必须在更新的距离严格小于原先距离时才能进行。对于次短路，判断堆顶的 dis 是否大于 u 的次短距离值。这样能保证复杂度正确。

• 拓扑排序找环的一个普遍思路：先把不在环内的点按照拓扑排序后入度不为 0 筛掉，然后找环。

• 在拓扑排序的任意时刻，队列里不会出现有祖宗关系的节点。

• Dijkstra 算法的核心是：当前确定的状态永远不能被将来的状态更新。因此对于“路径的长度等于路径中最长边的权值”等问题，Dijkstra 可以用来求最短路。

• 图论的很多算法很灵活，比如可以边在缩点图上进行拓扑排序，边在小图上进行 Dijkstra 等，比如 Roads and Planes G，要灵活变通。

DP

• 在图上，DP 转移代价为 0 或 1 时，可用 bfs；否则，用 priority_queue 的 bfs。

• DP 答案值域比较小时，可以用答案作状态（如最长递增子序列：f[len] 表示最长递增子序列长度为 len 时，最后一个数的最小值，f 是单调的，用二分）

• DP 分区：前 i 个？以 i 结尾？以 i 开始？

• “物品的代价之和等于 j 的最大价值”和“物品的代价之和不大于 j 的最大价值”的区别：如果是前者，设 f[i][j] 表示“前 i 个物品，物品的代价之和等于 j 的最大价值”，那么前 0 个物品，代价只能为 0，即 f[0][0] = 0，并且 f[0][x]（x > 0）都要设置为不能转移。如果是后者，设 f[i][j] 表示“前 i 个物品，物品的代价之和不大于 j 的最大价值”，那么前 0 个物品，代价可以为任意，即对于任意 x，f[0][x] = 0，并且 f[0][x] 都要设置为能转移。

• 区间 DP，一般就是两种转移方式：一，合成得到；二，拼接得到。

• 能用完全背包就不要用多重背包硬模拟。

• 树形 DP：可能需要记录根节点的决策状态。

• 线性 DP 的基本方程（由 i 前的任意点转移到 i）：f[i] = max(f[i], f[j] + g[j + 1][i])，其中 g[j + 1][i] 一般要预处理。

搜索、回溯

• 01 BFS 可以代替 Dijkstra 进行 O(n + m) 求最短路。

• bfs 技巧：从终点往起点搜（当起点比较多时）。

• 回溯的常见剪枝技巧：位运算、改变枚举顺序。

• 状态数过多时，要用 bfs，不要总是想 dfs。如果空间允许的话要记忆化，记录 vis，防止重复遍历。

前缀和、差分

• 前缀和能解决的问题要满足两个条件：满足结合律、存在逆运算。

• 任意多项式函数生成的数列都可以通过有限次差分，变成只需要常数次修改。

Code

算法实现

• 缩点时边权的维护：后面重新建图时再处理，不要在 Tarjan 时处理。

• DAG 中从某个起点出发，问路径点权最大值：用拓扑排序，不要用 dfs，因为可能有前向边，导致到同一个点有好几条路径，由于乘法原理，搜索次数会指数增加。拓扑排序时维护数组 reachable[] 表示这个点能否从起点到达。

• 对于区间 [l,r] 之内的数的求值问题，如果左右边界残余部分很难处理，那么可以用 ans([1,r])−ans([1,l])，这样就只用处理右半边的残余部分，会方便一些。

• 对某一个序列，二分答案，如果答案的值域是序列的值域，可以先对序列进行排序，去二分【答案夹在哪两个相邻数之间】，再用数学公式推出来答案。即：二分的时候 check(a[mid])。

• 如何遍历树上两点间的路径？先跑出深度，然后用朴素 LCA 算法，每次选择深度较大的往上跳，直到两个点汇合。

• 对于有负数的 dp，转移时判断合不合法，除了要判断有没有超出下界，也要判定有没有超出上界。

• 多路归并可以改成先对所有的东西进行排序。

• 不判重边自环见祖宗！

• 写 dp 要严谨，每写一个语句都要考虑周全，不要漏掉情况。比如循环是从 1 到 n 还是从 0 到 n。 写完代码后自己带着怀疑的眼光模拟一下，检查有没有漏情况。

• 注意无向图中，跟边有关的数组要不要开两倍。

• 二分查找，有可能出现断层，就是不存在查找的值，要注意判断。

编译、调试

• c++ A.cpp -o B.exe -O2 -std=c++14：把 A.cpp 编译成 B.exe。./B.exe 运行。

• 对拍，生成随机数：主函数外 mt19937 rnd(time(0));，主函数内生成一个 0~9 之间的随机整数：rnd() % 10。

语法

• 字符串转数字：std::stoi()，string to int。

• 手写哈希函数：

  struct 键的哈希函数 {
  int operator()(const 键类型 &键) const {
    // 哈希函数
  }
  };
  unordered_map<键类型，值类型，键的哈希函数，键的相等函数> mp; // 如果重载了 == 就不用写相等函数

• 负数除法向下取整的话不能直接除（直接除是向零取整），要用 floor(double(x)/y)。

• 两个整数相除存入 double 中，要乘以 1.0。

• 最大值要设置得更大一点。

• 局部变量要赋初值。

• unordered_map 有时可以换成双哈希映射进行处理

• 涉及“状态数总和不大于 1e6”一类的部分分，开数组大小要注意，不要直接开 n * maxlen 数组，要用 vector，而且一开始不要定义大小。

• 匿名函数：中括号里面捕获，[&] 引用所有。

• 函数传大数据一定要加引用。

• map、set 有 .lower_bound() 函数。

• 常数优化：让遍历的内层循环内存尽可能连续。

• bitset<len> 可以优化 dp。注意 len 必须是一个数，不能是变量。

• 不要用 vector<bool>，会变慢。

• map、set 的迭代器支持 ++ 和 --，并保证顺序。一次 ++ 或 -- 复杂度为 O(\log n)。因此，遍历复杂度是 O(n \log n)。

• multiset：删除一个元素的一次出现要用 erase(it)，删除全部出现用 erase(value)。

• 不管是 map 还是 unordered_map，用 double 作为键都是很危险的！会有精度误差。

• all_of(a + 1, a + n + 1, [](int x) { return x == 1; }) 返回数组是否全为 1

• 位运算的优先级比等号、赋值符都要高，要加括号！

• 多个测试数据，memset 一定要慎用，因为可能每次 n 很小，但 memset 都要把全部都清空

• 为什么有些引用参数要加 const？因为传进来的可能是一个临时变量，加了 const 的意思就是保证这个函数不会对这个临时变量做修改。

• 取模写形如 (x += y) %= mod 的时候，一定要注意 %= 不能写成 %。