初一弱鸡 WC 2025 游记

· · 生活·游记

比赛经历

省流，\text{selfeval}~100+28+5=133，查分没挂分也没有反向挂分。本人初一，如果嫌菜请大佬轻喷。

首先试机，题目是 \text{NOIP}~2024。尝试挽回一下场上的遗憾，结果 T_2 写了 0.5h 没有调出来。

正赛开始。开局看 T_1，一下就发现了这道题目的关键性质：每一只猫一定恰好被喂了两袋猫粮。然后随便写了一下，于是就过大样例了。过完之后直接去上厕所 + 开始喝第二瓶水。

自信出手，开始看 T_2。看到一半突然注意到有一个 \text{selfeval} 是可以用的，找了 0.5h 然后终于找到了。于是赶紧测一发 T_1，然后竟然只有 65 分。然后看了一眼，只要猫粮重复的我一个测试点都没有过。哦，原来大样例保证了猫粮不重复啊！想着与其去处理可能细节很多的这 35 分，还不如先去扣扣后面的题。

然后继续思考 T_2。感受了一下感觉这道题目很恶心，于是不打算冲了直接开始写部分分。首先第一个测试点完全就是来搞笑的，写了一下，然后 WA 了？不急先看 2\sim 7，这不就水 DP 然后输出路径吗？写了，一遍过，此时过去 2h，65+24+0=89。然后检查了一下上面发现写挂了一个小地方，改了就直接 28 分了。

这个时候还剩下 2.8h 左右。感觉后面的题目也有分了就回去搞 T_1 了。重新冷静分析了一下问题，在草稿纸上写满了，然后发现了一个之前没有考虑的细节。改了之后 WA 了几发之后就过了 \text{selfeval}。此时还剩 113 分钟。（怎么不是 114 啊，悲）

接下来还有一个 T_3。去看了一眼，先把第一个测试点写了，调了一下就拿了 5 分。然后看了一下后面，诶这个不就是一个大水的 DP 吗？推了推状态发现转移不可行。怎么办？接下来就在 T_2 和 T_3 之间反复横跳，一份没有得。

帅，前 3.5h 拿完所有分，最后一分都没拿到。

WaXeR 状态严重受到影响，只有 121；但是 Farmer_D 就很强 262，yxx 竟然还挂了 5 分 237，都是神人啊，鄙人自愧不如。

题目复述与题解

这个是题目的回忆版，可能会有不准确的地方。

所有题目都是多测。

T_1

有 n 只猫，每只猫需要吃 m 克的猫粮才能吃饱。

现在有两种猫粮 \mathrm{A} 和 \mathrm{B}，各有 n 包，克数分别为 a_1\cdots a_n,b_1\cdots b_n。克数都是正整数。

你需要执行 2n 次操作来喂饱所有的猫，每次只可以进行以下两种之一：

如果一只猫得到了一包猫粮，不管他还有多少克才能吃饱，他都会把这包猫粮全部吃完。

现在给定 n,m,a,b，问你是否存在一种方案满足无论发生什么，都保证能喂饱所有猫。

这边有有助于解题的关键性质：保证对于所有数据，\displaystyle \left(\sum_{i=1}^n (a_i+b_i)\right)=nm,\forall i\in [1,n],a_i\in [1,m),b_i\in [1,m)。

好像 n\le 4\times 10^4,T\le 50。

因为比我还菜的人才不会做这道题，所以我就把题解写的详细一点适用于向我一样的萌新。

我们先考虑一个弱化版的问题：有 n 个数，把它们两两配对，请问是否可以使得每一对的和都为给定的一个数 m 呢？这道题目非常简单，我们考虑设 \text{cnt}_i 表示 i 这个数出现的次数，那只要满足 \forall i\in [0,m],\text{cnt}_i=\text{cnt}_{m-i}。如果 m 是偶数，则还需要满足 \text{cnt}_{\frac{m}{2}} 是偶数。

然后我们回到原问题。因为 a_i,b_i\in [1,m-1]，所以一只猫至少要 2 袋猫粮才可以喂饱。又因为一共只有 2n 袋猫粮，所以注意到每一只猫一定恰好被喂了两袋猫粮。那这样每一只猫吃到的猫粮情况就只会是 \mathrm{A}-\mathrm{A},\mathrm{A}-\mathrm{B},\mathrm{B}-\mathrm{B} 三种。

考虑我们先处理所有可以配对的 \mathrm{A} 和 \mathrm{B}，直接选择一个 a_j 和 b_k 满足 a_j+b_k=m，然后删除即可。这样配对的正确性非常显然，考虑当前配对的数对是 (a_j,b_k)，则先喂 a_j，然后给那个得到 a_j 的猫喂 b_k 就可以了，这样可行性就有保障了。

把这些配过对的 a 和 b 删除后就剩下了两个序列 a' 和 b' 了。对于序列 b'，直接用弱化版问题的方法做就可以了。比较特殊的是 a' 的情况。由刚才的分析我们发现一个序列自己进行匹配的方案是唯一的。所以如果 a' 包含 \ge 3 种元素则一定不可能，因为 a' 相匹配的情况就不能唯一确定了，直接输出 No 即可。而如果 a' 包含两种元素，则不难发现两种元素的出现次数中必然有一个恰好为 1。然后再对 a' 做刚才的弱化版本问题即可。复杂度可以做到线性加值域。

T_2

有 n 个正整数 a_i，你需要构造一个长度为 n 的数组 b，满足在 \displaystyle \left(\bigoplus_{j=1}^n\left(a_j+b_j\right)\right)=0 的情况下最小化 \displaystyle \sum_{i=1}^n b_i，还需要给出 m 种可行的构造（只需要输出 b 非零的元素即可）。其中 1\le \sum n\le 3\times 10^5,1\le m\le 10^4,0\le a_i< 2^{60}。

思考思路：从高位到低位枚举，枚举到第 t 位选择若干个第 t 位不为 1 的数 a_{i_1}, a_{i_2}, \ldots, a_{i_{l e n_t}} ，将这些数第 t 位变成 1 ，并将更低的位全部变为 0 。

贪心结论 I：在 a_1=0 时，一定有 l e n_t=0 / 1 ，取决于该为 1 的数量是否为偶数。可以在 l e n_t=1 的时候暴力枚举改变谁，时间复杂度 O\left(\log ^n\left(a_i\right)\right) 。

我们考虑一个新的贪心策略 II：为了使 k 最小，在第 i 位时一定会选择后 i-1 位尽可能大的 a_x 将其改变。故对于 m=1 的情况可以按照这个贪心完成，时间复杂度 O(n\log n)。

考虑将贪心策略 II 进一步扩展。固定 k 时，在第 i 位时如果后 i-1 位更大的 a_x 改变不可行，则更小的 a_y 也不可行。

由此我们可以得到一个搜索的思路：对于每一位按照更小位的大小排序（如果该位为 1 则设为 -\inf），并且按照从大到小顺序搜索答案，搜索到不合法方案/方案已经被填满则返回。时间复杂度 \mathcal{O}(n\log n\log (a_i)+m\log(a_i))。

最后只需要考虑没有特殊性质 B 的情况，需要略微修改贪心结论 I。

贪心结论 I（修改后）：当 n 为奇数且存在某一位全为 1 时，可能会在更高的某一位 1 数量为偶数的地方选择 \text{len}_t=2 即可。其他情况不变。

所以不管是求 k 还是求方案，我们在每一位若满足条件时选择一次 l e n_t=2 即可。其他情况不变。

这样也就多一个 \log(a_i) 的代价。最后总时间复杂度 \mathcal{O}((n\log n\log a_i)+m \log^2(a_i))。具体实现可能会多一个 \log。

T_3

有两个整数（b 可能是负数，a 都是正数）数组 a,b，长度为 n。还给定一个常数 k。每一次你可以对 a 进行一次操作：选择一个区间并区间 -1。你可以进行任意多次操作，假设你进行了 k 次操作，你需要最小化 \displaystyle \left(\sum_{i=1}^n ([a_i\le 0]b_i)-mk\right)，输出这个最小化后的值。

好像是 1\le a_i\le 10^9,|b_i|\le 10^9,1\le n\le 10^5T，其中 T 是一个 [0,10) 的一个常数，忘记了。

令第 i 个数字一共被减掉了 c_i。特殊的，建立两个哨兵 c_0=c_{n+1}=0。然后就变成 Air Cownditioning 了，最少操作次数等于 \displaystyle\left(\sum_{i=1}^n \max(c_i-c_{i-1},0)\right).

我们考虑对于 i\in [1, n]，如果 c_i>c_{i+1} 且 c_i\neq a_i，那么我们可以将 c_i\leftarrow c_i-1，显然这样调整不会减少收益也不会减少代价。同理，如果 c_i<c_{i-1} 且 c_i \ne a_i-1，那么我们可以将 c_i\leftarrow c_i+1。

根据上述调整我们发现，一定存在一组最优解，使得对每一个 i，c_i=c_{i-1},c_i=a_i,c_i=a_i-1 三个等式中至少有一个成立。

考虑钦定一些 c_i=a_i 或 c_i=a_i-1。对于一个没有被钦定的 c_i，设他前面第一个被钦定的位置为 c_j，那么根据上述结论有 c_i=c_j。

分析完了性质，考虑对此进行 DP。设 dp_{i,j} 表示当前考虑 a_1\cdots a_i，且 c_i=a_i-j 的最大收益。其中 j\in [0, 1]。

枚举 i'<i,j'\in \{0,1\}，可以写出转移方程：\displaystyle dp_{i,j}\leftarrow dp_{i',j'}+\sum_{k=i'}^{i-1}[a_k\le a_i' - j']b_k-m\cdot \max\big((a_i-j)-(a_{i'}-j'),0\big)。直接暴力转移的时间复杂度为 O(n^2)。

考虑动态维护每个状态转移到当前状态时对应的权值。为方便维护，令状态 dp_{i,j} 对应的下标为 a_i-j。令维护的权值序列为 w，从 i-1 扫描到 i 只需要支持：w 区间加，求 \max\{w_i\}，求 \max(w_i+m\times i)。使用线段树维护即可。时间复杂度 \mathcal{O}(n\log n)。