CSP2025邮寄

· · 生活·游记

省流急速版

:::warning[你可能会笑死，请斟酌后点开] j:100+100+70+40=310

s:100+0+8+3=113 :::

day -inf

S 模拟赛，打了两场，第一场 250pts，第二场 5pts，感觉良好。

10.31

周五，jx 下午三点才放学，我们火车也在三点，所以中午起床直接跑路。

到了济南东火车站，在站台外拍了一张帅照，和两年前打小学组一个位置。到了站台发现全是 OIer，但没有我们学校的。我戴上【某机构名称】发的帽子，准备蹲同学。火车开始检票时蹲到了 @Alex866，他塞给我一盒薯片就逃跑了。

车上写作业，干掉了语文卷子。lyx 火车上啥也没干，看他返校怎么说。

下午五点到日照，天都黑了。去办入住，发现隔壁就是考场，办入住的时候还看见不少认识的人。

晚上去试机，发现 j 和 s 机器在同一个考场，还挨着（

试机完后回酒店。florr，启动！（好吧酒店无线太卡了

10.32 11.1

七点起床，准备去打 j。到了考场，居然让动电脑，打了一个有点癫狂的缺省源。我是 SD-J00628，大家可以在 SD 迷惑代码大赏里找到我。（大概

8：30 开题。这 T1T2 都啥啊，T1 十分钟秒掉，T2 注意到输出先列在行卡了我十五分钟。

T3 有点强度，一开始想的按位考虑，感觉不对又想的大炮，还是不对。发现满足条件的区间一定越短越好，想到对于每一个位置 i 找到最近的 r_i \le i 满足 a_i \oplus a_{i-1} \oplus \dots \oplus a_{r_i}=k。求出来 r 之后跑贪心，把每个 r_i 转化为区间 [r_i,i]，看看区间 [1,n] 内最多能放下多少不相交的区间。这样套一个异或前缀和求 r 数组是 O(n^2) 的，贪心 O(n)，考虑优化。

我刚写完几秒钟就又瞪出来一个性质。我们在上面为了保证每个 [r_i,i] 长度最短，每当我们发现一个左端点为 r_i 的区间 [r_i,i] 满足条件都需要更新一遍 r_i。但我们发现当对于一个左端点是 r_i 的区间满足条件后，因为我们是从小到大枚举的 i，那么对于后面的 i 区间长度肯定比第一个满足条件区间长度更长。也就是说，每个 r_i 值最多只会被更新一次。当我们发现一个 r_i 被更新了，后面的 i 就不必枚举 r_i 这个位置了。

因此，我们维护一个双向链表，开始链表里存着 1,2,3,\dots,n，每当我们发现一个 r_i 被更新了，就从链表里把 r_i 删去。对于每个 i 都遍历链表，只用链表里剩下的值判断是否满足条件。当发现一个链表内的元素 x 满足 x \le i 且 a_{x} \oplus a_{x+1} \oplus \dots \oplus a_i=k 时，令 r[i]=x，并从链表里删去 x 即可。正确性是显然的，大样例是全过的，思路是没人和我一样的。

打了 2h，终于过了 T3。T4 什么玩意，打了一个 set 没调出来，只能写 dfs，感觉有 40pts。

估计总分 100+100+100+40=340 分，应该能过（

中午回去睡了个午觉，准备下午打 s。

14：30 准备开。对了我是 SD-S00441，大家也可以去迷惑代码大赏里找找我，缺省源依旧疯癫。。。

开 T1，woc 什么玩意，不会是 dp 吧？一开始让 dp_{i,a,b} 表示前 i 个人 a 个一组 b 个二组，但发现时间空间都不对。题目求的最大价值，数据范围 n \le 10^5，显然是 O(n) 或 O(n \log n) 算法。下面是一些我的心理描写：

A：复杂度有点低啊，要求最值，难道是二分？

B：怎么可能，他有单调性吗，糖糖糖

A：那是线性大炮？

B：放，线性大炮至少得两维啊

A：开三个堆？

B：……说话过一下脑子行吗

A：woc 我会了，贪心

没错，这题是贪心。注意到题目中 n 是偶数的条件很奇怪，又联想到 \frac{n}{2} 这个奇怪的限制，发现性质：

这个性质启示了我，能不能用一种类似反悔贪心的思路。我们不管人数限制，先让每个人站到最优的组别，如果人数满足限制直接输出答案，否则找出人数超限的组别，把这个组别内的人按“把这个人放到另一个组别后会令答案少多少”从大到小排序，一直取大的，直到人数刚好为 \frac{n}{2} 即可。复杂度 O(T(n \log n))。

花了 1h 写完代码（不包括思考时间），只剩 2.5h 了，开 T2。woc 我不会，打一个 k=0 的最小生成树看 T3。这题正解是不是完全图上跑 prim？存疑

T3 居然是字符串，有点意思。不难想到哈希，一开始写了一个双模的，最后不会写了，改成单模了。我哈希参数是 base=1331,mod=998244353，ccf 不要卡我 orz

写完之后小样例全过，大样例都没过。花了 10min 造了一个 hack，hack 通过后大样例依然没过。只剩 1h 了，去打 T4 暴力。

打完了，估分 130。

感觉自己炸了，因为出考场发现 T2 暴力没开 long long，而且 1h 想到正解。。。

10.3711.6

查成绩。详情见文章开头。

其实我看到这个成绩之后并没有伤心，反倒感觉我自己挺厉害的。六年级时我甚至场切不了黄，现在已经有了场切绿的水平，这种提升让我欣喜到现在。

稍微扯一扯我在学习上的事。周六去 csp，下周二就期中模拟考。我每天晚上晚自习都去机房，文化课只能课间补。别人都说这样没有意义，因为一年前的我在 OI 上还是一个【数据删除】，这一年我真的成长太多了。

不急，我才初一。

我真棒！

结尾

推销一下我去年的 CSP-J2024邮寄，通过它你就知道我去年多菜。

CEXE 好闪，拜谢 CEXE。