NOIWC 2025 题解 & VP 游记

· · 生活·游记

VP 一场，只有 228 ，勉强拿银牌。

感觉这场很抽象，两道签加一道扣分题？

邮寄在最后。

A

先编编必要条件： - 存在 $n$ 对猫粮组合，满足每对加起来是 $m$ 。 - 不能有超过两对组合都是优质猫粮，除非剩下的所有优质猫粮的量都是 $\frac m2$ 。 这个东西显然也是充分的，那么就做完了。维护个桶双指针乱扫一通就好了，时间复杂度 $\mathcal O(n+m)$ 。 [QOJ 提交记录](https://qoj.ac/submission/867901)。 > 吐槽：两个数组输入反有 65 分，$2\mid m$ 的 case 处理炸了居然有 85 ，能过 $n=4\times 10^4$ 过不了 $n=5$ ？什么抽象的数据。 ## C 先编一个 dp：设 $f_{i,j}$ 表示前 $i$ 个人，第 $i$ 个人被砍了 $j$ 刀的最大收益，转移是简单的，优化成 $\mathcal O(n^2)$ 也是简单的。 然后你对着这个式子瞪（也许需要打个表？），容易发现只需要维护区间加、单点 chkmx 、区间求 $\max f_i$ 和区间求 $\max f_i+im$ ，随便线段树即可。时间复杂度 $\mathcal O(n\log n)$ 。 [QOJ 提交记录](https://qoj.ac/submission/868107)。 ## B 学习了 [wmy 的题解](https://www.luogu.com/article/aez4v4nl) 和官解才懂的。 赛时没编出来特性 B ，看到有人会特性 B 不会 $n\le 6$ 的 dp 有点没绷住。 首先特性 B 是关键，做法是从高到低考虑每个二进制位，如果这一位异或和是 $1$ 那么找一个 $0$ 推平（推平指 $\text{yyy0xxxx}\to\text{yyy10000}$）。瞪一眼发现贪心地推 $\text{xxxx}$ 最大的一定更优，因为不仅当前代价少，后面也会叉掉更多偏高的二进制位。 这个做法会似在 $n$ 是奇数且某一位全部是 $1$ 的 case ，此时找不到推平的位置，还不能随便选两个 $1$ 推到更高位，因为有进位的情况。解决办法是在处理更高位时，如果之前没有推平过且现在不需要推平，那么随机挑选两个最大的 $0$ 推平，选最大的原因和上面一样。 > Q：为啥之前推平过就不用考虑推平两位了？ > A：因为推平过了，低位就都有 $0$ 了，根本不会出现这种 case 。 然后随便暴搜就好了。时间复杂度 $\mathcal O(n\log n\log V+m\log^2V)$ ，实现不精细可能多带 $\log$ 。 [QOJ 提交记录](https://qoj.ac/submission/869234)。 > 吐槽：我的朴素实现跑了 555ms ，请问那个跑了 117ms 的哥们是什么成分，为啥辣么快？ ## VP 邮寄 D 爹让 vp 一下，那就打吧。 过了 8:00 ，试图卡 8:15:00 ，结果是 8:14:59 。绷。 先开 A ，瞪了一小会没啥头猪，于是写了个 `Yes` 上去获得了 15 分，过了 #1#8#9 。此时 8:20 。 扫一遍 BC 之后回来编 A ，很快编出来必要条件，写完交上去获得了 65 分。此时 8:34 。 以为自己条件不够充分，瞪了若干分钟以为是边界处理炸了，调了调获得 30 和 65 。此时 8:42 。 有点玉玉，又瞪了一会发现输入反了，并且发现刚才处理的是 $2\nmid m$ ，大骂自己后交上去 85 。此时 8:44 。 一脸懵逼，看了看发现这次确实是边界处理炸了，调过了。此时 8:57 。 编了编 B ，没啥进展，搓了一个异或和上去获得 0 分。此时 9:08 。 有点蓝瘦，看了看有点可做的 C ，先编出了 #1 ，炸了一发之后发现是输入一行两个数而不是两行，拿到了 5 分。此时 9:28 。 编了一个枚举上一个没被干掉的人在哪里的抽象 dp ，做了半天过了两个样例，交上去 0 分。虽然这个做法本来在数据范围里面没有立足之处，但我自己编出来了反例，哭。此时 10:23 。 换了一个 dp 当前人叉几次的做法，调了半天终于拿到了 35 。此时 10:48 。 为了避免炸，先拼了一下 #1 的 5 分，有了 40 分，中间炸了两发略去不表。此时 10:53 。 玉玉了半天，终于编出来怎么线段树了，码码码。大样例炸了，哭。调调调，拍拍拍，inf 年之后发现单点修改忘记 `pushup` 了，唐。终于切了第二个签。此时 12:02 。 然后开始编 nim 。瞪一眼，编出来了 #1 ，炸了两发拿了 4 分。此时 12:12 。 开始思考值域很小的情况。编了一会编出来一个 $\mathcal O(nV^2)$ 的 dp，码码码，调调调。调掉若干日常贩糖的 bug 之后交上去只获得 16 分。此时 13:05 。 很慌，看了两眼发现是调试时把值域改小忘改回去了，交上去 28 分。此时 13:06 。 开始编特性 A 的半档分，胡了若干贪心上去爆炸了 inf 发，直到 13:14 也没拿到那 6 分。哭。 赛后去你谷邮寄区找 solution ，看见一个会特性 B 不会 dp 的和一个 $100+100+40$ 的。感觉很离谱。 去官网找分数线，银牌线 212 ，金牌线 258 。勉强拿了 Ag ，Au 只能说离我有点远。不过我在赛后编出来特性 A 的 6 分和 B 的 22 分之后 256 ，加上 $m=1$ 可以随便造方案有 258 ，卡线 Au 。只能说 wtcl 。