考场上 Hints
加油啊。
-
心态很重要
-
题目没有那么简单，也没有那么难。
-
看题，最好先手玩一下样例/打个暴力。
-
不要一道题的验证暴力打很久，按题意模拟即可，不然可能会没时间想正解。
-
尝试先多想几个方向的思路，给出一些看上去比较可行的方案。
-
想到一个思路最好不要马上打代码，再思考一下，想清楚。
-
尽量写出自己的思路，如果还有可以思考的点就不要放弃。
-
需要分类讨论的草稿纸按格式写，最好能有缩进和层次结构，写清楚和准确是避免写不出来的好方法，尽量减少模糊的表述，尤其是模拟，可以用数学语言，限定清楚，把 corner case 写下来。
-
若干个算法组合
有哪些不太容易想到的？bitset，Hash，转成图上问题，二进制分组，根号算法
-
不要一道题做着做着忘了时间
-
做题速度，但是精准度也很重要。
-
多想相似的知识点可能可以使题目更可做/代码更好写。
-
千万不要忘了题目的限制或者自己多添加限制然后忘了。
-
注意题目的特殊性质（也可以自己想特殊性质），也要考虑不同暴力及其对性质的利用，或者对正解的提示作用
-
如果题目有特殊的格式要求，可以尝试先写出代码再修改。
-
想清楚再打，如果错了尽量想清楚再调，一定记得存原本的代码。
-
特判 sub 记得数组开够，避免 RE。
-
如果是 spj 的一定判断一下正确性。
-
在保存的时候记得把 assert 删去，避免没想到但是对的情况，可能可以多拿分。
多想为什么
- 找套路
- 联系不同的题
- 会板子，不要被卡科技
- 善于“刻画”复杂操作/函数
- 多定义辅助思考的 函数/集合 等
- 有些时候不一定要用到所有的性质
- 刻画复杂限制的时候先别直接开做，思考！
- 若限制的过程是一个可行性判定的问题，且是对于多个考虑限制，可以考虑对偶一下，即通过某些方法把限制作为值。
正确的：第一步读题目，观察一会；第二步想到若干个算法组合，发现思路正确；第三步写会代码，略微修改。
避免：在想到可能的算法后，仔细想想发现非常复杂，在犹豫中优化、修改，甚至会陷入不断求证的循环里，不知不觉时间就不够了。
看一下自己写的一些东西。
需要复习的东西：
manacher
SAM
Treap 和 fhq Treap
可并堆
网络流
自己的博客
三/四元环计数
tarjan 点双/边双
prufer 序列
计划
比赛
最近不是很稳，每天都挂很多分，是为什么呢？
-
题目看错/忘记限制
- 可以先打个暴力，把限制写下来，写清楚！
-
想到正解的旁边去导致看上去很对但是实际上错误
- 根据一些已经有的模型思考：矩阵/图/多项式/集合幂级数/hash
-
大模拟/大数据结构导致没有时间写暴力
- 先大致看一遍题，浏览一下题意，给每道题留出时间，有助于把控时间，策略得分
- 想一下能不能用更简单的东西维护？
- 快速实现，并且先用暴力替代一部分难写难调的再写，可以避免整体的调试。
- 对拍和正解尽量不要用同一个缺省源。
-
数据过弱/corner case
- 这个怎么办？可以自己写个暴力和数据生成器*
- 自己注意 corner case，暴力最好是直接模拟，数据生成只根据数据范围来
-
T4 可能并不是最难的 \(\to\) 题目难度不一定是正序的
- 先浏览一遍题目，给每道题留出思考时间，快速实现（替换法减少调试时间）
-
可以/需要分讨的题目，有 corner case 的题尽量写的好一点，实在不行就特判，但注意 corner case 输出不要写错！
-
头晕：不要太紧张，打出一道题/想到一道题的思路之后可以上个厕所冷静一下。
-
多测要清空
-
可能还有一些代码上的细节
考场上 Hints
-
不要一道题的验证暴力打很久，会没时间想正解。
-
想清楚再打，如果错了尽量想清楚再调，一定记得存原本的代码。
-
特判 sub 记得数组开够，避免 RE。
-
题目没有那么简单，也没有那么难。
-
多想相似的知识点可能可以使题目更可做/代码更好写。
-
尝试先多想几个方向的思路，给出一些看上去比较可行的方案，尽量写出自己的思路，如果还有可以思考的点就不要放弃。
-
如果是 spj 的一定判断一下正确性。
-
在保存的时候记得把 assert 删去，避免没想到但是对的情况，可能可以多拿分。
-
暴力不要写挂（千万不要忘了题目的限制或者自己多添加限制，添加了别忘了是自己添加的），可以先写一个暴力？
-
需要分类讨论的草稿纸按格式写，最好能有缩进和层次结构，写清楚和准确是避免写不出来的好方法。
-
做题速度，但是精准度也很重要。
-
如果题目有特殊的格式要求，可以尝试先写出代码再修改。
-
看题，最好先手玩一下样例/打个暴力。
-
心态很重要
-
想到一个思路最好不要马上打代码，再思考一下。
-
注意 corner case！
-
思考的时候可以把代码写下来，写的清楚一点，对于复杂的可以一步步细化，但注意不要一开始就错了。
-
想的太多又不想/写清楚，会似的。找性质切忌不用笔。
-
遇到一道题可以想一下它可能是由哪些算法构成的，想到之后可以考虑类似的算法，但注意还是要从题目整体入手防止走到死胡同走不出来，如果走不出来了可以先考虑其他算法，先放着！
-
做题的时候写清楚，尽量减少模糊的表述，尤其是模拟，可以用数学语言，限定清楚，把 corner case 写下来。
-
不要一道题做着做着忘了时间，只要想清楚其实可以有效避免头晕之类的钻进死胡同。
-
NOIP 等考试注意题目的特殊性质（也可以自己想特殊性质），也要考虑不同暴力及其对性质的利用，或者对正解的提示作用
-
加油啊。
辅助思考
辅助思考的方法非常重要！
摘录
对于这个问题，我们可以将序列拆成一系列状态 \((u, x)\)，初始在 \((1, x)\)，每次令 \(x\leftarrow F(x, u)\)，然后
有哪些不太容易想到的？bitset，Hash，转成图上问题，二进制分组
思维方式
多想为什么
- 找套路
- 联系不同的题
- 会板子，不要被卡科技
- 善于“刻画”复杂操作/函数
- 多定义辅助思考的 函数/集合 等
- 有些时候不一定要用到所有的性质
- 刻画复杂限制的时候先别直接开做，思考！
- 若限制的过程是一个可行性判定的问题，且是对于多个考虑限制，可以考虑对偶一下，即通过某些方法把限制作为值。
正确的：第一步读题目，观察一会；第二步想到若干个算法组合，发现思路正确；第三步写会代码，略微修改。
避免：在想到可能的算法后，仔细想想发现非常复杂，在犹豫中优化、修改，甚至会陷入不断求证的循环里，不知不觉时间就不够了。
套路记录
复杂情况
- 情况过于复杂的要写清楚，如果有多种复杂且难以考虑的情况的，可以尝试证明某些情况不存在。也可尝试调整法用于证明。
* 比赛 NFLSOJ
独立性
平面上点的移动
- 对于可以 \(L,R,U,D\) 移动到 \((x, y)\) 的问题，考虑旋转 45°，发现变成可以 \((±1，±1)\) 移动，移动到 \((x - y, x + y)\)，此时 \(x, y\) 轴独立，可以分开计算后相乘。
DP 优化
-
如果要记录的状态太多，可能（应该）是因为影响的因素太多，此时可以考虑独立性。但其实直接找独立性不太容易。
-
可以尝试分析最终答案的性质（调整法，一定不优的不用管），并枚举这个特征量或者什么操作，以此来将原本的问题变成一些子问题。
-
如果是直线上有关每个区间选一个点的问题，可以考虑是否存在一个“断点”使经过这个断点的区间都在这个断点上取到最优或者可以分割
-
而且如果选择的点之间相互影响决策，选择也没有顺序，那么就尽量不要一个一个加入？（也不一定）
-
-
独立性非常重要，若是区间最大值作为贡献的可以考虑最大值并据此分成多种情况。
* 最小化 NFLSOJ
-
位运算+加法
AND
-
考虑从低到高位，因为高位不影响低位，所以独立性更强！考虑低位到高位！！！
-
也可考虑从高到低，此时可能是类似线段树上二分的做法，对于加法记录一个 max/min 即可代表一个集合。
-
可能划分阶段是核心思想，划分阶段可以使独立性更强，有些时候独立性可以是划分阶段后阶段间的独立。
XOR
-
和异或有关的考虑 Trie 上做 和 一位一位确定答案
-
可以考虑记录 \(+\) 的限制相关，因为 \(+\) 可以只用 \(\min, \max\) 来刻画一个集合。
DP 过程的前/后效性特别强
- 尝试考虑最终答案形态（或性质），考虑满足有任意一个最优解会被 DP 过程得出即可。
判定性问题
-
在保证有解时，判定解可以从两方面入手：
- 其为解所必须满足条件
- 其不为解必须满足条件（这个比较难想到）
若 1 不符则必不是解，若 2 不符则必是解
限制转换/模型转换
不重复序列 \(\to\) 图上简单路径
- 生成一个不重复序列，且 \(a_{i + 1}\) 是 \(a_i\) 根据某种操作转化/用某种限制限制的，可以考虑在可转移的两个元素之间转化为图上的一条简单路径。
* MX-S4 youyou 的三进制数 - 单调递增序列 \(\to\) 区间选点
曼哈顿距离 \(\to\) 完全图
- 可考虑单纯将 \(dis(p_1, p_2)\) 作为可方便计算值的函数，转而采用完全图的性质来做。
* [UESTCPC 2024] 2-聚类算法
多个限制 \(\to\) 确定部分限制后的判定性问题
-
多个限制考虑确定几个限制后将剩下的转换成判定性问题（尤其是集合选择这种一眼 NP-Hard(?) 的？）。
原本不好做但保证了特殊性质
-
考虑特殊性质的作用，如判定序列上区间的可重集相等，对于相交的可转为不相交的，若保证了每个数出现次数 \(\le 2\) 则不相交的可以转化为和上一次出现的位置有关的判定。
\(\exists\) 区间 \(\to\) \(\exists\) 点
- 若原本为 \(f_{u, seg}\) 表示限制某个 \(x\) 属于 \(seg\)，合并时是区间交，要求不能为空，可以考虑设 \(f_{u, t}\) 为选择 \(seg\) 中的一个点，相当于转变为维护这个 \(t\) 的转移，且每次都在得到的区间中的 \(t\) 一定存在，故取得到。
共端点区间 min/max \(\to\) 笛卡尔树上中序相邻点对
-
可以尝试模型的转化，如果是对于一些共端点的区间的区间最值进行限制，可以考虑在笛卡尔树上做，但注意将限制的等价表述表述清楚，不然可能会暴毙，可能相当于限制了这个点集不能在 \(u\)，和它的左右子树中同时出现。
-
注意此时可能可以在没有放的子树内放一个。
曼哈顿距离 \(\to\) 切比雪夫距离
- 对于曼哈顿距离，（若 k 比较小且限制的是 max）可考虑转化为切比雪夫距离。
边权 \(\rightarrow\) 点权
- 若贡献为边权和，且操作为选点，最终答案为 \(\sum\limits_{i, j\in S_1} w(i,j) - \sum\limits_{i, j\in S_2} w(i, j)\)，可考虑将边权分担在点上，边权 \(\to\) 点权（选点）。
* [UESTCPC 2024] 2-聚类算法
点权有向图 \(\to\) 拆点 \(\to\) 边权有向图
-
\((u\to u', w_u), \forall e = (u, v)\in E, (u'\to v, 0)\)
限制是构造一组 \(p\)，满足可逆（不一定相同）的关系
e.g. 使得 \(\forall (u, v, w), p_u + w\equiv p_v\pmod x\)
异或 \(\to\) 集合幂级数 \(\to\) FWT
-
对于异或可以考虑用集合幂级数来描述问题，先做一遍 FWT 变成对应位置相乘的线性变换，接下来可能会好做许多。
多模态匹配 \(\to\) AC 自动机上 DP
- 注意若是不能走的是将某个的 fail 子树全部删除。
01 矩阵 \(\to\) 完全二分图定向/二元函数 01 \(\to\) 边定向
- \(A_{i, j}\) 的值可以转成 \((r_i, c_j)\) 间的边定向，01 矩阵的行/列和可以转成 \(c, r\) 的度数。
- 若是判断行/列和相等的可以考虑对于两个原本相等的 \(A, B\) 去除共同的边之后，图由环构成，且恰好是只存在相反的边。
ARC186A
- 若是判断行/列和相等的可以考虑对于两个原本相等的 \(A, B\) 去除共同的边之后，图由环构成，且恰好是只存在相反的边。
哈希 Hash
单调栈 \(\to\) 矩阵 Hash
好牛
- 考虑如果单调栈是相同的弹出，否则加入的话，判断一个串是否可以刚好消除可以将 a 轮流替换为 \(A^{1}\) 和 \(A^{-1}\)，其余同理，然后按顺序乘起来判断积是否为单位矩阵 \(I\)。因为一个完美匹配的乘积必为 \(I\)，而矩阵乘法满足结合律不满足交换律（半群性质）。
* 换猫 NFLSOJ
模拟类限制
- 单调栈，加点时，若相同就弹出，否则加入。可以合并，考虑 cdq 分治，可以二分 + Hash 判断弹出多少个。
* 换猫 NFLSOJ
容斥
为什么要容斥？
求恰好不好做，可能是由于转移系数不好算，或者状态太多。
通过钦定/要求某个限制，使得转移系数与之前的东西相对独立，从恰好每个都被选变成可以选任意一个，此时转移系数只与集合的大小有关。
* [ZJOI2022] 树
容斥系数
- 容斥的容斥系数没有那么复杂，考虑容斥系数的目的实际上是 \(k\) 个的会被 \(0, \dots, k - 1\) 先贡献一遍容斥系数，加上 \(k\) 的系数后要把它的系数变成 \(1\)，其实这个系数应该只与我们怎么设状态有关。
均摊容斥系数
- 考虑把答案的式子写出来，我们可能并不需要求出每个 \(c'\) 的方案数，可以尝试把所有的系数转移在转移过程中均摊掉。
- 有些时候由于二项式反演或者什么东西的存在，每转移一步要乘的系数不一定非常显然，此时可以考虑把式子列出来，也许可以用二项式定理，这样我们就可以少记录一位（即钦定的东西），并把这个东西在转移的过程中均摊掉。
* Ruin the legend
* MX-S6-T4 彩灯晚会
“点减边”容斥
-
对于树上问题，限制是 存在某个连通块集合满足限制 可以考虑 点减边容斥，把艾弗森括号 \([\_]\) 转换成数值，即 \([S\not=\emptyset] = (|\{p\in S\}| - |\{e\in S\}|)\)。
-
钦定大部分时候是为了方便转移/减少需要记录的状态，当转移系数只与钦定的值有关时可以只记录钦定的个数，而且最终算答案的容斥系数应该只与怎么钦定有关，与转移状态无关可以独立成两个问题考虑。
一类序列容斥计数问题
-
给定 \(M\) 和 \(p_{1\dots n}\)，求有多少序列 \(a_{1\dots n}\) 满足 \(\sum a = M\) 且 \(\forall i\in [1, p_i]\)。考虑如果没有 \(p\) 的限制可以用隔板法，如果有 \(p\) 的限制考虑钦定某些 \(a_i > p_i\) 即令 \(a_i = p_i + a_i'\)，此时减去钦定的 \(p_i\) 后可以用隔板法做，同时如果 \(M, p\) 很大的话可以 meet in middle 和 广义范德蒙德卷积 做到 \(\mathcal O(n^22^n)\)。
DAG 计数（可带权） - 容斥
- 考虑转移时枚举入度为 0 的子集/出度为 0 的子集，相当于钦定了新加入的是独立子图 和 新加入点的和未加入的点之间没有 出/入 边，此时点与点之间变得相对独立了。对入度为 0 和出度为 0 的都考虑一下！
重要
-
枚举入度为 0 的子集后对于加入的 \(T\)，\(T\) 中的点只可能指向 \(S - T\)，此时对于每个 \(v\in T\)，可以单独确定它的出度且不会因为后面的改变，可以考虑枚举它的出度。
思考：如果 DAG 的权值和每个点的出度/入度有关可以考虑这样做，如果与入度/出度都有关呢？
期望
可做性
- 能拆开的/独立的贡献尝试分开算，这样很可能是不劣的（除非可以互补吗，没见过）。
- 但注意有可能奇怪的贡献可以用考虑贡献的组合意义做，如集合中选点。
计数转期望
贪心思想
不考虑一定不优的贡献
-
如果是两两点之间的最优贡献，可以尝试不考虑一定不优的点对。
e.g. max(abs(斜率)) 一定在 x 相邻的两点间取到。
DP 的值与某一维度互换(可以分析一下答案的上界或者打个表？)
- 若值为 01 或者 值比较小且满足某个性质（单调性，只考虑最优的），可以考虑在 DP 的状态维度记录其答案，例 \(f_{i, j} = x\to R_{i, x} = \max\limits_{f_{i, j}\le x} j\)。
点分治树
优化建图
- 点分治/toptree 优化建图，可以把每个点拆成入点和出点考虑。
树上和 dis 有关的转移
- 如果转移的顺序是一定的且转移方程和 \(dis\) 有关，可以考虑在点分治树上维护一个凸包。
树上连通块 DP
-
树上背包维护连通块，如果我们已知某个点一定在连通块中，按 dfs 序依次取出，若被选则转移到下一个点，否则转移到第 \(dfn_u + size_u\) 个点，可以避免合并。
点分治后 DP 做到 \(O(n\log n)\)。
四边形不等式
-
形如 \(f_{i, j} = \max\limits_{k} {f_{i - 1, k} + w(k + 1, j)}\) 时，考虑四边形不等式，\(w(l, r) + w(l + 1, r - 1) \le w(l, r - 1) + w(l + 1, r)\)。得到四边形不等式给出了一个决策单调性的充分不必要条件。
单调栈
前缀 max/后缀 max
-
如果是前缀 max 个数/后缀 max 个数，考虑单调栈树，可以分成两类转移，即转移权值矩阵 \(A, B\)，考虑变化的位置和量。
线段树优化 DP 的本质也是快速维护 \(A, B\) 的变化，从左到右每个位置都取两种的最大值。
-
如果是前缀 max/后缀 max 并且是一个环，考虑从 max 处断开，分两类考虑。
判断能否成为栈底
- 如果是区间里依次加入问能否成为栈底的，考虑全局从左往右加，设上一个是 \(pre_i\)，那么答案即为 \(l\le i\le r\) 中 \(pre_i < l\) 的个数。
* NOIO2022 丹钓战
优化模拟
存在一类题，我称之为“优化模拟”。
排序类
对于某个排序的伪代码，求进行 k 次后的序列，
- 考虑某个值所在位置的变化
- 考虑某个位置上值的变化
* NFLSOJ 排序
矩阵旋转，子矩阵加
- 考虑“旋转”是一个比较难以维护的操作，这是这道题的难点也是突破点，考虑什么时候旋转是简单的，每次都旋转整个矩阵的时候，因为此时子矩阵内部的“结构”不变，这就是旋转操作的特点，每次旋转只有 \(O(n)\) 的相邻关系会改变，考虑维护相邻位置即可。
* [SNOI2024] 矩阵
计数
图计数
图的限制一般都很麻烦，但一般都比较弱，仔细分析最重要。
- 将难以描述的弱限制单步容斥成相反的强限制
- 将所有情况（给出的图/答案情况）分为 存在某种结构 和 不存在某种结构，并先考虑其中一种情况（把分类当限制），然后将 存在/不存在 该结构当作前提解决接下来的问题（通常会导致某个较好的限制/结论）。
* [ARC153F] Tri-Colored Paths
环
- 对环的个数计数，可能出现多个环算成一个环， 考虑记录链的个数（一个链有两个插头，有 \(h, t\)），新加入点的算成 \(1\) 个链。
* Horrible Cycles
* NFLSOJ circles
不相交路径集计数
- LGV 引理，记得考虑某类路径集的 \((-1)^{t\sigma}\) 是否相同。
- 考虑若有些起点和终点可以同时不选，但权值与有多少条条同时不选有关，可以考虑插值法，连一条权值为 \(x/y\) 的边，然后插值求 \(x^{r}y^{c}\) 的系数。
- 在断环为链的时候注意是否成多个环（什么意思）。
* 数集合 NFLSOJ
* [AGC061F] Perfect Strings
计数 DP
一眼结论但不知道是什么结论的
- 不一定是多项式，不一定是多项式，不一定是多项式！！！
- 考虑整式递推！！！ 即 \(f_i = af_{i - 1} ^ 2 + bf_{i - 2}...\) 这样。
或者考虑答案的差分数组/除/对数数组。
* 序列异或 NFLSOJ
* CF gym 105170A
限制
-
对于不好处理的限制先考察并尝试简化限制，再分析操作，如果限制是“存在至少一个”这种，可以将对于限制而言没有意义的量（例如块间随意重排后限制，可以不管块间顺序）压缩掉/先不管，枚举对限制有影响的量然后算出这种状态（等价类）中有几种情况。
* [省选联考 2024] 重塑时光 -
如果是对于某个 \(x\) 求满足条件 \(p\) 的 \(y\) 的个数，考虑对于 \(y\) 进行条件 \(p\) 来尝试简化。
-
如果限制条件是多种类型的匹配，一定要考虑到重复计数的问题！！！实在不行先跑一部分预处理将匹配变成不会重复计数的，若是限制 \(x\) 有 \(a_x\) 个，可以考虑先把每种满足的方案的 \(b_i\) 用 dfs 等方式求出来，其中 \(b_i\) 表示满足了 \(b_i\) 个限制 \(i\)。
* CTT2012 麻将
优化转移
- 如果是 \(f_{S, i} = \sum\limits_{T\subset S} t(S, T)\sum\limits_{j} f_{S - T, i - j} g_{T, j}\) 这种，注意到这是卷积的形式，转换成多项式后 代入 \(n + 1\) 个不同值，拉插可以 \(O(n3^n + n^2)\)。
- 如果转移时要枚举两个量，考虑转移系数之间是否独立（相乘也可视为独立），如果独立，可以做分步转移，这样我们的转移可以少一个循环。
* MX-S6-T4 彩灯晚会
时间复杂度
- 考虑预先钦定某个值可能可以使复杂度减少（大 -> 小，减少无用状态）
* CFgym105336F - 考虑在用式子优化的时候可以把式子写一起，这样可能可以交换求和顺序降低复杂度
* CFgym105336F
* NFLSOJ 旅行的意义 - 如果 \(n\) 比较小（\(40\) 左右，或者 \(< 100\)），且存在状压 DP 做法，可以考虑跑一下有用状态和转移，可能可能状态数/转移数很少。
* 交换比特 NFLSOJ
= CF1466H Finding satisfactory solutions
简单递推
- 如 \(f_i = \sum\limits_{j = 1}^{w} f_j \times t_j\)（其中 \(f_0, t_{1\sim w}\) 已知），要求 \(+,\times\) 满足三律（？），可以矩阵乘法预处理 \(A^{2^i}\) 做到 \((w^3 + qw^2)\log v\)
* 简单的有标号有序完全背包 NFLSOJ
图论
最小链覆盖
-
给定几个限制，要求第 \(d\) 时刻 \(p\) 点上有至少 \(f\) 个标记，标记可以随时间移动，对限制考虑最小链覆盖。
-
偏序集最小链覆盖 = 最大独立集，图上可以最小割，树上可以树形 DP，线性规划对偶，把每个标记分别考虑转化为每个限制考虑。
* CF1023G Pisces
* NFLSOJ Cakes for Clones MLXIV -
对于有未知变量且满足可减性的，可以考虑拆点后由环来消去其影响，未知变量相当于出点和入点不互相限制。
* ARC144E
有向图邻接矩阵
-
邻接矩阵 \(A\)，有 \(A^{k} = A^{k + d}\) 时，\(d\) 为最小循环节时，\(d\) 等于图上每个强连通分量内部的环的大小间的 \(\gcd\) 的 \(\operatorname{lcm}\)。同时最小的 \(k\) 可以通过倍增求出。
拓扑
- 拓扑排序中，当某个点 \(u\) 出队时，对于当前任意 \(queue\) 中点 \(v\) 都没有 \(u\to v\)，注意某些时候一些是否只能当场判。
* CF1062F Upgrading Cities
竞赛图
- 完全图定向后是竞赛图，强连通竞赛图必然存在哈密顿回路，竞赛图必定存在哈密顿通路，可以通过从哈密顿通路开始，由基础环一步步构造得到。
* [POI2017] Turysta
分层图
- 分层图必然是 DAG，可以 \(O(V + E)\) 求单源最短路。
* 滑冰场 NFLSOJ
无向图 DFS 树
- 无向图任意边的两个端点在 dfs 树上都是祖先后代关系。
QOJ 3023 Winter Festival（考试的时候想到了但写不出来）
一部分树上问题
修改和节点相邻的边，询问树上路径
-
因为和节点相邻的边可能有 \(O(n)\) 条，尝试把对边修改变成对点修改，同时考虑将边的权值视为关于端点的点权的函数，考虑用 LCT/树链剖分 维护。
正权边带权中心的带权距离
即求 \(\min_{rt}\sum_u dis(u, rt)w_u\)
- 考虑对于每条边，带权中心即 \(v\) 一定在它的 \(max\) 那一侧，所以对答案的贡献是 \(d_{e}min{\sum w}\)。
* 重心 NFLSOJ
* CF gym 105170J
换根 DP
- 如果是动态根的，既可以考虑 LCT 也可以考虑固定一个根，每次特殊计算移动的贡献，这样只用计算一次而不用动态维护贡献，会方便一点，同时注意我们可以通过 选择特殊的根（直径中点/直径端点等）使得贡献更加便于计算。
树上两点距离
- 当然应该尝试点分治树。
- 也可以考虑括号序，将两点间的括号两两匹配剩下的就是路径长度，于是可以用线段树。
* [ZJOI2007] 捉迷藏
点染色限定同色点对下界 考虑按 BFS 序枚举
-
考虑 BFS 序的性质：
- 对于一个 \(i\) 和其之前的 \(j, k\)，有 \(dep(j, k) \le dep(i)\)。
- 对于 \(l = \operatorname{LCA}\{i, j, k\}\) 有 \(dis(j, l), dis(k, l)\le dis(i, l)\)。
按 BFS 序染色相当于限定了点对间的距离。
可以尝试去证明加入 \(i\) 时，对于所有 \(j, k, dis(j, k\to i)\le x\) 都有 \(dis(j\to k)\le x\)，即保证 \(i\) 的 \(x\) 邻域中的 \(j, k\) 互相都是 \(x\) 邻域（已加入的）。
也即加入的 \(x\) 对于其所有 \(x\) 邻域都是直径端点？因为最深所以最远？
有关树上连通块交集的一个结论
- 树上给定联通块集合，两两交集都非空，等价于存在一个公共联通块。
* [SNOI2024] 公交线路
* Bus Routes
代价
- 如果代价比较奇怪例如 \(dis(i, j)^{\frac{3}{2}}\)，考虑是否是一个凸函数，然后可以尝试求导。
* CF566C Logistical Questions
虚树
-
动态维护虚树边数：用 set 维护当前点 dfn 序的集合，（先加入 \(id_0 = id_{n + 1} = root\)），加入一个点将 \(prev(it), next(it)\) 取出考虑贡献即可。
-
虚树上的边是原树上的链，有一种奇妙的写法?
for (int i = 1, iend = V.size(); i < iend; ++i) V.push_back(LCA(V[i - 1], V[i]))
MST
- 唯一性，钦定一个顺序，多种最小生成树太难思考。
- 考虑出现环的时候去掉最不优的边或者“即将过期”的边。
* [JOISC2022] 复兴计划
树上二分
- 类似点分治的过程，最多 \(logn\) 个点。
* CF566C Logistical Questions
博弈论
轮 + 局
- 如果是重复直到某种状态的，先考虑最朴素的博弈论暴力：DP 取 max。
- 此时问题在于可能会有环，发现对于每轮，开始的状态一定的话接下来的期望也是一定的。
- 所以考虑对于所有操作维护一个 3 元组，分别为 \((-1, 0, +1)\) 的期望概率，因为平局方案不变，发现对于一整轮，这个三元组肯定存在最优关系（胜率/（胜率+负率）最大的）。
- 考虑可以二分这个值然后将平局视为这个值，最后判断开始的期望与这个值的关系，如果算出来的值偏大，说明其余的贡献高于二分值。
- 因为平局的期望 = 整局的最优期望，所以考虑固定（二分）整局的最优期望并判定。
* UVA12164 石头剪刀布
* 猜拳游戏 NFLSOJ
SG 函数
- SG 函数是下一个局面的 SG 的 mex，也是子问题的 SG 的 xor。
比较难考虑的贡献
根号分治/根号平衡
- 分成跟 \(> B\) 的有关的 和 都是 \(\le B\) 两种，前者考虑只有 \(O(\frac n B)\) 个，每次 \(O(n)\)，可以考虑预处理某些信息后建立 虚序列，后者直接 \(O(size^2)\) 即可。
* P8330 [ZJOI2022] 众数
众数/出现次数
- 众数实际上是限制了出现次数，一般 “出现次数” 可以与 根号分治 挂钩，因为出现次数少的数可以直接考虑出现次数，出现次数多的数可以直接考虑每个数，这样就出现了根号。
* P8330 [ZJOI2022] 众数
字符串
子串
- 如果和子串有关的可以考虑 SAM 上做，如果限定了 \(begin\_pos\) 考虑在反串上做，可以变成 \(end\_pos\)。
* [SNOI2020] 字符串
回文串
- 回文串记得考虑二分和 hash。
* 字符串 YZOJ
构造
子问题
-
考虑变成子问题，然后考虑如何拓展！
-
考虑子问题到全局的改变如何维护，不要一直想着贪心或某种一眼错的策略，子问题，子问题，子问题！因为子问题是构造的重要部分，可以有效减少思考内容和错误概率和思维难度！
* 岛屿 NFLSOJ -
考虑变成子问题不仅是 \(n\to n - 1\) 还有 \(n\to \frac{n}{2}\)。
-
排序时可以先考虑 01 的情况然后考虑分治拓展。
* [NOIP2020] 移球游戏
三角剖分
-
考虑去掉一个 \(d = 2\) 的点后的子问题。
构造方案
-
如果是要求通过某种操作要求从一个状态转移到另一个状态，考虑寻找“基本操作”，可能是由多个本质操作（给出的）组合成的，操作的特点是比较强。
构造二元二次函数(e.g.dis)间的大小关系
- 尝试构造多次二元函数(e.g. dis)间的大小关系时，可以考虑基于等于后 \(\pm\epsilon\) 的影响，因为这样的话，不会影响其余的大小关系，即独立性强的构造。
* ARC172D Distance Ranking
位运算构造
我也不知道叫什么
- 考虑把 + 的变成位运算，即钦定相加的两个数不进位，好处是位运算的阶段性/阶段独立性更强，更容易递归成子问题求解，同时考虑是否存在关键点可以必然可以调整至合法。
* UNR#7 比特迷宫
矩阵构造
- 对于矩阵填数，考虑某一维满的时候的构造解的方式找到充要条件/必要条件/充分条件，从而先填满其中一维。
* [SNOI2024] 拉丁方 - 行/列不重复的填数可以考虑二分图边染色。
* [SNOI2024] 拉丁方 - 对于某些点未知，某些点已知的赋值，考虑全部已知的情况。
交互
确定未知
- 如果是树的结构，可以查询某个点到某个连通块的距离和，可以考虑先随机确定根，然后 dep 差 1 的之间考虑，注意某个点具有极多儿子的情况比较容易出问题。
* 树 NFLSOJ
信息量/确定未知序列
- 考虑每次都基于全局，尤其是期望的题，注意得到的信息若并不是期望最好的，想的可能不是应该怎么用，而是它的本质是什么，即代表了什么，我们的每个决定都应该基于全局的所有信息的期望最佳。
* Permutation
确定未知排列长度，每次走 \(x, \bmod n\)
- 我们可以采用 BSGS，但是发现中间要走一些肯定不在上面的很费时间，可以考虑确定排列长度的较好下界，考虑先随机 \(T\) 个值，那么其中的 mx 期望是 \(\frac{T}{T + 1} n\)。
* Guess Cycle Length
子序列
- 构造有 \(a\) 个最长严格单调子序列时考虑进制而非因数，具体可以先假设 \(k\) 进制，在 \(k\times 1 + k\times 2\dots\) 的序列的基础上构造。
* NFLSOJ 月詠に鳴る
排列
行列式/积和式
- 和排列有关时可能可以考虑矩阵的行列式或者积和式，积和式不好算，但是若判断积和式是否为 0 的话可以考虑随机赋权后的行列式（Hash）。
* 轻舟已过万重山 NFLSOJ
计算几何
- 一条直线若经过 \(x\) 个点，则必须另外需要 \(x\) 条平行直线才能将其全部覆盖。
* 平行线 NFLSOJ
* CF gym 105170d
势能
- 可以考虑势能，通过哪个势能是符合要求的来反推做法。
* [THUPC2022 Final]rsraogps
网络流
最小割
- 先把一定不优的去掉，再考虑把选取状态改为从某个合法状态开始，一直在合法状态中调整，即选取 trans。常数真的很小。
* 锌粉 NFLSOJ
建模
-
我们应该将给定（固定）的东西作为源汇点，本题中干净毛巾和脏毛巾可以认为是本质不同的两种东西，所以我们可以认为顾客是每天得到 \(r_i\) 条干净毛巾，返回 \(r_i\) 条脏毛巾。
-
对于我们这个商店，就是每天可以获得脏毛巾，然后要求返回干净毛巾。
-
也就是说，源汇点应该是不变的东西？
结论
- 一个排列交换任意两个数，逆序对总数一定改变。
（LGV 引理） - 一棵二叉树，若将只有一个儿子的点压缩，则最终的树高 \(\le \sqrt n\)。
* CF1168D Anagram Paths - 问区间中有多少相同颜色对数，时间复杂度 \(O(n\sqrt n)\)
* [Ynoi2001] 冷たい部屋、一人
NP-Hard 问题特解
集合覆盖问题求方案数
- 如果点数较少或者如果点数较多但是可以分成相对独立的 \(m\) 个集合，集合之间不独立的点有 \(n\) 个，每次询问要求每类集合中至少选一个则可以集合并卷积快速维护，复杂度是 \(O(mn 2^n)\)。
* [省选联考 2022] 卡牌
二分图
二分图最小点覆盖等于最大匹配
- 先贪心，再建模可能可以得到更可做的模型。
* [USACO05JAN] Muddy Fields G
判定二分图是否可以匹配
-
不一定要跑 Dinic，若有一边的点数特别小，考虑枚举这一边 \(S\) 然后要求邻域满足 \(|N(S)|\ge |S|\)。此时 \(S\) 每个都可以被匹配。可以使用高维前缀和优化。
集合幂级数
- 如果集合异或卷积，形如 \(\operatorname{FWT}(1 + x^{\{u, v\}})y\) 的，考虑 \([x^S]\) 可能会有 \(= 1\pm y\) 此时可以枚举最终的 \([x^{S}]FWT(H) = (1 - y)^a (1 + y)^{m - a}\)（点乘！！！），计数有多少个 \(S\) 使得取到 \((1 - y)^a(1 + y)^{m - a}\) 且 \([x^{\varnothing]}]H\) 可能可以根据 FWT 的定义快速计算单点的值。
* 环覆盖 NFLSOJ
= 2022 集训队互测 环覆盖
贪心
- 对于对 \(x\) 做操作使得 \(x_i\ge y_i\)，等价于 \(y_i\) 做反操作使得 \(y_i\le 0\)，同时考虑操作具有限制，可以把对操作的限制转成对最终 \(x_i\) 的限制，即从某个 \(x\) 变成 \(y_i = 0(1\le i\le n)\)（如果代价和 \(x_i\) 的值联系紧密如 \(\sum x_i\)）。
* Add One 2
组合数
- 若有组合数相除求和，考虑拆成阶乘后转换形式使得分母固定并提取出来。
* CF1392H ZS Shuffles Cards
* 不朽之蜍 NFLSOJ
二元函数求平面矩阵上最值
- 若限定 \(x\le y\) 考虑把矩阵拆成 \([l_1, r_1], [l_2, r_2]\) 相同/相离后统计最值。
* 大战杀马特 NFLSOJ
还没有类似的多个用于归类的 Trick
二次剩余/快速判断完全平方数
- 考虑平方数的性质。从幂次为偶数入手的话你会发现分解绝对超时。从平方入手，既然是平方数那么一定存在二次剩余。
- 考虑二次剩余的性质非常好，用 \(p\) 个质数随机获取其二次剩余并记录（若能整除则判断其余因数），要求异或值为 0，因为在 mod 意义下，若为完全平方数则必为二次剩余，否则概率是 \(\frac 1 2\)？
* [SNOI2024] 平方数
维护多项式用于求值
-
如果是给定 \(a\)，要求对于不同的 \(x\) 快速求 \(\sum\limits_{i} \prod\limits_{j\in C_i} (a_i + x)\) 这种的，考虑维护一个多项式！
-
如果有模数且为 \(u^v\)，发现若 \(x = ku\)，则 \(x^v\bmod u^v = 0\)，所以考虑把 \(x\) 拆成 \(ku + b\)，用多项式的好处是可以改变点的贡献（原本为 \(1\) 现在变为 \(x + *\)）。
-
是多项式而不是进制，因为进制不够本质/简洁，要考虑的东西反而更多。关于如何在考场上从进制转换到余数：我也不是很清楚，考虑在想到一些相关的知识点和思路的时候考虑一下相似的知识点可能可以变得更可做。
二叉树上字典序
-
可以考虑给左边 (保证右边的第一个 > 左边的第一个) 或者 (保证先左边再右边) 两个情况所需的最小值后其余全部给左边，保证左边最小后剩下的给右边。
模拟
- 写的详细一点，清楚一点，分类分清楚非常重要。
- 对于模拟（可能需要优化的），先把暴力写出来，即可能出问题的地方先模块化的时候用暴力代替。
- 模拟可能需要转化成其他模型，这个需要注意写清楚，可以考虑用结构体封装，接口要对好。
- 模块化并不是万能的，有些时候不 good 的模块化反而会导致代码写不清楚！！！尤其是跳来跳去的这种。
- 写的详细一点，最好不要省略。
* NOIP2022 喵了个喵
* 网页 CSS(NFLSOJ)
平面最近点对/平面周长最小三角形
- 考虑分治，先按某个 \(x\) 分成两个集合，得到子问题的解后，再只尝试更新可能更优的点对，可以证明复杂度为 \(\mathcal O(n\log n)\)。
麻将题
- 看懂规则，其实应该可以做的。
- 如果限制比较简单，其实并不难。
* 拉密 NFLSOJ
一些小 Trick
观察
- 某些题目可能可以通过观察大样例得到一定的提示，但是想通过观察（大）样例直接推出结论就像企图通过观察素数螺旋发现推出线性筛一样不太可能。
二进制分组
- 不太容易想起来的技巧，思想是对于一个集合计算两两不同的最值时，考虑枚举对答案贡献的两个元素重新标号后二进制意义下不同的位置在哪。
树套树 \(\to\) cdq 分治
- 如果能用树套树的考虑能不能用 CDQ 分治优化，会好写很多。
* 歌剧演员 NFLSOJ
判断特殊情况
- 注意想到哪些不可能/特殊的情况可以先判掉，简化题目的条件和情况，有可能存在除了特殊情况外的正解。
* [ARC153F] Tri-Colored Paths
补丁
- 如果代码挂了，可能是错了一个小点，比如某个情况没有考虑到，说不定可以打个补丁？总而言之，不要放弃希望。
* 超命运树 NFLSOJ - 跟子序列有关的限制，如果发现了对相邻元素的限制，而这是必要不充分条件，可以考虑两两限制 \(|i - j|\) 和 \(|a_i - a_j|\) 的关系。
* NFLSOJ 相似数列
二维数点
- 二维数点需要分析清楚情况，把过于具体且繁琐的自然语言限制转为用数学语言/代码表述的便于可能更加便于套路优化的形式。
* 刷墙 NFLSOJ