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

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

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

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

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

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

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

七点起床，准备去打 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)$ 算法。下面是一些我的心理描写：

没错，这题是贪心。注意到题目中 $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 想到正解。。。

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

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

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

不急，我才初一。

我真棒！

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

CEXE 好闪，拜谢 CEXE。