别样的 CSP 2025 大战
xyber_nova · · 生活·游记
记
考前：序曲
TL; DR：两个神人高中生的奇妙冒险。
上午：CSP-J
-
-
-
-
-
冷静下来，发现由于异或运算满足优美的“消去律”，自然想到了异或前缀和。形式化地： $$ \bigoplus_{i=l}^{r} a_i = \left(\bigoplus _{i=1}^r a_i\right) \oplus \left(\bigoplus_{i=1}^{l-1} a_i\right) $$ 于是，问题就转化为：在所有满足 $\bigoplus_{i=l}^{r} a_i = k$ 的合法区间 $\left[l, r\right]$ 中，求最大不重叠子段数量。 一开始，我想了个错误的贪心，浪费了大约40分钟。结果突然灵光乍现，想起了CSP-S 2024 T2的第二个子问题。思路瞬间清晰：求出所有合法区间，按右端点排序，然后进行经典的区间覆盖贪心。 （PS：实际上，在写暴力解的时候，我就已经想到了这个优化。不过，本着“为信仰充值”和“提供对拍程序”的严谨心态，我还是完整地实现了一版暴力。） -
中午：幕间休息
-
路上，和同学们激烈讨论下午S组的难度，大家普遍乐观地认为会很简单——现在回想起来，【数据删除】。 -
-
下午：CSP-S
-
-
-
1. 不难发现，在任意时刻，至多只有一个部门的人数会超过限制。而理论上的最优情况，是所有人都被分配到自己的第一志愿部门（当然，这通常是奢望）。 2. 那么，那些满员的部门就必须“裁员”。裁掉谁呢？我的第一直觉是裁掉那些“最不喜欢”本部门的人（这也是我的第一版思路，然后被样例1的数据3无情地暴打）。 3. 很明显，我们的直觉**并不可靠**！正确的贪心，应当是让“裁员”这个操作的 **“损失”最小化**，从而得到全局最优解。 形式化证明：显而易见，裁掉 $x$ 个人的操作是不可避免的，而裁掉哪些人则是我们可以决定的。**我们必然希望，这一系列裁员操作，使得最终解的“劣化程度”最小。** 4. 具体地，我们定义 $C(i, j)$ 为将第 $i$ 个人从部门 $j$ 开除后，解的“劣化程度”。它可以形式化地定义为： $$ C(i,j) = \max_{k \in \{1,2,3\}, k\ne j} a_{i,k} - a_{i,j} $$ 这个值，直观上代表了将第 $i$ 个人调剂到他次优选择时，满意度的下降值。 5. 用一个优先队列来维护所有超员部门成员的 $C(i, j)$ 值，每次贪心地弹出 $C(i, j)$ 最小的成员，并将他放入其最喜欢的备选部门。 （碎碎念：考场上我没注意到 $n \pmod 2 = 0$ 的保证，还专门写了个特判，真是严谨过头了。） -
1. **T2**：有点状压DP的感觉，但是我的大脑已经 $DeepSeek \leftarrow DeepSleep$（毕竟在YN，切掉T1就足以确保省一和NOIP入围了）。于是，我写了个特殊性质判断：如果没有点权，就直接跑Kruskal；否则，就上 DFS 暴力枚举 + Kruskal。 2. **T3**：一眼看出来和KMP相关，但考前讲这个算法时我恰好没听（欲哭无泪）。只好写了个朴素的 $O(n^3)$ 暴力，聊以自慰。 3. **T4**：完全不知所云。写了个判特殊性质直接计算 $n!$ 的代码，连样例都过不去，权当表达对出题人的“敬意”。 -
考后
教练用民间数据为我进行的初步估分如下：
- CSP-J：360分左右
- CSP-S：164分左右（T3、T4 缺数据）
最后，祝各位谷民在未来的比赛中 RP++，都能稳进NOIP喵。