2025CSP-J2/S2 游记
省流：
CCF 吃了 78 分。
| -J： | T1 | T2 | T3 | T4 | |
|---|---|---|---|---|---|
| 估分 | 100 | 100 | 40 | 24 | |
| 实际 | 100 | 100 | 40 | 24 |
| -S： | T1 | T2 | T3 | T4 | |
|---|---|---|---|---|---|
| 估分 | 100 | 64 | 30 | 0 | |
| 实际 | 100 | 16 | 0 | 0 |
我是fvv
-J
T1 和 T2 花了大概30分钟吧，比较简单。
然后是 T3:
第一眼比较简单，轻松就想到了 DP，以及前缀异或和优化。
考虑区间 DP，但是左右端点需要两维，空间会炸。
然后？没然后了。。
赛时只想到了这里，花了大概一个小时想如何优化，但是没想到那个贪心。。
遗憾拿了 40 分，去看 T4 了：
因为 T3 心态崩了，没心情去想正解，然后暴力拿了 24 分。
然后考试就这么结束了。。
出去问了一下同学，普遍 330+，直接玉玉了。
但他们都说一等应该没问题，心情好了不少。
-S
上午的失败并没有影响到下午（吧）。。。
T1，看完题面，一开始想的是 DP，但是鉴于上午的 DP 没打好，以及这题的后效性很明显，所以考虑贪心。
三个社团分成三组，不考虑
然后考虑约束，想到把对于每组内答案贡献最小的取出来，将其改为 -1，然后重新贪心。
复杂度肉眼可见的很高，考虑优先队列维护三个组对总答案的贡献。
对于“重新贪心”步骤，在贪心的过程中去判断目前的答案是否符合。
现在复杂度还大了一点，不管了，测样例。
等一下，样例的第三组数据把这个思路 hack 掉了。
心态又有点崩，上个厕所。
上完了，还是没思路。
去看了 T2，T3，T2 想到了最小生成树，T3 想到了 KMP，这两个我都会，心态又好了不少。
然后看到 T1，注意到了只会有一组会大于
感觉离正解很近了。
然后又上了个厕所，又想到了如何不被样例的第三组数据 hack，那就是只用考虑交换过程中，对答案的贡献影响最小的进行交换。
然后正解就出来了，大概花了一个半小时。
T2 和 T3 的暴力打完了，时间差不多就走了。
-S 最后挂了 78 分，还是太菜了。。