CSP-J/S 2025游记

· · 生活·游记

Day -inf

CSP 2024 J1: 76.5

CSP 2024 S1: 37.5

很有实力了

Day -10

复习。复习。复习。

Day -1

直奔HZ。考点HZSFDX离JD还挺近的。

晚饭吃了酒店旁的一家羊肉店，很好吃撑亖了。

一开始看到英文招牌有: "Bad Ass"，于是不懂英语文化的我就笑亖了，后来才知道"Bad Ass"是"帅呆了"的意思。

貌似自己更好笑，hhh

Day 1

早上起来十分紧张。

到达考场后，整包餐巾纸都要拿出来，包装不能带进去，于是折腾了很久。

8：25发密码了，一开始没有读懂，后来发现是上善若水。

第一次输密码打成上善肉水了

8：30开题，先看了T1，一开始被吓到了，感觉题目好长，后来仔细一想发现就是把所有数字从大到小排序就行，约8：40时测完大样例，获得100pts。

开T2，又被吓到了。一开始以为蛇形排座位就要二分、找规律啥的，后来发现模拟就行了，于是又很快过掉了，约8：50，已获得200pts。

开T3了，一开始看下发的样例的顺序，以为 "xor" 是T4，现在才发现是T3。看完题一时半会儿没有思路，于是在草稿纸上写了写，觉得可能是贪心，后来写着写着有了一点感觉。首先要是分的区间最多，那么每一次选择区间时，要满足的条件就是左端点在上一个区间的后面，且右端点尽可能的靠前，这样为选择后面的区间留下了最多的空间。大致思路就是及一个指针x，一开始先指向0，然后亖循环，每次找到所有在x后面的左端点对应的右端点中最靠前的一个，那么当前选的区间就是这个右端点对应的左端点和他本身构成的，此时ans++，并将x设为当前右端点。现在还有一个问题，就是如何优化找最靠前右端点的这一步，首先有一个性质我是最早就想到了，可以求一个后缀异或和，记s[i]为后缀异或和为i的后缀中开头最靠前的一个，有了这个辅助数组，就能O(n)求出每个位置作为左端点时对应的右端点（如果有多个右端点就去最靠前的，根据贪心的思路）。 具体代码如下：

int sum = 0;//sum为当前后缀的异或和
for (int i = n;i >= 1;i--) {
    ans[i] = s[sum ^ k];
    //根据异或的性质可以得出
    //若两个后缀异或和分别是x和x^k
    //那么更长的后缀比更短的后缀多出来的区间的异或和为k
    sum ^= a[i] , s[sum] = i;  
}
//s[i]为为后缀异或和为i的后缀中开头最靠前的一个后缀的开头
//ans[i]为位置i作为左端点时对应的右端点

知道了ans[i]，只要求一个后缀最小值就行了，记sm[i]为所有在i后面的左端点对应的右端点中最靠前的右端点的位置，这样x指针每次O(1)跳就行了。需要注意的细节是，一开始要给ans数组全部赋值成n+1，表示无解，之后若x跳到了n+1，就可以退出亖循环了。9：30测过大样例，300pts。

终于到了T4。为什么题目中多次出现CSP-J 2024 T3的名字呢

看完题目后有点感觉，但是又没有完整的思路。看出一个性质，题目给的式子等于把用来拼多边形的木棍集合从小到大排序后满足:

\sum_{i = 1}^{m - 1} a_i > a_m

于是乎想到先把木棍排序，但是之后就只会暴力做法了，写了好久，调了好久，最终在10：30写好了暴力。用set存储当前每一种可能的和（由 a_1 到 a_{i - 1} 组成），再看其中有几种和大于 a_i，加入答案，但是这样的做法只能拿80pts后来被卡常变成68pts了555。于是我就想优化，但是想了半天无果，最终也只能检查一下freopen之类的东西，最后10min睁着眼睛睡觉发呆。

13：00，中午吃的饭也很美味。

13：30，回酒店以后写完数学作业才睡觉，睡了20min，出发了。

14：25，密码是"人杰地灵"，只能说看不懂。

赛后有人说意思是 "人人爆零"

14：30，开T1。看了一眼，想了一会，先做T2了，原因不明。

14：40，开T2。题目看的眼花缭乱，不过还是很快发现和并查集有关。一开始题目读错了，以为是可在n个城市中选k个城市化，所以写完代码连小样里都没过，后来再读题，发现是有另外k个乡村，于是又改了改代码，总算通过了小样例。但是到了大样例就不对了，不仅跑出来很慢，还错了，答案好像是5048……，结果我一直输出5072……，调试了很久，后来一直在觉得思路假了和觉得代码写错了两个想法间跳来跳去，但是再一想，又觉得思路也没错，代码也没错了（后来重构了好几次还是没用）。但是烦人的是大样例调试不了，不知道怎么办了。后来去看T3、T4，T3觉得是可能是字典树，但是毫无头绪，只写了个暴力，T4直接枚举全排列，加一个特殊性质A，得了几分也没算了。后来又回去想T2，但终究没有想出来。提一下T2可能是假做法的思路，就是先把原图的最小生成树搞出来，然后枚举0 到 2^k - 1，表示每个乡村选不选的状态，之后先算改造乡村的费用，然后把每个改造的乡村都和n个城镇连一下边，再跑最小生成树就行。时间已经过半，我急得焦头烂额，十分懊悔一看到T2就冲动了，写了2h多，现在获得分数只是T2玄学、一点暴力分 + T3 x pts + T4 12 pts (x \le 20)，而T1连读入的代码都没写过。于是我在逆境中激发出了潜能选择放弃（T2），仔细观察T1样例，脑中有了贪心的策略。先枚举每一个人，把他分到最满意的部门去，如果有多个最满意的就随便选，之后会进行调整。现在就是会有些部门超过 \lfloor \frac{n}{2} \rfloor个人，这时候就要把他换到另外两个部门中，还是根据贪心的原则，选另外两个部门中较为满意的分过去，但这时另外两个部门又有可能太多人了，所以要三个部门都看一遍，把多出来的人都调整，最后就符合条件了。但我又想到一个问题，就是一个部门要调走一些人时，选哪些人最优，我立马想到根据另外两个部门的满意度最大值来排序，但是测小样例就发现有问题，我又观察了样例，对比了正确的分法和我的分法，发现正确的评判标准应该是调到另外两个部门中较优的一个后满意度会减少多少，这时就优选选择满意度减少较少的人调走，对答案的影响会更少。现在整个流程就理出来了，先把每个人分到最优的部门，然后根据之前所说的满意度减少的差值对每个部门中的人进行排序，然后先看部门1，把对应的多出来的人数都分到部门2、3中，优先调走满意度减少较少的，然后因为部门2、3的人有变动，所以重新排序。接着看部门2、3，也重复部门1的步骤，最后人都分好了就直接算答案。写完T1，测过大样例，只剩1h了，我仍不甘心，又去看T2，但是最终还是在考场上留下了遗憾。

考完天已经全黑了，出来后直奔西湖。

晚上在酒店不敢自测

Day 2

听说-J人均AK，-S人均 \ge 150pts，于是心态崩了。

估分

J : 100 + 100 + 100 + 80 = 380

S : 100 + (16 + [0 ，玄学]) + 20 + 12 = [148 ，200]

Day inf

查分了

J : 100 + 100 + 100 + 68 = 368

S : 100(因为rp += inf) + 16(玄学即是0) + 0(暴力写不对???) + 12(暴力出奇迹) = 128(寄了)

后记

初赛游记

J : 92

S : 76.5

终于在OIerDB上留下了自己的名字！

明年的目标——

J: AK

S : [250 , 350]

明年还要住yyjt酒店，太好了！

3333字符&&114行