2025CSP-J2/S2 游记

CCF 吃了 78 分。

-J：

-S：

T1 和 T2 花了大概30分钟吧，比较简单。

然后是 T3:

第一眼比较简单，轻松就想到了 DP，以及前缀异或和优化。

考虑区间 DP，但是左右端点需要两维，空间会炸。

然后？没然后了。。

赛时只想到了这里，花了大概一个小时想如何优化，但是没想到那个贪心。。

遗憾拿了 40 分，去看 T4 了：

因为 T3 心态崩了，没心情去想正解，然后暴力拿了 24 分。

然后考试就这么结束了。。

出去问了一下同学，普遍 330+，直接玉玉了。

但他们都说一等应该没问题，心情好了不少。

上午的失败并没有影响到下午（吧）。。。

T1，看完题面，一开始想的是 DP，但是鉴于上午的 DP 没打好，以及这题的后效性很明显，所以考虑贪心。

三个社团分成三组，不考虑 $\frac{n}{2}$ 的约束，先贪到最大值。

然后考虑约束，想到把对于每组内答案贡献最小的取出来，将其改为 -1，然后重新贪心。

复杂度肉眼可见的很高，考虑优先队列维护三个组对总答案的贡献。

对于“重新贪心”步骤，在贪心的过程中去判断目前的答案是否符合。

现在复杂度还大了一点，不管了，测样例。

等一下，样例的第三组数据把这个思路 hack 掉了。

心态又有点崩，上个厕所。

上完了，还是没思路。

去看了 T2，T3，T2 想到了最小生成树，T3 想到了 KMP，这两个我都会，心态又好了不少。

然后看到 T1，注意到了只会有一组会大于 $\frac{n}{2}$ 的约束，同时接下来的调整中不用再考虑约束。

感觉离正解很近了。

然后又上了个厕所，又想到了如何不被样例的第三组数据 hack，那就是只用考虑交换过程中，对答案的贡献影响最小的进行交换。

然后正解就出来了，大概花了一个半小时。

T2 和 T3 的暴力打完了，时间差不多就走了。

-S 最后挂了 78 分，还是太菜了。。