CSP2019 回忆录

本来题目想写「游记」的，但是因为我的博客一直咕着，过了都快一年，所以就改名为「回忆录」了。

下接 CSP-S && NOIP2020 爆炸记。

Day 1

在车上还是有点紧张的，毕竟这是我第一次参加 CSP，踏进熟悉的附中校园，在求索碑前点了个名，然后便开始等待入场。

想了想，大概去年的提高组能考个 $420$ 分，于是想着今年也往这个分数冲，考前也在 luogu 上签了个到，祝了一下自己 rp++。

但事实证明我还是太菜了。。。

开考先看 T1，看了大概十分钟，发现反推模拟一边就可以得出答案，之后边想边写花了 $20$min，测完大样例已经过了半个小时。

然后开始看 T2，首先敲了一个 $O(n^3)$ 的暴力上去。那时码力低下，光是写这个就花了我半个小时，时间已经过去了一个小时。

然后开始想正解，想了一小时 $15$ 分钟还是只会 $O(n^3)$（真不知道那时候我的脑子在干嘛），于是先看 T3。

T3因为本来就没想要正解，所以直接开始敲 $O(n!)$ 的10分暴力，这次没有失误，$7\,\text{min}$ 就写完了。然后去看链的部分分，一开始有一个贪心的想法，但是后来发现假了，所以去看菊花的部分分，还是不会，于是回头想 T2，这时只剩半个小时了。

想了 10min，发现可以统计以一个点为尾的个数，不需要枚举子区间，于是会了 $O(n^2)$ 的做法（当时甚至不会想到用栈进行转移），马上开始写，最后 10min 写完。

检查一下文件名啥的，再想想 T2 正解，最后无果，考试结束了。

刚考完出来感觉自己可以退役了，第二题居然没有做出来。出来问问同学，同届最强的两个想出来了，其他都是 $50$ 分，心里稍微平衡了一点。学长说，T2 直接用一个栈把链上的情况搬到树上就行了。仔细拍脑门想一想，发现在栈内的点就是根到这个点的路径，然后我就会了。。。感觉自己好蠢。

然后学长一直在大喷 T3，大部分都是 $10$ 分暴力，zky 学长加上了菊花图的 $25$ 分，然后 cy 学长想出了正解，但是细节巨多，也不知道可不可以 AC。

大概和大佬们的差距是 $50$ 分，还可以接受。。。

预估得分 $100+50+10=160$。

中午睡了一觉，下午来参加普及组。

开考看 T1。。。$1\,\text{min}$ 秒杀。然后看 T2，开完题目就知道模拟，当时想的链表做到 $O(1)$ 修改，但是看了看数据范围，发现直接数组暴力实现就可以了，$15\text{min}$ 敲完，这时过了半个小时。

接下来看 T3，想了 $1$h，还是想不出什么，突然看到 $T=2$ 的部分分，这需要一个完全背包就可以了。突然有了想法：直接做 $T-1$ 次完全背包！然后我开始验证这个想法，发现每天肯定手上要钱最多，那么前一天就要最优策略，于是做 $T-1$ 完全背包。回忆了一下完全背包怎么写，写了 $30\text{min}$，过了大样例，这时还剩一小时 $15$ 分钟。

然后看 $T4$，想了半个小时还是只会 $30$ 分，又花了半个小时写完（我当时的码力。。。唉。。。），然后就没什么时间了，检查一下文件名啥的，考试就结束了。

考出来后发现同校的 LinZhengyu 与 ChenHanlin 两位大佬都 AK 了，还有一位初二的学弟也 AK 了。他们说 T4 直接求奇偶最短路就好了，比 T3 还要简单，感觉自己好蠢啊。。。

预估得分：$100+100+100+30=330$，没有 AK，还是太差了。

晚上去各大 OJ 上测自己的代码，普及组和预估的一样，但是提高组的有点出入：T1 少了 $5$ 分。

定睛一看，发现 1<<i 有问题，虽然我开了 ull 但是我的 i 有到 $64$，会爆 ull，不禁懊悔，为什么当时不测一下极限数据。

Day 2

考前还是和第一天一样，但是今天我不抱着什么希望，只求 AC 一题，剩下的暴力多骗一点。

事与愿违。。。

开场把三题都看了看，看完后先去想了想 T1，想了 $45\,\text{min}$ 还是只会 $64$ 分做法，其中的 $32$ 分的 DP 很难写，所以第一题先不写，溜去看 T2。

T2 和 FCS 集训的一道题很像，式子大概推了半个小时，我把平方和变成合的平方减去积的和，然后合的平方可以 $O(1)$ 算，积的和可以和 FCS 集训的那题一样 $O(n^2)$ DP，于是我开始写，前前后后写了 $35\text{min}$，没过大样例。。。于是开始调，查出来大概一个错，然后把 ll 换成 ull 就过了大样例（但是照常理是不需要 ull 的，但是我这个不知道为什么不开 ull 就会挂），这时候已经过了一小时 $45$ 分钟。

回头去写 T1 的暴力，前 $32$ 分的 $10\text{min}$ 就写完，但是后面的 $DP$ 整整写调了一个小时还是没法过自己造的数据，就自闭，这时只剩 $35$ 分钟了。

赶紧看 T3，前 $40$ 分就是暴力求树的重心，但是我写了半个小时，最后五分钟惊险写完，还想看一看链和满二叉树的部分分，可刚想出来考试就结束了。T_T

出来后发现同届的两个大佬和学长至少都是 $64+64+75=203$，而且学长大部分都把 T1 做出来了，nb 的还把 T2 和 T3 写出来了，被暴打了。。。

预估得分： $32+64+40=136$，晚上去各大 OJ 上测评也没什么出入。

最后的实际得分 PJ： $100+100+100+30=330$，TG： $95+50+10+32+64+40=296$，省一确实都是拿到了，TG 大概全省 $90$ 名的位置。看了看今年的分数分布，再次感慨 OI 难度增长速度太快了，感觉自己水平的增长速度都赶不上它。

总结 && 展望

现在的我，已经要上高中了，回看初三这一年，有欢笑、有伤心、有悔恨、有收获，虽然不敢说成长很多，但是还是有成长的。祝自己的高中生活过得顺顺溜溜的，还有 NOIP2020 rp++！！！