AHOIer 2022 CSP-J/S 初赛 & 复赛 VP 寄
Micnation_AFO
·
·
个人记录
话说洛谷能不能写一个可以查看历史版本的可持久化博客。
Day -1
还有两天，做几套初赛题和思维题加加 rp（。
上午下课的时候做了一本通初赛篇的提高模拟卷，发现选择题基本不会，可别寄啊/kk。
晚上六点五十的时候把之前被机房大佬 hack 了十几遍的题目做了一遍，之前一直卡在 Wrong Answer on test 2，现在是 test 3，不管怎么说有进步（
Day 0
0:10 的时候，把上面说到的那题 AC 了。tnnd 为什么学校星期六还要上课。
上午上课的时候做了三套模拟卷，有一套 pj 的做了 80+，题感还可以。
下午和傍晚做了 pj 的真题、模拟卷，基本都稳过，现在比较担心 tg 初赛。
晚上的时候 lg 好热闹啊，全是送祝福的，rp++！
然后与机房大佬玩了几局 Ac Saber，双方发挥都还可以，我打字有点优势，战况大概对半开。
睡觉前水了一道黄，看了一道紫打算第二天考场没事干的时候想。睡得比较早，检查了一下要带的东西比如零食、把博客背景图换成原来的头图之后，十一点没到就睡了。
Day 0.5
上午考普及，距离考场比较远，早上六点多就出发了。
普及组的试卷，看了一眼选择题感觉还行，最后一题洪水填充没学过，但之前听机房大佬说是图的遍历，所以不是很慌。
做的时候发现选择题比想象中的稍微难一点，不过我的选择题一向很差，主要是之前上课一点没听。
做到阅读程序的时候把我做炸了，第一题算出来总是没选项，先看了后面几题。
二三两题没什么思路，先放了，做后面的题目。
完善程序应该是这几年最简单的了。洪水填充第一次写，所以谨慎了一点。做完这些大概过去了 40 分钟。
然后就死啃阅读 T1，算累了就看看 T2 和 T3。后来发现阅读 T1 每次都是有一小步算错了，心态炸裂。
后面比较顺利地蒙完了阅读 T2 和 T3，判断题比较有把握，但是选择蒙的成分较大。
自己考场估分：20 + 20 + 30 = 70 。
总之，考得还可以，至少这个成绩在 AH 差不多能过了。
Day 0.75
提高试卷好难，一堆不会/kk。
第一题是同学强项，但是我对 Linux 一窍不通（，随便蒙了一个。
前面的选择题把我做傻了，感觉都特别难/kel。
然后就是看到了宇宙射线，当场笑死（，还有 for (j = 0; j < n; j *= 2) 是什么鬼啊。
排列组合做作业那道题，算出来是 \dfrac{C_8^2 \cdot C_6^2 \cdot C_4^2 \cdot C_2^2}{P_4^4} = 105，瞪了半天都没有这个选项，以为自己的做法假了，先跳过了。下一道排列组合也巨水，26^2 \times 10^3 即可，CCF 今年倒没怎么考我最不擅长的排列组合（。
这个时候差不多过去了 $\texttt{1h}$，T2 看了一半有点头疼，就去写完善程序了。第一个归并求第 $k$ 大数，属实没太看懂，勉强分析了一下连蒙带猜结合自己的分析选了一下。第二题倒水实际上还不是很难，分析了一下，意思看懂了，但是由于完善 T1 的原因，做 T1 的时间太久了，就先去看阅读 T2 了。
瞪了一会看出来是一个不基于比较的排序算法，但具体是桶排还是基数排序不清楚，之前也没学，不过由于很久之前查过一些资料所以知道我们常说的桶排其实是计数排序，所以最后一个选择题侥幸选对。剩下的两个选择一个可以简单模拟，一个不用脑子也能蒙出正确答案，比较稳，反而判断题有些危。
看了一下时间，还有四十分钟，先去做最后一题。
大概用了十几分钟选完了，自己测试了几组数据都对，应该没什么大问题。
后面就去蒙阅读 T3，然后考场当时降智，没看出来进制转换，勉强根据逻辑蒙了一下，基本没有稳拿分的题。
最后几分钟把有歧义的那道题仔细读了几遍，发现所谓分组可能仅仅只分 $1$ 组，于是迅速算出答案。后面检查了一下，交卷之前好像还改了一个选择题的答案什么的，但是都不重要了，~~反正都是蒙~~。
考场估分：15 + 20 + 25 = 60.
今年的试题比较简单，过线不能说 $100\%$ 稳（虽然去年分数线只有 $40-$）。
## Day 1
考完出来跟机房同学对答案，发现竟然最后一题大家几乎都全对，都是 `ACAAC`，然后有个同学跟我说他旁边的人考完说他最后一题全部蒙 `B`，默哀（（（。
回去的路上一直在聊天/对答案，一路上开着奇奇怪怪的玩笑，很有意思。但是没有 WIFI 和手机，上不了网。
晚上到家后，看了看洛谷和知乎，果不其然，大家都在说宇宙射线、题目有错和有歧义的问题。
然后：
1. 我草？？？阅读 T1 不是 KMP？
1. 我草？？？倒数第二题只对了一个？（不过后来看到不同版本的答案，对的个数也不同）
1. 我草？？？fx 博客说 S 组最后两个的代码都是假的？
《大 寄 特 寄》
不管了，都考完了，whk 还有一堆作业没写。后面复赛的时候再更。
## Day 2
问了教练，教练说我肯定能过，AH-WH tg 的分数线最多也不可能超过 50。
所以现在基本准备复赛了。打算把前几年的真题全部按考场环境 VP。
晚上写完作业浅浅对了一下答案，考虑到我记在纸上的答案不是我提交的答案，所以会与真实成绩有一些出入。主要看了 S 组的：
$24 + (7.5 + 8 + 3) + (9 + 15) = 66.5$。
好耶！又被机房大佬吊打！
晚上打 CF，希望不会掉分，不过今天状态很不好，赛前忘记报名了，只能等着 extra 了/kk。
CF 有一题没看到 $y \le x$，差点掉分！wssb！
## Day 10
按照通知，今天中午出分。不出意料，网站崩了。
然后帮大家一起改 URL 查分，最后通过 F12 去除验证码，然后用大佬给的链接，查出来了 S 组的分数，68.5。
J 组过了十几分钟，查出来是 77pts。
谔谔，J 没过 80，S 没过 70，看来彻底被机房大佬吊打了。几个朋友的保守估分都是 J85+，S75+。
## 10/25
AH 没了，AFO。
## 10/29
决定 VP 一下。
开场拿到 T1，想都没想扔了个快速幂，感觉稳了。
T2 充分吸收去年教训，5 min 不到打了暴力，随便推了两下公式，然后没什么思路先放了。
T3 之前就有推测是大模拟，一看题面长度就暂时放了。
然后开 T4，60pts 的无脑暴力 dp 很好想，在值域上 dp 一下，空间有点紧，但是大样例都过了。
然后把题目重新全部读了一遍，感觉暂时没什么问题，时间已经过了 $\texttt{50min}$，暂时估分 220pts。
后来又推了半天 T2，然后推出来一个二元二次方程组，其中有一个方程是一元二次方程组，所以可以代入消元，然后求根公式就行了。但是考虑到 $p + q$ 无法开方、精度误差等问题，我选择了二分：枚举 $p$，然后根据二次函数，两个数越近，且和不变，那么积越大，单调性就有了。随便写写过了大样例。
T3 读完题发现一眼典，直接用中缀表达式的方式算就行了。暴力递归，复杂度 $O(n)$，但是剩余时间没写出来。
最后民间数据得分 $90 + 100 + 10 + 60 = 260$，T3 前两档分数莫名没拿全，T1 未特判挂掉了 $10pts$。
## 10/30
VP 提高，时间：$\texttt{0:10}\sim\texttt{2:40}$、$\texttt{9:10}\sim\texttt{10:40}$、$\texttt{11:00}\sim\texttt{11:30}$。
T1 一开始的想法是暴力连边然后跑最短路，但是好像不太会处理最后如何回到起点。
后来先把距离每个点 $k$ 之内的连成一条边，然后就转化为了，如何找到一条起点、终点为 $1$ 的、长度为 $5$ 的路径，使其权值之和最大。
写完微调了一下，过了两个样例，最后一个大样例 TLE。耐不住性子，提交了一下，全 WA + TLE。
看了一会没管了，去开 T2，然后用十分钟左右打了 $60pts$ 的暴力，大概思路就是线段树维护每一行的最小值，然后枚举 $l_1\sim r_1$ 取其最大值，并没有挂分。
之后写了 T1 的暴力程序，然后开始想 T2 正解，过了挺长一段时间，由于时间太晚，所以先去睡觉了。
早上刚打开电脑 VP，就想到了 T1 最后找环的时候，路径不能重复，比如 $123421$ 是不合法的，于是改了一下，提交发现还是 $0pts$，不过数据经过加强之后重新提交了一下，是 $5pts$。
开始码 T2 正解。思路是开两棵线段树，分别维护 $a$ 和 $b$ 数组区间的正数最大值、正数最小值、负数最大值、负数最小值、是否有 $0$。然后对于每组询问，大概分了十几种情况分类讨论。写了很久，码了 $300+$ 行，然后就是一波乱调，过了两个小样例，这个时候被通知有事，临时走了。
回来测了两个大样例，最后一个样例在线段树 `build` 的时候就 RE 了，检查了数组大小、代码实现，发现都没什么问题。又过了十分钟左右，发现 `freopen` 写的是 `freopen("game.in", "r", stdin);`，但是我的输入文件写的是 `game4.in`，当场吐血。改完之后一次性 [AC](https://www.luogu.com.cn/record/92184863)，又长又臭的代码：[Link](https://www.luogu.com.cn/paste/7qllvmbc)。
~~不要问我为什么不用 ST 表，问就是我板子没背熟。~~
最后 $15\texttt{min}$，T1 跟暴力拍了快上万组了，感觉一点问题没有，此时严重怀疑 lg 数据有问题。最后手搓样例，打了一个 `1145141919810`，结果竟然输出不对，然后发现我没加 `#define int long long`（（（，加上之后 70pts，高于预期，也可能是 lg 的数据太水的原因。
最后得分 $70 + 100 + 0 + 0 = 170$，似乎比平均分低不少（？
upd：到 infoj 上测了一下，也是 $170$。
upd2：官方数据出来了，pj 90 + 100 + 5 + 60 = 245, tg 70 + 100 + 45 + 0 = 215，另外，之前 S3 写了全部输出 `NO` 的代码，但是认为 lg 数据不会那么水，所以没有提交，后来发现 lg 的民间数据也是可以得 $5$ 分的，所以 lg S 的民间数据应当是 175pts。