2020 CSP-S 复赛游记

好久不见，距离上一次的 CSP-S 初赛游记又是一个月啦～

昨天，也就是2020年11月7日，我刚刚考完了本年度的 CSP-S 第二轮，几句话简单总结一下就是：

1582年的10月竟然只有$21$天？天文学家又为何需要计算$10^9$天后的日期？
动物园竟然饲养着$2^{64}$种动物？$10^8$种饲料又从何而来？
数据库软件竟内置了$10^5$个函数？又为何频频无响应？
决斗场上为何会有$10^6$条蛇？蛇又是为了什么而互相吞食？
为何选手出了考场都口吐芬芳，甚至想要亲切地问候 €€£ 外公的女儿？
为何全网都在寻找 T1 的出题人，想要和 TA 面基？
为何 €€£ 今年不考 DP？为何正式比赛变成了真•模拟赛？
组题人（不是错别字）又究竟受何打击？竟这样报复社会？

这背后究竟是人性的扭曲，还是道德的沦丧？请继续阅读本文（

P.S. 去年复赛滚粗记请移步：2019 CSP-S 复赛滚粗记

Day 0

因为今年 NOIP 恢复，CSP-S2 并不是最后一轮，学校不给停文化课，所以国庆集训之后就没怎么准备这次复赛了，导致我心里很慌

复赛前两天学校里又刚考完期中考试，身心俱疲的我还没好好休息第二天就去考复赛了

然后今年的复赛终于不用去长宁科艺了，自己的高中就是上海今年四个认证点之一，而且我被安排在我平时刷题的机房，监考老师就是自己的教练（狂喜

电脑是自己熟悉的 Windows 7 环境，而且有货真价实的 NOILinux 虚拟机！（狂喜x2

考试前一天晚上看了几眼板子（结果凡是我看了的一个都没考到），想起去年 D1T1 的格雷码就又去 OI Wiki 上认真复习了一下二进制，没想到我真的押中了，今年 T2 就是二进制、位运算相关的～

Day 1

上午还要在外面补文化课（累），上完课看了眼上午普及组的卷子，刷了刷灌水区，发现普及选手一片哀嚎…我预感下午不妙（果然…

下午提前一小时到自己学校，看到别的学校的选手都站在考场外等候，我熟门熟路地走到一楼角落的实验室，开了台电脑边等边摸鱼（这大概就是在自己学校的好处23333）然后大概两点十分就到楼上去考试了

到了两点二十五公布解压密码，我们考场竟然是手写在白板上的…应该学学人家长宁科艺，直接用极域发下来多好，都不用自己输

今年的 S 组的密码是“可以攻玉”的拼音中间穿插了“2020”，左右两边还有英文括号，中间的0oO、1lI手写在白板上完全分不清啊喂😂好在老师帮我们把各种情况都试了一下并注明清楚了，我密码一次输对

然后就是解压建文件夹一气呵成，开始读题…

T1 儒略日（julian）

题还没读完我就开始脊背发凉，倒吸一口凉气…

没错，是我最害怕的大模拟，它出现了！

所以 €€£ 为啥要在短时赛里搞一道大模拟呢？

由于看了 T2、T3、T4 感觉都不可做，我决定先肝这道大模拟，争取把它切了

首先想到的模拟思路是 Month-By-Month 进行模拟，用$year$和$month$分别记录年月，然后按要求模拟，注意各种特殊条件判断（比如闰年啊，公元前1年的后一年是公元1年之类的），处理好进位

写完+调试完就花了我一个小时…测完样例1和2后我还暗暗窃喜，以为就这样切了，没想到样例3超时，而且超的不是一点点

没办法，我打算继续优化，我突然灵光一闪，都 Month-By-Month 了为啥不 Year-By-Year 呢？于是又开始写+调试，又过了半小时，一测发现样例3继续爆炸，此时我的内心是崩溃的…

后来又想到公元后的日期可以从公元1年1月1日开始推，只要把$r$减去$1721424$（公元1年1月1日的儒略日），然而样例3还是超时

这时候突然想到了二分，但是一看距离比赛结束还有2小时，我果断先放弃，去做别的题（后来考完发现还真的可以二分

T2 动物园（zoo）

考试前一天晚上专门看了二进制相关的内容，真的派上用处了

赶快先默写了getBit()、setBit()、unsetBit()三个函数，看到涉及到$2^n$就先打了个表，用 unsigned long long 数组存储，然后就开始朴素的暴力模拟。先按照题目意思生成饲料清单，然后循环$0$至$2^k-1$判断每种动物所需要饲料在不在清单里，在的话就计数器自增，最后输出计数器的值减去已经有的动物的数量

测了一下依然只过了样例1和2，样例3超时，算了一下时间复杂度是$O(2^k*m)$，必超时

然后尝试想了十几分钟正解，也没想出来…就放弃了

T3 函数调用（call）

这题实在没啥思路，尽管看到数据范围里的特殊情况我就联想到了这题和树应该有点关系，但是也想不到正解

那就继续暴力模拟吧…继续过了样例1和2，没过样例3

问题就在于我一不留神数组开大了，当时也没算没发现，考完后发现了为时已晚，整道题抱零了TAT

T4 贪吃蛇（snakes）

显然不可做，以为是 DP 然而也没看出是啥类型的 DP，完全没思路

好在看到了数据范围里有$20\%$的数据是$n=3$，还是可以直接模拟做的，所以就打算骗到这个20分走人

四道题这样过完还剩下二十分钟，我又看向 T1，突发奇想能不能打个表？然后我就傻乎乎地开始打，然后逐渐意识到完全不现实啊喂，这么大规模的数据打表出来怕不是要有29TB，不仅时间不够硬盘也存不下更不可能交上去啊，浪费我十分钟

最后十分钟就啥也不干了，检查了freopen防止抱零，开了 NOILinux 虚拟机把程序都跑了一下，确认没有问题，到了晚上六点半准时提交了代码，最后签字走人

出了考场碰到了和同学汇合，然后大家开始不约而同地吐槽 T1 搞人心态，吐槽组题人 T2 明明比 T1 更好做为啥放在后面，有大佬说自己应该200pts稳了，我这个苣蒻瑟瑟发抖，我怕不是又像去年那样连50pts都拿不到，哭😭

2020.11.8

一大早搞到了自己的代码，开始用各大平台的民间数据自测，各平台之间分数都差不多，比我预想的要好一些

T1 50-60pts TLE（想尽各种办法优化还是超时）
T2 40pts TLE
T3 0pts MLE（数组开爆直接整题零分，哭晕）
T4 20pts WA（本来就是冲着20%的数据去的，还行）

总之大概就是110-120pts，至少我不是去年那个只拿23pts的废物了，也算心安了，这分数可能有个3=吧，2=应该别想了，希望 €€£ 的数据不会太毒瘤…

关于 €€£ 所谓的成绩优异者可进入 NOIP，也不知道复赛要达到什么水平才能进，希望只要没抱零都可以进（老希望工程啦

2020.11.17

终于出成绩啦～（原本说好16号的结果 CCF 咕咕咕了…害我白紧张一天

官方成绩120pts，比洛谷民间数据高了10pts，也比学校的 NOILinux 官方数据测评结果高了10pts，应该是 CCF 换了少爷机让我 T1 多过了一个点，€€£ 收了那么多钱总算办了点好事（

虽然排名还没出来但是据教练说今年 SH CSP-S2 一等线不到 200pts，所以 120pts 应该有个2=吧qwq也算是对自己一年努力的回报了

2020.11.20

顺利入围 NOIP 2020，竟然只要 2020 CSP-S2 没有爆零就能进😂毕竟 SH 有将近 $\frac 1 3$ 的选手爆零

接下来又要开始准备 2020.12.5 的 NOIP 啦…但是12月又是地理生物一模考（地生双选的痛苦），唉，又要忙死了

希望能在退役前的最后一场比赛拿个好看点的奖，加油吧…到时候会再写一篇游记的～

总结与反思

应该说这次比赛算是出其不意的那种，复习了好久的图论和 DP 一道也没考，尽管整体难度不及去年，但个人感觉还是并不好做的

然后就是写给自己下次 NOIP 和算法竞赛需要注意的（如果没有 AFO 的话）：

• 一定要养成直接写scanf和printf的习惯，这次全程cin和cout最后来不及改了
• 想清楚了再动手，避免写完一遍推翻重来
• 注意计算空间复杂度，别再开爆数组了

最后希望大家都能在 2020 CSP-J/S 取得好成绩，顺利进入 NOIP～