CSP-J/S 2025 游记

· · 生活·游记

第二次考 CSP-J，第一次考 CSP-S。

Day -??

初赛：只考了 J 组初赛，时间充裕。
J 93.5pts，S GESP 衔接免考。

Day -2,-1 (10.29,10.30)

集训模拟赛，分别获得了 0pts 和 35pts 的好成绩。 :::info 印象最深刻的是前一场 T1，用了线段树求最大值在 1e6 范围下喜提爆零，正解是单调队列，订正的时候终于学会了。 :::

Day 0 (10.31)

读了读《算法竞赛进阶指南》的基本算法一章；尝试切 J 组模拟赛题没做完；看了看去年部分真题感觉基本懂了。

忽然发现一天都没写题，这对保持赛前状态是无益的，于是写了一道红题。睡觉。

Day 1 (11.1)

早上继续看书、真题、模板。
还好这次考场在对面自己学校。

八点多进了考场。屏幕上用极域开着全屏广播，然后我用 Win + G，Ctrl + Win + D 切走了但好像其实还不能动鼠标键盘。

正文开始

以下部分内容与题目解法有关。

CSP-J

8:25 开始操作，敲了模板代码并解压了文件，这时是 8:30。

开了 T1，排序假了，直接开桶。

开了 T2，排序并推一下位置。

切进 Linux 写完 T1,T2，此刻已经过去了半个小时左右。

9:04 开了 T3，一眼转化异或前缀和并考虑 dp，写了式子再用 umap 维护一下最大值就做完了；调的时候最开始 WA 了就发现是初始值的问题。9:27 过了。

9:30 开了 T4 （去年 T3 小木棍阴魂不散），考虑固定最长选中的小木棍，将剩下选中木棍长度之和大于最大长度的方案数转化为所有可能情况减去剩下选中木棍长度之和不大于最大长度的方案数，背包即可。调的时候发现比答案少了一些，原来还要加上木棍长度相同时用背包多减掉的数量。10:41 过了。

写完之后直到 10:52 认真检查了一下文件夹/文件名等。

然后写了 T3 的考场题解，写完是 11 点多。 :::success[T3 考场题解]

s_{i} := xor_{k = 1}^{i} a_k;
k = a_{i} xor a_{i+1} xor .. xor a_{r} = s_r xor s_{l - 1}
<=> s_{l - 1} = s_{r} xor k;
dp: f_{i} := max number of ranges from 1 to i;
f_{i} = max{f_{i - 1}, max_{s_{l - 1} = s_{r} xor k} f_{l - 1}}.
g_{t} := max_{s_{i} = t} f_{i}.
then: f_{i} = max{f_{i - 1}, g_{s_{r} xor k}};
g_{s_i} = max{g_{s_{i}}, f_{i}}.
init g[0] = 0.

:::

在小范围内对 T4 拍了 10 组都过了。然后写了 T4 的考场题解，(11:50, 11:55) 写完。 :::success[T4 考场题解]

0. sort the array in decreasing order.
1. consider the longest stick selected, say a_{i} = l_{1}.
   then the rest sticks that can be selected is from a_{i+1} to a_{n},
2. as we want to find the possible number of cases that
    sum_{i=2}^{m} l_{i} > l{1},
   where l_{2} ~ l_{m} is the rest sticks selected,
   then the answer is all possible number of cases 2^{n-i} subtracts
   the possible number of cases that sum_{i=2}^{m} l_{i} <= l{1}.
   we can use a 01背包 to calculate this kind of cases,
   as we prework this case with volume a[1].
3. then we can deal with query with the longest stick selected a_{1}
   with the above algorithm. when there is duplicate length of sticks,
   the answer should be increase by the number of the sticks that have
   been calculated in order to solve the problem of the answer being
   reduced more than it should be.

::: 11:58 交了，感觉状态极其良好。

中午
吃饭；看真题、模板以及 LCA 求法。

CSP-S

T1，半晌先是没思路，然后写了 O(n^4) 的 dp，再看了半天感觉这是三维费用背包，改成 O(n^3)，估计只有 55pts；期间想过贪心但感觉哪里不对，退了，此时过去了约 1 小时 40 分钟。

T2，直接状压枚举加的乡镇然后跑最小生成树，写出来本地 RE，用链式前向星写的，发现从点 1 出发的边经过多次取 Next 后越界，无法解决，挂了。

于是改看 T3，存 char 类型字符串的话不能知道字符串有多长会 RE/MLE，存 string 我又对这样的字符串查找不熟，改来改去暴力打不出来，退了。

T4，打了 O(n\times n!) 的暴力，n = 10 都会 TLE，估计只有 4pts，退了。

切回 Windows, 调 T3，没调出来。再调 T2，也没调出来，最后一秒交的，遗憾离场。

总结与回顾

CSP-J

估分：100 + 100 + 100 + 100 = 400分。
洛谷自测：100 + 100 + 100 + 100 = 400分。
希望不要挂分。

CSP-S

估分：55 + 0 + 0 + 4 = 59分。
T1 没写反悔贪心的做法，一方面前段时间的模拟赛好好学了背包 dp 就有点往这方面上去想的感觉 （但要是我没学 J 组 T4 不好做），另一方面潜意识里有贪心的想法但没写，感觉贪心没学好。
T2 考后才意识到 RE 的情况其实可以改用 vector，另一方面对最小生成树的做法掌握的还不够熟练。
T3 对字符串 STL 相关掌握的还不够熟练。
T4 ？？？

写在最后

祝大家 J 组像我一样 AK，也衷心祝愿大家（包括我）不要重蹈我这次 S 组的覆辙。

基础的算法及知识点还是要掌握好，多写题。 :::info[tips] 在 Linux 下可以使用 LemonLime 进行评测样例及对拼数据。 :::