这就是它 tricky 的地方了。

sim_sugar · 2022-10-19 20:00:56 · 个人记录

但是没有顺序，见到什么写什么

1. 注意观察形如最大化最小值，二分答案，然后找判定性问题的切入点，例如 “放 K 个使得（二分的答案）” 可 转为 “使得（二分的答案）的最小数量是否 \le K”，然后贪心满足条件，判断贪心的条件时又进行了树形 \text{dp}，对此应具有思维连贯性。
2. 分块尽量避免复杂度 \sqrt n 后面跟东西。可以考虑手搓 不支持 查询但是 O(1) 修改且大小 O(B) 的 树形结构 用于暴力重构块；根号平衡一般会用在不止一处，注意分析结构的大小；可以考虑离线处理每块对每个询问的贡献，以此减小空间复杂度。对于带插入型分块，有两种自然想法：块链和根号重构，但是一般情况下 使用根号重构。树形结构的插入要讨论清楚，对插入但未重构的点记录祖先。
3. 对区间值域上每个数的判定，考虑能否合并、快速判定一个集合是否满足，然后分析错误率，随机常数个子集 进行判定。对于不带修、区间 是否存在 一种子序列的判定（且这种判定与 全局给定 的一些东西有关），考虑 贪心构造 每个位置结尾（或开头）的子序列，记录对应的位置，转为 \text{RMQ} 问题解决；若涉及形如 “前一个……” / “后一个……”，可以考虑建立树形结构，离线回答询问。
4. 有重复贡献的概率 \text{dp} 一般通过高斯消元，但是形式较为固定（稀疏矩阵）可以手消做到 O(n)；若形如区间询问这类概率 \text{dp} 可以 移项 变成 k 阶递推式从而使用线段树维护区间矩乘 \rm tag 做到 O(qk^3 \log n)。带修区间询问满足限制的填数方案数等，观察到题目给出的限制是矩阵形式，也可以考虑设计 动态 \text{dp}，用线段树解决。
5. 范德蒙德卷积 \begin{aligned} \sum_{i=0}^{n}\dbinom{A}{i}\dbinom{B}{n-i} = \dbinom{A+B}{n} \end{aligned}，从 组合意义 上讲是一种对方案进行拆分/合并的技巧（分为两部分后各选各的）。真的很有用，不信去看 CF1747E（题解），虽然这个破 *2900 我们想了几个世纪。
   Upd：上指标范德蒙德卷积 \begin{aligned} \sum_{i=0}^{n}\dbinom{i}{A}\dbinom{n-i}{B} = \dbinom{n+1}{A+B+1} \end{aligned}。
7. 序列先按 2^k 分块再相邻两块进行操作，最后询问，考虑贡献是否独立，能否 交换操作顺序，然后离线后按一定顺序枚举 k 进行修改（注意修改能否写成矩乘形式）。
8. 计数类 \text{dp} 多用刷表，注意 转移的顺序。容斥时可以针对某一部分进行，如有一些不确定的和一些确定位置的障碍，对行走方案计数，确定位置的障碍 \text{dp} 时绕过，然后 钦定经过 k 个不确定的障碍，则容斥系数 (-1)^{k}。
9. 拓扑排序的一个性质：任一时刻队列中的点不存在可达性关系。（来自 Walking_Dead 的博客。虽然我没有做这题，但是翻到了这个题解（？？？ 好现在做到了。
10. JOISC 2019 D4T2 这类题，找到判定断开每条边是否合法的标准，然后只保留不合法边，还是会形成树形结构，然后结合树论、贪心、\text{dp} 解决即可。对于合并树上同颜色的所有点的路径为一个大点，可以使用只路径压缩的并查集，直接上跳合并（说得不太清楚，可以回去看代码）。
11. JOISC 2019 D2T2 给到的 70：多将问题形象化地放到平面上考虑，可以往最优化路径上转化，往往能通过找最优路径的形态简化问题；观察 \text{dp} 转移的分层性；观察产生影响的决策点个数，以此找到优化切入点；转移形式包含前缀 \min/\max 可以考虑维护差分数组；考虑分开维护合在一起不好维护的部分；一次成功的转移会影响一段区间的情况下考虑各种数据结构优化。
12. 典题：旧词：树上一眼不好求，看了很多眼还是不好求的东西，考虑将贡献差分。固定形式的差分可以只维护系数。
13. 终于用上了。\max(a,b) = (a+b+|a-b|)/2，\min(a,b) = (a+b-|a-b|)/2，形如总答案与所有子段最大值/最小值有关的问题，如果绝对值这部分比较好维护的话，可以考虑这样做；对于随意进行若干次多种操作求最优方案，先构造一种最优方案；对于求所有子段的最优方案步数和，考虑拆式子分开维护，并且对于每个位置上与别的位置无关的信息，考虑直接算在答案里的贡献。
14. 典题：回滚莫队在复杂度允许的情况下可以随便滚来滚去，但是要注意左右贡献尽管可以分开算，但是必须保证算左边的时候右边对左边的贡献正确。（可以回去看链表的做法。）分治之后补。
15. 68861641，91815541，1145141923，1145141999，现在 1e9+9、998244353 属于人见卡，怄火。
16. 看起来很 \text{dfs} 的东西可以考虑预先求出每个状态下面可能到达的状态数，通过这个进行剪枝。（估价函数？）
17. 大恶心分讨题就不要做了，直接写暴力看其他题（。
18. 难搞的数据结构题还是从子问题角度入手（如 计几瞎暴力 一题），看不出来所有操作加在一起怎么做就尽力去设计 优秀的、独特的算法解决只有其中一部分操作的问题，然后可以尝试从这些算法出发扩展到原问题。就当作想不出来的时候找尊严做法也行。
19. 转化的方向需要更活络，比如一个序列枚举每个数处理时如果做到 O(cnt_x \text{polylog}) 那么整个问题复杂度也是对的。理性分析每个操作的复杂度，不能就感性。
20. 合理合并两个计数限制相关的序列使得转移更具有规律性。这个 “放到一起排序” 的 trick 和下面的 “插入法统计排列方案” 都相当于赋予当前 \text{dp} 正在考虑的元素一个和已考虑元素之间的偏序关系，从而使得状态设计更简洁，转移更方便。
21. 设计 \text{dp} 状态可以 使用插入法构建排列，从值域离散化地考虑，尝试忽略元素大小差异（忽略形态只记录数量，注意形态不只是指形如 “连续段长度”、“形成的环大小”、“连通块……” 这类单个元素本身的性质，也可以是这些元素之间的关系，如 段间距离）。
22. 矩阵构造考虑给每条对角线制定相同策略。
23. 判定性问题也可以转化为计数（加强问题限制）。
24. （我觉得用不上）考虑使用信息论方法分析获得一个最优化问题的上/下界，然后尝试 构造方案达到这个界。如果有小天才像这题一样模数给的是 p^{k} 要算组合数，考虑把 p 的次幂单独算（对暴力算和预处理都适用）。

    auto C = [](int n,int m){
        unsigned t1=1,t2=1; int cnt=0;
        while(m){
            int v1=n,v2=m; --n,--m;
            while(!(v1&1)) v1>>=1,++cnt;
            while(!(v2&1)) v2>>=1,--cnt;
            t1*=v1,t2*=v2;
        }
        return cnt>=32?0:t1*(1ll<<cnt)*inv(t2,p);
    };

Upd：但是 分析上下界的式子来猜测构造方案 不失为一种方法。

25. 观察是否可以舍弃不必要维护的地方从而降低修改量。
26. 区间询问 “是否可以选出…… / 每次选出……，是否可以操作 x 次” ，考虑 瞎猜贪心，找到最优方案，证明可以先感性理解。
27. 基于比较的贪心（\texttt{Exchange Argument}）：设计状态，然后找到每个元素在状态间转移时产生的贡献，比较这个贡献。（注意这里的状态不只有 “不选 \to 选”，也可以是形如 “选 i 次 \to 选 i+1 次”）
28. 考虑观察相邻几项的转移方程的相似性从而实现直接递推 / 归约成另一个问题。深奥的整体 \text{dp}：打表观察两个相邻层的 \text{dp} 数组以找到转移规律，从而通过直接修改整个数组来转移。
29. 有操作次数限制的构造题，如果有方案但是时间复杂度不太对劲，写完后可以打个表分析一下离上界的距离，可以通过 复杂化一部分构造的步骤 来使得构造方案整体更简单，从而降低时间复杂度。
30. unordered_map 内部没有针对 pair 或结构体的哈希函数，需要自己手写。

struct PairHash{
    template<class T1,class T2> size_t operator ()(const pair<T1,T2> &a) const{ return hash<T1>()(a.first)^hash<T2>()(a.second); }
};

31. 分治的复杂度平衡有两种形式：1. 单层开销大，但层数少；2. 层数较多，但设分出的左右区间为 L,R，单层可以做到 \min(L,R)，则复杂度类似于启发式合并。如果是第二种，不要用 auto，想要减少码量应当使用 inline 定义成函数。一个猜测可能的原因是每次调用分治时都会重新定义一次 lambda 表达式，导致跑得非常慢。
32. 判断一个数是否存在某个质因子次数大于所有给出的数中该质因子的次数（值域很大）：对每个数分别求 gcd 后对所有 gcd 求 lcm，判断是否 \lt x。（这个不需要证明吧）
33. 对于竞赛图一般考虑缩点后的有向链上解决问题。
36. [Ynoi2003] 铃原露露（支配对）：考虑将区间判定问题转化为已知判定对区间进行修改的问题，即将即时需求的判定转化为若干对它产生贡献的修改的叠加；扫描线可以考虑维护每个位置作为左端点对应的答案；考虑找到（大多数时候是）O(n^2) 或者更多的需要进行操作的元组中哪些是有用的，也就是寻找支配关系从而减少有效元组个数。
38. 数据分治。博弈论对于不好推的部分考虑记搜（\text{dp}）预处理。
39. 贪心时考虑如何将混乱邪恶的操作转化到一个 固定且方便 的形式上。
40. SG 函数一般是有 不那么长 长度小于按定义求解的复杂度的循环节的！
41. 弔题：每次只改变一位的位运算（\text{popcount}(x \oplus y) = 1） -> 线段树结构；多想想动态开点线段树上的暴力操作，分析复杂度可能是对的。
42. 倍增，优化 dp。
43. 任何有单调性的量都可以作为二分的对象（如果这个量还跟答案呈单调关系那么多半是这么做的）。
44. 大力剪枝 1s 能跑 1e11（？）。
45. 注意给出的限制能否变成每个元素分别对答案的上下界限制。
46. 弔题：能列方程的可以多列几种出来，尝试用 \texttt{exgcd} 直接求出答案；能转化成同余方程的就上 \texttt{CRT/exCRT}。
47. 对于区间答案与区间左右端点处信息有关的情况首先想到线段树维护，每个节点存最左最右信息和区间答案即可（GSS 模型）。（一般来讲这种题分块都比这个难写）
48. 可 撤 销 并 查 集 路 径 压 缩 /fn。
49. 下降幂和普通幂的转化：\begin{aligned} x^{\underline{k}} = \sum_{i=0}^{k} (-1)^{k-i} {k \brack i} x^i \end{aligned}。
51. 区间覆盖，且单点覆盖次数 O(1) \to 在覆盖同一点的区间之间 连边。
52. 约束转化为不等式，如果涉及的元素较少，考虑差分约束或 2-SAT。
53. 连乘可以考虑取（离散）对数之后变成求和，然后卷积算。
54. 寻找答案经过的不动点从而分治 / 扫描线。
55. 不妨尝试转化分析的对象（比如一张网格图中，分为几类满足性质的格子，可以从数量固定 / 最少的一类开始分析）。
57. 按行转移的状压 dp 通常可以通过加一维按位置转移将复杂度从 O(B^{2k}) 降低到 O(kB^k)。（类似于轮廓线）
58. 如果 dp 的转移类似于一边是上标固定的组合数的卷积，可以把 dp 数组看作多项式，经过换元（例如 y = (1 + x)）将卷积变成平移。