CSP-J/S 2025游记

· · 生活·游记

初赛前一周

有老师给我们讲初赛的知识，需要背的东西太杂了，但是基本不考，考到了就蒙一个。

文化课老师允许我们少做一点作业，但是我明白，以老师的习惯，后面是要补上的，所以我还是在认真地做作业，初赛基本不用复习。

9.20

如我所料，初赛轻松通过，两场都是90+。

国庆假期

集训开始了，停文化课。10月9日开始，可以在教室上(shou4)完(wan2)早(zhe2)自(mo2)习后，逃离文化课老师。这种感觉就是爽。每天下午还能多0.5小时运动时间，等打完球，吃完饭后，再去学习，效率真的能提高，原来调不出的代码说不定就能调出来，然后骂自己一句joker。

复赛前一周

心态受到了大影响。

周六在隔壁学校打的模拟赛，打崩盘了，大约是今年目标的一半（150/300），机房倒数第二，在所有参赛的人里也排在后半段。这次是策略的失误，T3明显比T2简单，但是我由于无法接受T2做不出来的事实，一直在做T2。

考前两天的模拟赛，又崩盘了，分数被学弟学妹吊打。本来只有100多分，但是由于没有对拍，T1挂了，总分只有两位数。

10.31

试机。考场的电脑比我日常用的快多了。

明天就要考试了，不能让心态受到影响。于是听了若干遍、若干首歌曲，包括但不限于《海阔天空》《不再犹豫》《红日》。坐标CQ，喜欢听老歌、粤语歌，还有救吗？

心态终于保住了。

11.1

注意：此部分涉及做法。需要做今年真题的读者可以跳过。

上午40分钟AK，包含测大样例的时间。前两道题都是语法基础级别的，第三道是一个简单的DP，结合前缀异或和的技巧。第四道题，可以考虑枚举最大值的位置，同时用DP维护和的信息（当选中的数和为某个数时的方案数）。

切完水题就开始玩虚拟机、睡觉。本来想在代码里写歌词，争取上迷惑行为大赏，但是忘了。

下午去了之后，T1一眼看出贪心做法：先把所有人塞进权值最大的部门，此时如果有部门人数超了，就把这个部门的人调走，过程中尽量减少损失的权值。实现的时候思路略有不同，但是等价：先把所有人按最大值减次大值从大到小排序，再尽量往权值最大的部门塞。30分钟左右做完了。

开T2，一开始在考虑能不能直接建图跑一边MST，貌似不行。k\le 10 的范围启发我枚举改造哪些乡镇，然而每次都跑MST超时了，所以猜结论：只用保留原图的最小生成树上的边。这样复杂度就能接受了（吗？）。大样例过了。然而，我的程序貌似有一点慢，真的能过吗？复杂度貌似是 O(2^kkn\alpha(n))，假了，不会优化。能过80就不错了。我在考场上并没有想到复杂度的问题，以为能过。

开T3，对于自己发现了不保证 |t_1|=|t_2| 感到庆幸（虽然没什么用）。考虑到枚举被替换区间的左端点，计算有多少组 s 满足：与 t 的对应位置相等，且覆盖了所有 s_{1,i}\ne s_{2,i} 的 i。如果我们把一组 t 的同一位置两个字符看成一个字符（相当于合成一个 t），再把 t 插入字典树中，计算的就是一点到另一点的点权和。较浅的一点可以用哈希定位，然而当时第一反应没有想到较深的点怎么定位，只能暴力。后来灵机一动：二分。然而再套一个带 log 的算法用于定位就超时了，也不敢写 unordered_map，所以手写哈希表，从某些质数中随机抓一个作为哈希表长度。By the way，字符串哈希的 base 也是随机抓的。

T4只会状压。

打完T4的暴力后，对拍了T1。中途竟然停了下来（暴力和正解输出不一样），给我吓坏了。原来这组数据的 n 是奇数，无效。

晚上照常打ABC，但是rp耗尽了，只做了5题。

11.2

上午被拉去锻炼（初三了，下学期要中考体考），发现立定跳远退化了，因为已经1个月没练过了。

明天就要开始补文化课了，但是晚上我们在机房团建，全在打牌、下棋、看视频。

11.5

由于网站的漏洞，提前看到了成绩。

J组：100+100+100+100=400

S组：100+80+100+8=288

失望了。

实话实说，没有达到今年的目标（300）。

S组还是全机房倒数第二，准确来说是倒数倒数第二（人话：第二）。

T2和T4都挂了。这次没有极限数据用于测试。以后应该注意：造几组特殊数据、极限数据，测试一下，潜在的问题就能显现出来。

11.10

又是一轮集训……