Note

其实是兔子收集的各种下饭操作与名菜食谱。（

零·策略篇

多校 NOIP 2021.11.05:

这个真的是，我每次打毛毛虫剖分都是 rush 状态 qwq。像这种 已知代码难度大、不便于调试的算法，尽量在考试前期发现并制定策略。如果不幸在后期才看出来，必须做好止损工作，例如完善其他三题（包括最终检查，freopen 等），若本题已经写了部分分，则另开文件 rush。调试过程中千万不要慌，骂自己几句然后冷静下来，这种长难代码一定要理清思路，写的时候就不要给调试过程挖坑。

By the way，注意若有多个代码模块逻辑上高度相似（比如复制粘贴改变量名这种），一定小心有区别的地方；若在一处发现了 bug，立马考虑其余几处是否有相同 bug。

壹·读题篇

「CSP-S 2021」「洛谷 P7914」括号序列:

我谢谢你。

「多校联训」挖掘机:

贪心显然，每次给定 (K)？那就根号分治……Woc 根本过不去！自闭一个小时发现 (K) 是常数，麻了。注意多次询问是否共用常量参数。

贰·思路篇

「多校联训」超级加倍:

出于对点分的热爱尝试将二维偏序优化至线性.jpg

「多校联训」石子游戏:

瞬间推出 SG 函数有取模，瞬间忘记取模转化起手式：(xmod y=x-lfloorfrac{x}{y} floor y)，并且整除结果是可枚举的。这样才能进一步转化。

「多校联训」黑客:

有的题，真就该傻瓜题用傻瓜方法。热烈祝贺 OneInDark 玄学数论分块嵌套 + 莫比乌斯反演 + 剪枝完成了暴力能过的题目！

叁·实现篇

「WF 2011」「BZOJ #3963」MachineWorks:

函数形参的类型推导（eg int func(auto a)）是 C++20 标准的语法。

「多校联训」第 k 大查询:

std::set::iterator 自加最坏 (mathcal O(log n))。

「多校联训」树上路径:

换根 DP，因为删除一个儿子后还要求最大和次大，所以得维护前三大，但是判断细节就很细节（？）调了老久。诸如此类几个东西比大小，反复检查，举例验证，出 bug 时优先核验！

「洛谷 P5903」「模板」树上 k 级祖先:

「名菜警告」：记得判 (u) 的零级祖先为 (u) 自身，否则直接用 __builtin_clz(k) 是未定义的。

「OurOJ 9865」路径中位数:

点分治，分治中心的贡献没有加在桶里。

「多校联训」肯德基:

有一个 if 用于剪枝，但在极限数据时只会变成常数。为了卡常把它删掉了，而没想到小数据也会因此跑满，全部 T 飞了 qwq。

「UVA 10735」Euler Circuit:

(n) 打成 (m)！(n) 打成 (m)！你他娘不是 (m) 打成 (n) 就是 (n) 打成 (m)！

「CERC 2016」「洛谷 P3679」Bipartite Blanket:

Two-pointers，其中一个指针扫到 (-1) 就不扫了，但其实这其实是意味着接下来一整个序列都合法。

「CSP-S 2020」「洛谷 P7077」函数调用:

(n,m,q) 反复手误，你再敢不造 (n,m,q) 互异的数据检查就去死吧。（

「NOI 2016」「LOJ #2083」优秀的拆分:（By OneInDark）

「名菜警告」：我们写 SA 一般有个 cmp 函数：
```
auto dif = [&]( const int x, const int y )
    { return id[x] != id[y] || id[x + w] != id[y + w]; };
```
x + w 会越界……吗？并不是，若越界，id[x] != id[y]……吗？还是不是，当 x == n - w + 1，有可能刚好越界到 id[n + 1]，一般数组会有冗余空间所以不会 RE，但多次后缀排序一定要清空到 (n+1)！！！

错误示例（By OneInDark）：WA submission。

「CF 113D」Museum:

高斯消元，EPS=1e-7 忽略一些系数导致巨大精度误差。在确定不影响复杂度的情况下，实数消元还是无脑全部枚举一遍吧。

「CF 1368G」Shifting Dominoes:

求矩阵并的那种线段树的 pushup:

inline void pushup( const int u, const int len ) {
    // cnt[u] = cvr[u] ? len : cnt[u << 1] + cnt[u << 1 | 1]; // RE.
    cnt[u] = cvr[u] ? len : len > 1 ? cnt[u << 1] + cnt[u << 1 | 1] : 0;
}

「CF 321D」Ciel and Flipboard:

思考一个结论的时候把“平移相等”顺口说成“对称”，代码写出来真写成关于对称轴对称了……
(a_{i,j}in[-10^9,10^9])，四个加起来没开 long long。
每次测样例必须所有样例同时通过；检查代码时检查细节、逻辑思路的正确性。

「CF 1580C」Train Maintenance:

根号分治，一种情况在差分，一种情况没差分，写着写着就乱套了。任何分类求解的算法一定要用同组数据测试不同情况！

「CF 1598F」RBS:

可持久化线段树写成动态开点完全没有持久化线段树。

「多校联训」大鱼吃小鱼:

瞬间看出标算结论，瞬间想出标算，一经思考：“我草这 treap 被 split 成这么散怎么还原？”痛失一百分。有时候平衡树非常吻合思路的进程，但实现时可以考虑权值线段树作为细节少、易调试的数据结构。
线段树二分，if (l == r) 这个 statement 里不要忘记就算 (l=r=1)（整棵树左端点）也是有可能不在二分上界里的，注意判。

「UVA 1592」Database:

清空了，但没有完全清空。

static std::string str;
while (...) {
    if (...) { do something with str; }
    else { str.clear(); }
}
do someting with str;
// str.clear(); !!!

「多校联训」树:

有一个东西 h，我把它换成 rh，并重新定义了 h 的含义，然而某处本应是 rh 的地方没改……