一个 CSP 游稽

· · 生活·游记

Day 0

11:45 出发。真是一个风韵犹存的时间呢。

14:15 到达，发现同学好像还需要 4 个小时才能到，所以开摆。

欸等等，我的准考证怎么被小明用墨水污染了？希望没事。

16:06 开始集训。集训的时候先开摆再说。

18:30 开始模拟赛。20/200 我也是个人物（

19:30 去逝机。

S 试机时发现了 CSP-Jer 的代码，大概是这样的：

#include <bits/stdc++.h>
using namespace std;

int main() {
  frepoen(
}

然后 ta 的编译选项是 -g3。还是 C++98 大佬。

为了表示对 C++98 大佬的尊敬，我试机完以后将编译选项改回了 -g3，并且将版本恢复回 C++98，为 ta 的比赛提供最好的照顾，让 ta 能够在自己熟悉的环境中比赛。

20:50 返回集训场所。又要开摆开始集训了。

21:50 集训结束。怎么这次这么晚？

22:30 洗洗睡吧。

Day 1

04:30 迷迷糊糊的起来了

05:00 又睡了

06:30 起床，吃饭，出发。

07:10 到考场。

07:50 进考场。感觉要废

07:55 发现默认的编译选项就是 -g3。看来不一定是

08:00 发现 C 盘是不可还原的（破天荒第一次）

08:15 看到全场都开始打缺省源了，我也开始默写我 61 行的缺省源。

CSP-J

上！善！若！水！

T1

08:48 打完缺省源开 T1。

没得说。欸，T1 题意是啥来着？

我用的是 std::vector<int> 存每个数字排序后输出。仅 3 KB。

T2

09:14 开 T2。

我第一个注意到的信息是 CSP-J1 没有保龄人。

不难发现第 k 个人坐在第 \lfloor \frac{k-1}{n} \rfloor+1 列。那我们就可以判断 列 的奇偶性，进而算出行数。

排序的问题交给 STL 解决！

T3

09:30 开 T3。

前缀异或和

前缀和需要一个运算和一个逆运算。例如加法的逆运算是减法，所以 S_i = S_{i-1}+A_i，所以 l 到 r 的和就是 S_r-S_{l-1}。而异或的逆运算是它本身，a \oplus b \oplus b=a。所以我们引入 前缀异或和 的概念，S_i=S_{i-1} \oplus A_i，A_l \oplus A_{l+1} \oplus \dots \oplus A_{r}=S_{r} \oplus S_{l-1}。

\mathcal{O}(n^2) 做法

维护一个数组 T，T_i 表示在 1 \leq j \leq n 且 j \in \mathbb{N} 的范围内，满足 S_{i} \oplus S_{j-1}=k 的 j 的最大值。这里选出的区间就是 [j,i]。

答案统计：维护一个 last 变量 s，表示我们选出的上一个区间的右端点。如果当前枚举到的 T_i>s 就可以选这个区间。

满分做法

忘了

T4

打了 40。注意 DFS 的常数，要不然就只能二十几来着。

CSP-S

人！杰！地！灵！

自己太菜了，摆了。

最终成绩

CSP-J：T3 挂分了，共 240。

CSP-S：100+0+0+0=100\operatorname{pts}。神奇吧（

S 组我是校队第一