CSP2025 游记

· · 个人记录

简要概括：过度自信导致炸了。

坐标 HA

CSP-J

看 T1，由于 $n\le10^6$，于是打了个 sort，根本没想桶排。 看 T2，小学数学题，秒了。 $9:00$ 左右开 T3，一眼区间贪心，直接枚举 $n$ 个 $l$，显然每次选择最小可选择的 $r$ 是最优的，难在如何确定 $r$。 考虑前缀和，设 $sum_i=\oplus_{j=1}^{i}a_j$，则对于每个 $l$，只需找到它右侧第一个 $r$，使得 $sum_r=sum_{l-1}\oplus k$，可以使用 `map` 统计，由于我脑子抽了，考场上写了一个很史的 $O(n\log^2n)$ 的 `map`，所以改成了 `stable_sort` + 离散化，时间复杂度 $O(n\log n+2n)$。 当前时间 $10:10$，当前状态良好。 开 T4，感觉不太会，先写了个 $O(2^n)$ 的暴力。按照以往的经验，T4 多半是 dp，观察数据范围：$1\le n\le5000$，$1\le a_i\le5000$，直接设 $dp_{i,j}$ 表示枚举到第 $i$ 位（必须使用 $a_i$），总和恰好为 $j$ 的方案数（设 $maxn=\max_{i=1}^n$，因为 $maxn\le5000$，所以总和 $\ge maxn+1$ 的方案直接统计到 $dp_{i,maxn+1}$ 中即可），然后我就不会了…… 最后在 $11:20$ 想出来转移方程了？$dp_{i,a_i+j}=\sum\limits_{k=1}^{i-1}dp_{k,j}$，写出 $O(n^2\times \max_{i-1}^n a_i)$，大样例还过了？ $11:40$ 想出前缀和优化，随便写了一个 $O(n\times \max_{i-1}^n a_i)$，大样例过了？ 估分：$100+100+100+100=400$，我 ak 了？？？ --- 后记：由于过度自信，我的 T4 开了大约 570MB 的空间，0pts，@[\_Liyx\_](/user/1041884) 和 @[unordered](/user/1269251) 都 ak 了，心态炸了。 /ll/ll/ll 考后期望得分：$100+100+100+0=300$。 ## CSP-S $02:30$ 开考。 开 T1，简单贪心？10mins 乱写一通过大样例了（考后感觉炸了）。 开 T2，首先 $k=0$ 时跑一遍 kruskal 即可，注意到 $k\le10$，考虑状压 dp，最终调了 3h，没过大样例 /ll，这个故事告诉我们，一定要注意时间分配，感觉做不出来的题考虑跳过。 因为 T2 调了太长时间，T3 只读了不到 5mins，基本没看懂题。 T4 直接特殊性质和 $O(n!)$ 暴力。 炸炸炸。 靠崩了，没估分。 %%% @[心灵震荡](https://www.luogu.com.cn/user/649315) @[mahaihang1](https://www.luogu.com.cn/user/792311) @[ask\_silently](https://www.luogu.com.cn/user/690160) @[\_Liyx\_](/user/1041884) @[unordered](/user/1269251) @[WangYaoran](https://www.luogu.com.cn/user/1278291)