NOI-WC2025线上营员游记

· · 生活·游记

由于洛谷文章区投稿至官方合集后再修改可能会被移出，但后续可能会增加或修改游记内容，所以建议在这里查看各版本游记 QwQ。

（（有史以来排版最混乱的一次（（不不不 THU/PKU WC 游记同样十分混乱

（（为什么会有这篇游记呢？

省组织单位：很遗憾，我们决定让一个提高组比你低十分的同学参加。因为你的报名时间是 11 月 24 日，而他的报名时间是 11 月 23 日 23 时前。

但显然，真正的报名截止时间是 11 月 26 日 13:00。

于是这下连铁牌都没有啦！（（

NOIWC 2025 没了？不不不！没有条件就创造条件！手动给自己创造个加差旅费 0 元的线上营员出来！

Day 13（01-29） 比赛日

发现洛谷上有题了，于是 22:52 上班，注意到难度为绿黑紫（（嗯嗯！就当没看到！就当没看过榜（（

读完 T1，顺利获得 n \le 1 的 5pts（bushi）。简单思考注意到似乎先分配完所有普通猫粮再分配优质猫粮比先分配优质猫粮更优。注意到 n \times m = \sum_{i=1}^{i \le n} (a_{i} + b_{i})，于是每只猫所得到的猫粮均不可以出现溢出。

想了 15 分钟发现似乎对于一种分配普通猫粮后的方案，对获得普通猫粮后没吃饱的猫中获得猫粮最多的一只，如果优质猫粮中最大的那一袋分配给它后出现了溢出，似乎一定有一种可能将所有分配给它后不会溢出的猫粮都分配给其它猫的方案。于是这种方案一定不可行。

但注意到这似乎是必要不充分条件（（

此时读了一下样例，发现样例解释十分有道理。如果按照先分配普通猫粮的方案似乎确实无法得到任何可行方案。

糖丸了！糖丸了！糖丸了！

注意到虽然我们无法在喂食之前得知一袋优质猫粮会给哪只猫，但喂食后我们是可以得知的。

又想了十分钟注意到每袋猫粮的质量都是 1 到 m - 1。于是每只猫至少要吃两袋猫粮才能吃饱。同时由于总共的猫粮数为 2 \times m，于是每只猫能且仅能吃两袋猫粮！

（（感觉要是正式赛场上以我的心态很难在半小时内认识到这一点（（

于是对于特殊性质 B，每一袋猫粮都有唯一确定的一袋与其相匹配。注意到两袋都是普通猫粮的匹配直接分配就可以，对于一袋普通和一袋优质的匹配则是先分配优质猫粮再给这只猫对应的普通猫粮，而对于两袋优质猫粮的匹配则需要放在所有其它匹配之后。简单思考发现对于两袋优质猫粮的匹配最多能有一对，如果出现两对及以上则无法保证一定可行。时间复杂度 O(T \times n)，顺利获得性质 B 的 35pts。

发现对于其它的分数就是尽量减少优质猫粮间的匹配，于是首先贪心的对每一袋优质猫粮，在普通猫粮中寻找匹配。注意到剩余未能成功匹配的优质猫粮数量为偶数袋，于是可以得到当剩余未能成功匹配的优质猫粮数量小于等于 2 时存在一定可行的方案，而大于 2 时则不存在。时间复杂度同样 O(T \times n)。此时开考 42 分钟顺利预期 100pts QwQ~

签到成功 QwQ！

（（但是暂无数据我也不知道对不对 qwq，而且如果正式赛场感觉自己大概率会想不到（（

看 T2 nim 游戏...但我不知道 nim 游戏的最佳策略哇 QAQ！说好不会考博弈论呢 QAQ！

（（但他好像给了最优策略喵 QwQ~ 虽然我不会证明

53 分钟时读完 T2，发现其实和博弈论没有任何关系 QwQ！

发现对于点 1 时有且仅有把小的那一堆增加至大的那一堆这一种方案，预期获得 4pts（（

发现对于点 2 到 4，dfs 每一位增加至多少即可，预期获得 16pts（（

思考至 65 分钟时无果，决定先读 T3。发现特殊性质 A 时一定可以 l=1 且 r=n。于是枚举攻击次数，再仙丹树计算收益。注意到一些攻击次数的枚举是无意义的，于是离散化。总时间复杂度 O(n \times \log n)，预期 5pts（（

（（这就是 WC 么 QAQ！怎么 5pts 都这么艰难！这就是 WC 么 QAQ！怎么 5pts 都这么艰难！这就是 WC 么 QAQ！怎么 5pts 都这么艰难！

继续思考到 89 分钟时想到一个神秘区间动规做法，但发现时间复杂度直接 n^3 \log n QAQ！并不能获得任何额外分数（（

艰难思考到 115 分钟时终于想到神秘仙丹树做法可以 \log n 的维护增加或减少一个人后的总贡献。于是暴力枚举开头，再从左到右顺序加入每个人，就可以总共 O(n^2 \log n) 预处理出直接选择每一段区间时的总贡献。于是之后动规的时间复杂度顺利降至 O(n^2)。总时间复杂度 O(n^2 \log n) 可以通过 2 至 8 点，总预期 40pts QwQ~

总预期 100 + 16 + 40 = 156 QwQ，如果没看过榜我大抵会自我感觉良好（（但看过榜的我意识到还差 7 分才有 Cu QAQ

（（感觉如果是去年差 7 分铜我大抵是直接跳了 QAQ（（嗯嗯其实今年我大抵也会跳（（于是今年叫什么楼？

挺好挺好没在绍兴丢人（（

（（怎么感觉自己游记越来越无聊了 QAQ~黑历史系列了属于是。

一把子怀念力！希望 APIO 能去吧 qwq~（（