CSP2021游记

· · 个人记录

2021.7.20

占坑。

2021.8.23

今天开学了，中午回家看了下 CSP 的比赛时间，诶为啥初赛和复赛是星期六，可怜的我只能请假了。

2021.9.1

眼神不好，初赛是 9 月 19 号星期日。

2021.9.9

昨天结束报名了，离初赛还有一个多星期，有亿丢丢紧张。

2021.9.15

为什么星期天学校还要上课哦，真的非要请假了！！

2021.9.19

欧！今天考试，上午好紧张啊，默默的发了个说说
然后就去考试了。
到了二中，没想到还只有 1 个人，睡了一会后，考试的人都到齐了，但总共也只有 10 个人。
老师略讲了规则后便发卷子了，前面几个选择题连蒙带猜的一下子搞了一下下，快速进入了程序阅读题，第一个题是个数学题，但是我以为 acos(0.5) 是 π （结果事实是 \frac{π}{3} ），然后呢计算题就全部算错了，也没看出来这是求啥的。第二题 solve1 好像是个求和，但 solve2 我肯定是最大子段和。第三题我从上午懵到下午。程序填空呢第一题好像跟我之前出的一个题有点像，乱搞了一下。第二题我都看不懂题目描述，又是随便写了几个。到了 11 点，有人提前交卷了，而我却继续睡觉。
到了下午，有 29 个人，还有一个很胖很胖的一年级小学生承担了我的所有笑点。发了卷子之后，前面选择题——诶我咋都做过，诶最后一题不就是 p1809 过河问题嘛？妙啊这题挺坑的。 程序阅读题第一题，那个 x & -x 有点不是太懂，又蒙了一些，就看了第二题，瞬间崩溃，这不是上午那个恶心题吗，继续推了半个小时还是不会。第三题瞄了一眼题目，随便猜了几个又跳了。程序填空第一题，嗯这个题不是链表吗（约瑟夫问题），好吧这个使用数组模拟的，很轻松的就做完了。第二题是个结构体问题，但是答案好像跟我想的不一样，匆匆完成看了看时间还有1个多小时，睡了半个小时后，提前交卷，就跟着 cjh 到处乱逛。

比赛结束后，赶回学校上课。

放学后，根据肌肉记忆，对了一下答案，大概 tg 52.5, pj 67.5 ，湖北线肯定能过。

2021.9.22

教练跟我说我 pj 71 市最高分 ， tg 52 。

2021.9.27

成绩公布，确实是这些分数，努力备战复赛了！

2021.9.28

参加了 CF 的 div 3 只 A 了 A, E1 ，然后被被吊打了。

2021.10.22

晚上出发，去武汉，住一晚上。

2021.10.23

今天要考试了好开心啊，早上 7 : 20 就到了华科，没几个人，就吃着早餐，等待着同学们，不久，他们都来了，我们一起谈着等下考试的打算，说说笑笑的进考场了。
进了考场，我的座位号是 17 ，左边是信号屏蔽仪。我打开电脑的 wins10 -1 熟练地敲好了快读模板，监考老师说要打开 wins10 -2 ，所以。。。只能再打一遍。
把几个文件夹都建好了，老师发解压码了 6weid\n16384# 。

$ T2 $ 插入排序，诶这么这么熟悉，去年也是可以用插入排序，快速读完题，直接按照题意模拟一遍，$ 50 $ 到手，但是怎么优化呢？我想了想，发现了更改数据后，多次查询的数据不会改变，因此每次更改一个数字，只需要重新排一次，现在是 $ O(5000n^2) $ ，我又想了一会，想起来插入排序具有稳定性，每次排序都会确定至少一个数的位置，因此每次修改一个数，这个数只可能向前移或者向后移，因此也就不需要整体重排了，只需要正反两个方向排一遍足以，最后 $ O(5000n) $ 足已通过，在 $ 9:45 $ 左右写完了。 $ T3 $ 网络连接 看到题目，本来以为是个最短路，读完题，结果是个大模拟，很简单，没什么好说的，只有 $ check $ 判断是否合法复杂一点，码量稍大，考验人耐心。在 $ 10:05 $ 我过了所有样例，还剩一个半小时主攻第四题。 $ T4 $ 小熊的果篮 看到题目，一眼就认定是区间 $ dp $ ，再一看范围 $ n=2*10^5 $ ，好吧否定。先按题目说的，打了暴力的 $ n \le 1000 $ 的 $ 30 $ 分，此时 $ 10:40 $ 。闭目养神想了一会会，发现当进行操作，如果连续的未删除的那一连续的一串为 $ 1 $ ，下次操作就不存在了，从此一个很重要的结论，当这样连续的串有奇数个，那么前后两个串可以直接相连，然后跟着这个思路，我用双端队列（应该是链表，当时不知道叫啥，瞎写的）维护当前序列的左右端点，但合并的时候很明显有很大的问题，因而我没调出来，在 $ 11:30 $ 的时候，我发现这个方法行不通，果断的放弃了写，把刚刚的暴力代码复制过来，能混一点是一点吧。 交卷后，我感觉自己考得蛮不错的，没想到他们说这次好简单，考到高分不是很难，分数线因此也会很高，我自己也估了一下 $ 100 + 100 + 100 + 30 = 330 $ 。 中午吃了一点好东西，回到酒店休息了一会，突然发现 $ T4 $ 的代码好像时间复杂度没有这么高，应该可以过更高的点，但是 $ T1 $ 枚举 $ n $ ，如果数据严一点，就超时了，那就暂且估 $ 80 + 100 + 100 + 70 = 350 $ 。 下午同样是到了考上，等待着同学们，与他们一起进去。 这次我结识了一位好友，他叫 郝仁 （好人哈哈） ，这次的解压码是 $ 21!9-324@emb $ 。我偶然的发现了留在这台电脑里的上午的考生的代码，我从容地点开，第一题他直接枚举的，数据卡一点，超时送给他，第二题，直接是 $ O(5000n^2) $ 模拟，后面就没看了，开始考试了。 $ T1 $ 廊桥分配 ，读完题后， $ 10 $ 分钟很轻松的写完了 $ 40\% $ 的暴力，然后呢...然后就没有然后了，这就是这题所有的思考，枚举两个机场的个数，用堆来维护停的机子，时间复杂度 $ O((m1+m2) \log n^2) $ 。 $ T2 $ 括号序列 ，读完题，嗯区间 $ dp $ ，定义状态 $ f[i][j] $ 表示以 $ i $ 为左端点， $ j $ 为右端点的串的总方案数，方程...写不出来，此题完结，乱写了个暴搜，样例都没过，就丢了。 $ T3 $ 回文 ，读完题，没思路，当然是继续暴搜，枚举每个数取 $ L,R $ 时间复杂度 $ O(2^n) $ ，可能啥都过不去，看到有一个特殊数据，差不多就是 $ LL $ 或者 $ RR $ 的输出，但是考试时候没咋看懂，多写了一个判回文，直接输出 $ n $ 个 $ LR $ ，否则直接 $ -1 $ 。 $ T4 $ 交通规划 ， 没看懂题，把数据输进去，把样例全输出了，然后还有 $ 2 $ 个半小时，硬是摸过去了。 出了考场，同学们说他们也跟我差不多，只会第一题一点点暴力，于是我们一起喷出题人。。。 然后估分 $ 40 + 0 + [0,40] + 0 = [40,80] $ ，应该能过二等线吧。 所以总结结论，今年 $ pj $ 简单，线会很高，但是 $ tg $ 很难，线会很低。 回到家后，浴谷自测 $ pj $ ，$ 100 + 100 + 75 + 70 = 345 $ ， 计蒜客 $ 100 + 100 + 90 + 70 = 360 $ , 小图灵 $ 80 + 100 + 100 +40 = 320 $ , $ T3 $ 仔细思考发现，还是有一个没考虑，然后改了之后才过。所以，综合起来看，就是差不多 $ 350 $ 。 $ tg $ 数据还没出完，现在 $ T1+T2 $ 很稳 $ 40 $ ，希望 $ CCF $ 没有把数据出的很毒。 $ 2021.10.24

为什么当时考试的时候没有把空间开大一点啊，只开了自认为能过的点，然后刚刚就发现还可以卡过一两个点，真后悔。

2021.10.30

官方分数

pj : 90 + 100 + 75 + 70 = 335 tg : 40 + 0 + 0 + 0 = 40

看起来 pj 一等稳了， tg 应该是二等。

2021.11.5

官方这么快出成绩了呀， pj 一等， tg 二等。

完结撒花✿✿ヽ(°▽°)ノ✿