做一个纯粹的容器

· · 生活·游记

背景：NOI2025 Ag 退役

起因是，二月月考考试间隙无聊，听别人说起 WC2026 的题，自己有兴趣做了一下，做了三天发现自己全都会了。

然后我觉得，像是找回了自我一样。

突然发现，自己已经太久没有为了某一道题而冥思苦想，太久没有感受到那种，额，不恰切地说，"思而不学则殆"的感觉。

上次这样还是在 NOIP 之后，嘴巴 VP 了这场，大概 1h 会了前两题，1h 会了 T3 的 48 和 T4 的 40，给我留 2.5h 写代码，于是就有 288。甚至能排到我们学校的第二名。于是颇有感慨，感觉自己，"吾虽老矣，箭矢犹锋"。

之后想出 T3 是一个树剖后，甚至还心血来潮偷跑去机房写了一个 O(n^2m) 的费用提前计算 dp 的做法。

之后 T3 会了一个树状数组优化的 O(nm\log)，T4 会了一个 O(nq\log)的暴力，因为学业压力和时间紧就没继续想了。

不过，很高兴地见到，去年noi，noip，今年 wc 中的题，感觉质量真的大幅提升。这些题目，实实在在考察思维，每道题都有自己的设计感，像是对着问题想出做法，而非对着做法编问题的结果；并且弱化了代码，并非我们经常在训练中见到的，很快发现是一个套路，会做之后，写起来一坨的那些题。

回想起有教练跟我说过，一道题，即便做法美妙，如果不能从中汲取到一些方法论的东西，那这道题就没有任何价值。

功利而言，说的不无道理，这样的题于水平进步无用。但其实，一道题，尤其是那些高水平的题，我认为，将其当作训练的资料，真的很玷污它。

要将它当作一个艺术品来看待。

或许我站在这里这么说有些大言不惭、冠冕堂皇了。毕竟题目的区分度，部分分之类影响选手成绩甚至前途的东西，都与我不再有关系。

但也正因如此，才能够让人再次体会到，做一道题，不带任何其他东西的纯粹的快乐。

这使我联想到，中国人与西方人对于山水的态度之不同——中国人对山水有纯欣赏的态度，人在山水中会有怡然自得、与自然融为一体之感；西方人则不同，常把山水当作自己要攻克的难关。这就是为什么，中国作品的意象中，山水往往给人以宁静闲适之感；而西方经常是穷山恶水，还经常往山洞里装一个巨龙之类的东西。

做题亦是如此，在功利的情况下，我们看到的往往也是“穷山恶水”，往往认为题目强如怪物，拼尽全力无法战胜。这本身是种正常现象，无可厚非。

记得我在 NOI 闭幕式听到 dzd 总结题目时旁边人一直在问候出题人的母亲，非常趣味。

其实感觉，这场 NOI 是我打过的，题目几乎最好的比赛了。用欣赏画来比喻，一次画展为了雅俗共赏，有 2 张儿童简笔画，剩下 4 张中有 3 张都是风景画，还有 1 张是没有谁能看懂的抽象画，这就会使不擅长风景画鉴赏的人非常难堪。所以说，问题在于题目板块上比较重合，或者说部分分安排稍欠合理，而非题目质量不足。

OI 啊，能纯粹欣赏题目，喜爱算法的人，已然甚少了。就像空洞骑士中没有被瘟疫感染的角色，已然少之又少。

究其未被感染之原因，无非就这几种：第一，螳螂领主的部落，那里因为训练极其严苛而未被感染；第二，蜂巢内的小蜜蜂，它们完全听从首领的意志，没有自己的思考，还有小骑士，也是听从玩家的控制而没有自己的思考；第三，格林亲族，它们有自己的仪式与追求。

但这三者于我们，都不甚现实。毕竟，没有人想在惨无人道的压力中存活，没有人想完全听从于他人或领导的安排，更没人想在邪教组织中失去自我。

留给我们的，只剩下最后一条路，那便是，以一颗纯粹之心活在这世上。

看啊，东巴在王国边境以好奇之心探寻圣巢的缘起，古董商人以求索之志研究圣巢的历史，防御者以不屈的希望守候在下水道的角落，小虫米拉以热爱之心勤勉劳作于十字路于水晶山峰的交界，天真的小鸵鸟在王后驿站默默吃草。

它们都以一颗纯粹之心活在这世上，无欲无求，方能不受瘟疫之影响。米拉的感染，是小骑士导致的十字路感染的象征，亦可能根本是因为它自己在工作中失去了自己的纯粹之心。

世间最美好的事情，便是能够以纯粹之心，追求自己纯粹的理想。

做一个纯粹容器，做一个装得下一个纯粹之心的纯粹容器。

WC 题目思路解法。

T1就是给出一个直觉，+1 一般来说在 *2 之前操作是更优的，除了补齐位数的过程。

那考虑将两个数二进制高位对齐，将较大数定为 x 的话，x*2 一定是不优的，因为 *2 会使之后的 +1 变难，而且 x 也一定不需要补齐位数。

所以我们枚举 x 的 +1 操作导致的最高的进位的位置，讨论一些情况发现之后不可能再给 x 进行 +1 了，然后使用一些位运算 O(1) 算出 y 需要的步数。

总复杂度 O(T\log V)，被卡常不管。

T2 先进行一点转化，变成花代价放一堵斜 45 度的墙，要求不存在一条一直向斜上的路径经过 <k 个墙。

斜着有点阴间，先把它转直，然后把碰到边界的那些墙延伸到无限远。

嗯，优美不少。

然后发现 k=1 是个最小割状物。

又是一个平面图，于是考虑转成最短路。

分析一下发现，我们可以让一堵墙的终点连向其所有左上方的起点，这样就对了。

于是可持久化前缀和优化建图，就解决了 k=1，复杂度 O(n\log^2n)。

发现图中只有 O(n) 条非 0 边，于是可以少一个 log。

好像会有一堵墙被两条路径借用的情况。咋办呢？ 对于一堵竖墙，有意义的情况，进来要么是横墙交过来，要么是从某竖墙掉下来；离开要么是横墙交走，要么是掉下去。 讨论所有情况发现两段路径共用一堵墙，它们路径不交，一定可以调整成不共用的情况。 于是把最短路改成拆点费用流就 ok 了。总复杂度 $O(kn\log^2n)$。不知道原始对偶的情况下能不能也少一个 log。 T3 一看，好有趣。 仔细想想发现我啥都不会。 那尝试弱化条件，我就不要求增删之后是一棵树，能怎么样？ 好像还是没有头绪。 那我也不要求保证删除的边存在呢？也就是这对铅笔橡皮随便画，不用考虑别的铅笔补上了现在没有的边。 诶？好像有点感觉。 发现一对铅笔和橡皮，最终画出的轨迹，形如若干个环和一条链，其中有些边被删一次，有些边被加一次。 那是不是只改变了链上的两个端点的度数奇偶性？ 哦，原来如此。 大胆猜测像欧拉路径判据一样，度数差值为奇数的点的个数除以 2 就是答案。 于是先考虑把要变成的树进行些操作，使其奇偶性都对两个，把这些操作放在末尾。 这个简单，只有两个点都是叶子且连的父亲相同的情况要特判。 接下来考虑怎么在奇偶性正确的情况下构造。 取出一个新树中的叶子，要把它在原树中也搞成叶子，无非就是删一些边，再加一条边，也可能不加。 那随便尝试尝试，注意铅笔橡皮可以无代价交换位置，不难构造出方式，注意你的方式还需要最终铅笔橡皮处于同一个点，以便回收利用。 然后在原树和新树中删掉这个叶子，一直操作下去。 操作数应该不会超过 $O(n^2)$，没有问题。 upd：又想了几天，T4会了一个 $O(4^k)$ 的做法。 让我求网格图拓扑序对 2 取模的结果，这我哪儿会啊？ 于是考虑我会什么。 我会外向树拓扑序计数，直接阶乘除以 $siz$ 之积就行。 我会有向树拓扑序计数，容斥转成外向树森林就行。 于是还考虑容斥。 将图容斥成上面横线向右，中间向下，下边横线向左的标准型。 什么？你问我为什么这么容斥？因为这样之后去除无用边，剩下的是有向树森林啊。这看起来就更可做了。 然后又发现，如果容斥完是多个有向树，那带一个组合数，将这个组合数用 lucas 拆开，发现一定是 2 的倍数。 所以可以发现容斥完一定联通，且答案与有向树的方向无关。 于是我们考虑对这个树的形态进行 dp，状态记一个 $siz$ 乘积中 2 的幂次，应该可以得到一个非常丑陋的高次多项式复杂度做法。 细细思索一下，发现 $2^i$ 的倍数必然出现 $2^{k-i}$ 次，不能有浪费。 于是有一个判据就是，这棵树存在一条边分成两半，大小相同，两边都可以继续分，以此类推。 然后就有一个 $O(k8^k)$ 状态 $O(2^k)$ 转移的dp。 好像很难继续优化了。 于是考虑换一个判据。 观察到一定是二叉树。 树一条链一定可行，那我们考虑什么样的子树合并也可行。 手摸一些情况，发现两边 $siz$ 加起来不进位就能保证不浪费 2 的幂。 于是换一种 dp 方式。 设 $dp_i$ 表示前 $i$ 都联通，一次转移一段连续的上下都有限制的边，再枚举一下那个竖直限制边的位置即可，预处理区间的系数可以复杂度 $O(8^k)$。 我们发现几乎所有情况系数都是 0，这是为什么？ 我们先只容斥上下的边，中间的不容斥。 发现中间如果有形如向上在向下左边，说明一定有环，无解，不做这种转移。 其次，如果有多个向上，我们容斥非最靠左的向上时就会出环，也不考虑。 所以，只需要容斥最左边的向上即可。 分情况讨论一下，全向下就做一个 n 形的转移，全向上就做一个 u 形的转移，先是向下然后向上就在分界的两个位置做H形转移，复杂度 $O(4^k)$。 n 形和 u 形可以动态高维前缀和优化，H 形还不会。 ***