2025NOIP 游记

Pyrf_uqcat · 2025-11-30 03:53:38 · 生活·游记

省流：t1 好像挂了。

警示：全文全是废话，不知道在讲什么。

开赛 2h 没拿分。如梦。

调试 10min 设备，大致浏览了 T1。第一眼感觉 T1 很一眼，好像背包直接乱搞就行了。发现 m \le 1\times 10 ^{18}，短暂思考之后想到对于大部分的钱，循环买 x_i+y_i 最小的那种糖果两颗是最优的。然后又想到对于一些 x_j，可能在最后剩下的钱中优先购买便宜的 x_j 可能会比最小的 x_i+y_i 更优，然后就觉得这题应该是个贪心。

开贪。直接将糖果按照 x_i 大小排序，记最小的 x_i+y_i 为 tot。考虑到买糖果应该是两个两个买，然后最后再考虑是否能多买一个，于是我写了比较 x_i+x_{i+1} 和 tot：若 <tot 则选择，若 >tot 则比较 x_i 加上最小和的 x 与 tot 比较。前两个样例经过调试一些奇怪错误很好就过了。

跑大样例，其实在测样例就意识到这题答案输出只有 1 个，样例可能会很水。然后在 candy6（答案为 83）的样例中输出了 82。

对此进行调试，想了很多奇怪的想法导致浪费了大量的时间：先是认为若和最小的 x 和其他糖果组合时，它的 y 会不会也和其他糖果组合，经过 10min 我写好了这个判断，但对所有答案没有任何影响。后来又想到对于 x_i 被选择的糖果，会不会它的 y_i 也被其他组合。写了一份堆优化的贪心，每次弹出最小的 2 个值，再加入它们的下一次价格。直到弹出的 2 个数总和 \ge tot 时退出循环，开始买 tot。但是还是无法通过 candy6。

时间已经过去了 1h+，我开始怀疑贪心的正确性，以及这题是否是个贪心或是 dp。

越来越紧张。

想到之前水讨论区看到的，如果卡 T1 则先去打 T4 暴力，这样就只剩 3 题，可以很好调节心态。然后往下去翻 T4，过程中看到 T3 是最最不擅长的树有点害怕。

T4 题面还算是好理解，初看样例发现 m 个区间查询问题，第一眼以为是莫队，然后发现好像没有任何关系。我写了一份较为优化的最基础暴力，直接枚举从 1 到 m，每次跑需要的位置和区间的 l,r。但是又发现了问题：我从未写过将数取模 2^{64} 的题目，导致 long long 没能存下，使用 unsigned long long 后发现这东西从未用过。啥也不了解，咋办啊？？然后我最基础的暴力对于所有 k_i i\ge0 都没有问题，但对于样例 1 中的 k_3=-1 我不会取模。不会取模这一整道题都可以丢掉了，好失落啊。我在不断尝试如何将负数取模后，经过了 40min，还是不对。看来好像注定 T4 是个 0 了。

过去 2h 了，我望着我 4 份 0 pts 的代码。

继续折回搞 T1。发现之前的思路都好糊，尝试重新分析：对于第 i 个糖果，我如果会取到 y_i，则说明它的 x+y 是最小的，对啊，说明有且只有一种糖果会取到 y。因为若其他糖果会取到 y 则说明其他糖果的 x_j+y_j 会小于 tot，而我定义了 tot 是最小 x+y，所以这并不可能。那么除了 tot 的糖果，其他所有糖果都是最多取 1 个，所以可以按照 x_i 从小到大排序。将 i 从 0 到 tot 位置扫一遍，计算对于购买前 i 糖果 1 个，剩下全买 tot 的答案，取其最大值就是最终答案了，这很好证明正确性。再用前缀和维护一下前 i 个 x 的总和，计算最大值的复杂度只有 O(n)。

开始重构 T1，没有经过调试，直接通过了 candy6，高兴坏了。将所有大样例都跑了一遍，却又在 candy4 出了问题，我尝试将 i 从 0 到 n 扫一遍，然后就对了，我也不知道为什么，但至少都通过了。

时间复杂度 O(n \log n)，瓶颈在于排序。T1 得到 100 pts。我记得当时是 2h 21min。心态 +5。

T2 咋感觉不太好读，那就像 CSP 一样先看 T3。T3 理解题面耗费 15min，读不懂子树什么意思。

大致看了看数据范围，想到对于每个节点取 \operatorname{mex}，那么每个节点的值 a_i < n。其实对于这种构造类的我还是比较喜欢的，毕竟挺有趣的。快速打了一份 dfs 枚举每个 a_i 取值从 0 至 n-1 来判断答案取最大值的代码，调了好久。对于每次判断价值，直接对于 n 个点全部都扫一遍树，判断价值复杂度约 O(n)，总时间复杂度约是 O(n^n)，应该可以跑过 n\le7 的前 2 个点。

T3 还是感觉挺有意思，继续寻找特殊性质，目标落到 m\le 2。发现树只有 2 层时，根据样例是不是可以直接贪心，对于 d_i=1 的节点，把答案加上它的子数就行了。然后过不了样例。

考虑到 d_i=1 的节点，找到子数最多的就行了，对于其底下的节点分别取 0 至 siz-1，此时该节点和节点 1 的值应该最大，其他所有 d_i=2 的节点全部取 0，那么每个 \operatorname{mex} 应该都是 1，对于 d_i=1 全部取 1，每个 \operatorname{mex} 都是 2。求最大价值时间复杂度 O(m)，存边复杂度 O(n)。顺利跑过了对应的 tree4，T3 到达了 8+8 = 16 pts。

印象中时间刚好过去 3h。

回去开 T2，发现每个 w_i 只能取 1 或 2，共有 2^n 种方案，观察数据范围，发现 n\le5 有 3 个点，这还说啥，直接 dfs 了。

笑点解析：读完题不看样例时，我认为题目中的排序方法是完全正确的，和我自己思考的最大值取法一样，一定能取到最大值。

发现了题目难点：对于每个 w_i 都决定好时，怎样判断是否是最大价值。初步思考，并观察样例，我认为是当排序后 w_i 为 1,2,1 且剩下的钱为 2 时可能会出现问题。此时按照题目描述肯定是去第 1 个和第 3 个，但可能会有第 3 个的 c 特别小导致 c 总和小于第二个的情况，然后在判断过程中特地判断了剩下钱为 2 时的取值情况，顺利通过了样例。

然后在跑大样例时 sale2 中出现了问题，发现自己的每个答案都有可能比标准答案大，说明每次取法有更优解我没考虑到。想了约 10 min 后，想出了一组 hcak：当排序后 w_i 分别为 1,2,2,1 且剩下 4 元时，按照他的方式只会购买第 1,2,4 个，但是可能购买第 2,3 个可能是最优的。经过浅浅猜了个大致正确的结论，应该是最优方式最多比题目取法多 1 个 w_i=2 的商品。所以我记录了 w_i=2 按题目取法取了 tmp 个，然后再模拟取 tmp+1 个 w_i=2 的商品，剩下全部用 w_i=1 的商品补齐 m。顺利通过了 sale2。

此时 T2 复杂度是 O(t 2^n n \log n)，前 3 个点咋感觉不太好过啊，不知道 sale2 咋跑过的。然后我就没事干跑了 sale3，竟然跑得飞快。大脑飞速旋转，这为啥能跑过 n\le10 啊？

大约过了 3h 40min，T2 应该是 20pts。

忽然注意到特殊性质 A，所有 c_i 相等的话，那是不是无论怎么取所以商品成本都相同， w_i=1 优先，感觉好像无论怎么取都可以啊。答案为 2^n，T2 分数到达了 20+4=24pts。特殊性质 B 不太好想，感觉是比较取商品的数量，先跳过了。这次 T2 部分分怎么这么少。

继续想 T3，在草稿纸上飞速画树，浪费 10min 后无果。

又回到 T4，毕竟一题挂 0 太难受了。根据样例，我感觉 C++ 算出的 2^{64} 好像有问题，然后自己手算了一遍，好像确有问题，将模数修改后，我猜测负数取模时直接把数加上模数就行，然后直接就这么写了。中间经过了好多好多调试，最后终于把样例 1 成功跑过了。用 query2 大致验证了正确性，时间复杂度 O(qn^3)。

T4 虽然 O(qn^3) 好像跑不过第 1 个点，但是 r_i-l_i 应该不会很大吧，默认 T4 得到了 5pts。

还剩下 20min，出发大力搓 T2 的 m=2，考虑到 m=2 最亏就是 w_i 取 1,2,1 的时候，然后直接枚举第一个和第三个，以二分微微优化到 O(n^2 \log n) 求答案。但是跑不过对应的大样例，本来应该还能有 8pts 的，可惜了。

NOIP 结束了。

算了，至少比 CSP 没写完好。黄紫黑黑也太恐怖了。当天晚上熬夜快熬穿了，希望别挂。

Day2 洛谷民间数据估分。

不是我 T1 怎么挂了？？？WA on # 1 # 3？？

我不会写 n \le 2，望周知。

我忘记判前 i 个 x 的和是否 \le m 了，所以我的答案至少为 n。官方数据是不是要爆零了。草。

我 T2 咋也挂了，明明 sale3 跑过去了，但在谷上却是 2 个 1.08s 被卡飞了。那我 T2 不是只剩 16pts 了吗，看机子跑得快不快了。

后两题没问题。

upd on 2025.11.30：T2 民间数据重修了，我 24 pts 回来了。