CSP-J/S 2020 游记

初赛

Day 0(2020.10.10)

今天上周五的课，本来下午第三节班会课想上机房去的，但又觉得还是在教室里做做 whk 作业比较好，结果没想到一上课班主任就进来开始讲作文，最后题也没刷成，whk 也没做，真是失算了。。。

班会课下了之后直接上去机房，先颓了一会红警，晚上的时候教练给我们发了一套模拟题来做，真的把我心态都弄炸了，选择题就难得跟什么一样，有五六道都是猜的，后面就更不用说了，根本不知道那些程序是想要干什么，只好随便看一看，然后蒙一个答案，最后只得了 65pts，yzh 和 lyx 还有 ys 巨佬都比我高，这怕是要退役的前奏。接着顺便又花了大概一个小时把洛谷的模拟题做了一遍，好几个题都没有好好想，也是随便整了一个上去，还好得了 76pts，不然是真的要自闭了。

早点睡吧，希望明天能拿个好成绩，放几张图片在这里，便于膜拜以增加 RP。

Day 1(2020.10.11)

早上的时候膜拜了一下巨佬的照片，打开洛谷后发现大家全都在祝自己 RP++，我也发了一个帖子，但好像没什么人回复。。。

8 点从家里出发去学校门口集合，初二的居然也来了，而且还是倾巢出动，现在连初二的都这么强了，能来考 tg 了，我们当年初二的时候还只参加了 pj，看来这是要被后辈碾压的节奏。。。

ZJK 神奆居然也来了，还有 WKR 巨佬，他们两个怕不是来给我们拉高分数线的吧😨

跟去年一样，学校给我们弄了一辆公交，一辆貌似是学校自己的大巴，上车之后没什么事可干，打了一会暗影格斗和几何冲刺，膜拜了一下某位同学打印的图灵的照片，顺便和他们合了几张影，就到考点了，人倒不是很多，只是感觉很有压力吧。上楼找到自己的考室，没想到 lyx 居然跟我同一个考室，还坐我旁边，说不定到时候有数学题可以瞟一下他的（滑稽

tg 的考试感觉还可以吧，选择题没什么太大的难度，只是有点坑人，比如有道选择题，看似是一道十分经典的考栈的题目，没想到最后问的居然不是栈顶，而是栈底元素，这完全就是考人细心了吧，还好我读题算比较仔细，不然要是错了真的有点亏，阅读程序也还可以，起码知道这个程序在干啥，第一题应该就是一个暴力求解，第二题是用类似快排的方式求序列中的第 k 大值，第三题是一个双向广搜，它闲着没事干手打了一个 map 和 queue（关键是 map 还不是跟 STL 里面的 map 一样用的是红黑树，而是直接一个数组记录对应关系。。。），具体实现的应该是这样，假设把一个字符串第 $0$ 到 $m$ 位左移一位或是 $m$ 到 $len-1$ 位右移一位称为一次操作，求将一个给定字符串变成一个给定状态最少需要多少步（语文不好别在意），整体感觉还可以，除了第二题老是问时间复杂度外其他的都还不算特别难，补全代码第一题有一点点弱智（相对于一般的提高组初赛难度来说），第二题就有点难受了，不太搞得懂它的算法，只好根据题目中给的每个变量的意思来猜答案，预计可能会错很多

回学校途中又打了一会暗影格斗，中午在学校吃完饭，不想回寝室睡觉，毕竟只有不到半个小时，就跟 yzh 和 ys 在学校里乱逛（yzh 说他考试的时候旁边坐的居然是 ZJK，只可惜没抄到他的答案），碰到 wlm 回教室写作业，于是就跟着他跑到他们教室里去打了一会游戏（成就达成：在学校教学楼里公然拿出手机打游戏），主要是其他人还在放周末，没回校，不然我们绝对是不敢的

下午人可就多起来了，进考点的队伍排了老长，终于挤进去的时候离开考只有 10 分钟了，这次考室里没有熟人了，但有很多都是我们学校的，光是前两排 12 个人里就有 6 个穿着我们的校服（虽然一个都不认识。。。）

pj 果然没有上午那么难受，整体难度都小了很多，看来还是有希望的，起码应该不会 AFO 了，前面的题就不说了，阅读程序还是一样除了第一题不知道它到底想干什么，只能手动模拟，补全代码是真的有点弱智，一个质因数分解，一个什么最小区间覆盖，说实话，第二题本来我还觉得可能有点挑战，结果题面给了那么多提示，一点难度也没有了，考完感觉还是比较欢乐的，hx 跟我们说他居然在草稿纸上写了一篇 1000 字左右的议论文，题目好像是《论红警盟苏两军的优势和不足》，有点记不清楚了，结果他没想到草稿纸是要收的，导致他 40 分钟的努力全部木大

回校的路上终于把几何冲刺的第一首歌给打通了，看来我还是太菜了。路上还看见很多返校的，当时就差没有打开窗户跟他们打招呼了

晚上上完晚自习回家之后在洛谷上看到了粉兔发的 tg 的试卷和答案，索性对了一下，结果错了不少，尤其是最后一题，五个选择题错了四个。。。最后总分应该是 73pts 以下，有两个判断题我记不太清楚了，但应该八九不离十了，希望 SC 的分数线不要那么高，我可不想第一次参加 tg 就在初赛跌倒。

复赛

还好没有在初赛时就被刷下来，pj 87pts，tg 71.5pts，几乎是踩着线进的复赛，话说今年 SC 的线是真的高，跟 ZJ 都只差一分了。。。

Day 0(2020.11.6)

今天还是在机房度过，早上本来计划把 KMP 推 next 数组的那个过程再看一下的，结果一到机房发现全都在颓废（听有些大佬说考前 TF 是我们机房的传统？），我还是把前一天考前模拟爆零赛的 T3 改了，稍微看了一下 lg 上的一些模板题，了解了一下威佐夫博弈，看了一下 KMP，然后就也加入了 TF 的阵营，颓了一上午 wings，还跟旁边的大佬打了几把 generals（被虐爆了。。。）。临近吃饭的时候突然觉得还是应该切两道题练一下手，于是做了一下 14 年 tg 的联合权值和寻找道路，虽然是两道绿题，不过真的有点水，联合权值就是分两种情况讨论，然后一遍 DFS，中间维护三个值，就可以算出答案了，不过因为把模数弄错了，本来题面是要求模 $10007$，但我在代码里打的却是const int mod=1e5+7，交了两遍才发现这个问题，寻找道路是真的没什么说的，先一遍反向 DFS 找出哪些点与终点联通，然后枚举所有边标记哪些点不能出现在路径上，最后一发 BFS 完事，老实说要是 tg 的题都是这样的话，那感觉好像也没什么好怕的然而事实并不是这样的。

下午又颓了好久，有一个教练坐在讲台上，一点用处也没有因为是小机房所以没装云课堂，好多人都在颓你画我猜，教练问起来他们还说是在复习算法，就是一个人来画图，然后其他人根据图和提示来猜是什么算法，关键是他们还特别大声，有人还大声喊你这个无向图怎么可能是强连通啊，我还是跟上午一样颓 wings，不过好像还有很多人也在颓，据我们估计，wings 那个榜上的前十名里面至少有五六个都是我们这个机房的。。。

晚上跟教练请假回家，路上买了个面包当明天早饭 7 点从学校出发是真的离谱，回家后颓了一下 Malody 和 osu!，老实说不是很喜欢 osu! 的那几种模式，感觉看起来太花哨了，有点难受，虽然谱面是真的多，但是游戏体验其实没有多好，可能还是习惯了 Malody 那种，尤其是 osu!mania，感觉还很不一样，那种滑块居然是要在合适的地方松手才能拿到高分，不像 Malody 只需要一直滑到底就行了，之前一直没搞懂所以分数都很低，后来总算是明白了，但还是不太会，于是最后果断弃了 osu!。

睡觉前拜了一下 ZJK 神仙，希望他能保佑一下我

Day 1(2020.11.7)

真的不人道啊，早上 6 点 20 就起床了，收拾收拾又膜了一发 ZJK 巨佬就上路了，到了学校门口发现只有一群初二还是初一的，过了一会才来了 hx，早饭还是在学校门口啃了面包，上车之后开始补觉，用 MP3 听了会歌，到了电子科大之后对着 mzx 和 sjx 以及 hfy 等一众大佬隔空膜拜了一发之后就进考场了，机子跟去年几乎一模一样，没什么变化。正在默默祈求大佬包佑的时候，旁边那个人问我 find 函数怎么用，一开始我没听懂，他说了三遍才听清楚最近耳朵有点不好使了，然后我问他是 string 的那个还是 set 的那个，他不知道 set 是什么，我就解释了一下，然后跟他说我不会用 string 的 find，聊了一会之后，我发现他居然对图论一点也不了解，搜索也只是听说过，做了些走迷宫之类的题，而且他还是初二，老实说我觉得他有点危，不过他自称对 DP 比较熟悉，应该可以弥补一下，他还说这次考完他就不整 OI 了，我一开始还以为是他 whk 太差以至于老师和家长不让他继续了，没想到是他自己不想搞了，他还说他一开始就不是自己想来的（貌似是这样吧，这一段我没怎么听清楚），最后我还是鼓励了一下他，让他争取在 AFO 之前拿个 1=。

上午-PJ

上午的 pj 还是比较简单，T1 傻逼二进制，奇数就输出 -1，偶数就用 lowbit 乱搞一下就行了，大概开考 20min 就切了。

T2 想了一会题意，没搞懂到底是按成绩来还是按人头来算，比如如果成绩是200 200 100 100，那排名到底是1 1 2 2还是1 1 3 3，最后决定应该是后者，然后就开始想怎么整，最开始我想的是整一个 multiset 来维护成绩，后来突然想到这玩意不支持随机访问，要查询第 k 大值只能 for 过去，很有可能会被卡到 $O(n^2)$，想起早上还是昨晚看到的一个用 vector+lower_bound 实现和 set 一样的功能的有趣的方法，于是果断用了那个（当时还觉得既然有 set 了为什么还要搞这么花里胡哨，现在想想那玩意最大的好处就是可以随机访问），最后复杂度 $O(n\log n)$，$10^5$ 的数据应该是没什么问题了，即使是 CCF 的老爷机也能行。

T3 一开始没怎么弄懂，决定先看一下 T4，看了一下 T4 之后觉得应该是个 DP，于是又回去看 T3，这次先是打了一发 $O(|s|q)$ 的暴力，然后考虑优化，发现其实有些变量即使发生改变也不会影响到整个表达式的值，比如 $x_1\lor x_2,x_1=1,x_2=1$，这两个变量任意一个变成 $0$ 都没有影响，但如果是 $x_1\land x_2,x_1=1,x_2=1$，那么这两个变量任意一个变成 $0$ 都有影响（我将其称为关键的变量），所以可以先预处理出整个表达式的值，并且算出哪些变量是关键的，如果反转的是关键的变量，那么整个表达式的值一定会反转，反之则一定不会，这样下来复杂度就是 $O(|s|+q\log q)$ 的，就没什么大的问题了，不过不太清楚是不是对的，而且中间用了一大堆 vector 的骚操作，什么 insert 啊，assign 之类的都用上了，还开了一个存储类型是 vector 的 stack，有点怕玄学 RE，虽然大样例是过了，但这常数肯定得上天。

T4 先想了一下能否用一些折半之类的搜索技巧，没想出来，于是还是决定用 DP 来整，用 $dp_{i,j,0/1/2}$ 分别表示从上边，左边，下边走到 $(i,j)$ 的最佳方案，不过从下方走上来要分开计算，最后整了个三个循环，几个样例都过了，就没再管了。

然后开始用 NOI Linux 虚拟机测代码，因为之前没用过虚拟机，所以以为不能把代码直接拖进去，只好一个一个复制，后来才发现是可以的，测完之后没什么问题，开始想着要不要对拍一下，T1T2 没什么必要，T3 生成数据太麻烦，于是就开始拍 T4，不知道为什么一开始脚本老是有问题，后来发现是暴力程序的文件名不太对劲，改了之后居然拍出一个错来，当时离考试结束只有 20min 了，然而我以为是 12 点 30 分才结束，于是开始不紧不慢地查错，修了那个锅之后正要重新开始拍，监考员突然提醒不要在 CSP 目录下建子目录，我才知道原来是 12 点整结束，吓了一大跳，急急忙忙拍了 100 组很小的数据，都过了，然后就没管了，连样例都没测就走了。。。

中午的时候我们只有五个人既要考 pj 又要考 tg，于是去电子科大旁边找饭吃，mzx 和 hfy 巨佬去吃粉了，hyf 自己去吃面，我和另外一个叫 xzq 的初二巨佬跟着教练找了个家常菜馆子，点了水煮肉片，莴笋木耳肉片，鱼香肉丝和紫菜蛋花汤仔细一想突然发现全是荤菜，我没怎么说话，倒是 xzq 和教练聊得挺高兴，过了一会其他人都吃完了，我们菜都还没上齐，于是只好一边吃一边等，不得不说确实要比学校食堂好吃多了，连教练都在吐槽学校食堂太难吃了。

饭后买了瓶冰红茶，在考场门口用手机打了会 Malody，又膜了一发活的 ZJK 巨佬，就进考场了。

下午-TG

老实说刚进考场的时候还是很紧张的，因为是第一次考 tg，没什么经验，怕拿不到 1=，但过了一会就好了，没那么紧张了。

试题密码上午下午连起来是他山之石，可以攻玉，我觉得这还不如去年的认真检查。

T1 着实把我恶心到了，光是读题就花了我 20min，因为想着一定得把 T1 做出来，所以就没管后面的题，这玩意是真的难受，我小学学奥数的时候就很不擅长日期计算，这还给我整个公元前 4713 年，我就是把计算器扣烂了也没办法算出来离公元 1 年差了多少天啊，最后反正用了一些玄学的方法，把整个日期的计算分成了四段，即公元前 4713 年 1 月 1 日到公元前 1 年 12 月 31 日，公元 1 年 1 月 1 日到公元 1582 年 10 月 4 日，公元 1582 年 10 月 15 日到公元 1582 年 12 月 31 日以及公元 1583 年 1 月 1 日到以后，前面三段我都算是处理好了，起码把第一个样例给过掉了，但最后一段硬是整不对，$3000000$ 的数据算出来是 8 月 10 日，$4000000$ 的数据算出来又是 7 月 14 日，一个少 $5$ 天，一个多 $2$ 天，关键是这玩意调都没法调试，我**怎么知道公元前 4713 年 1 月 1 日之后 $3000000$ 天是哪一天啊！调了一个半小时都没弄对，最后还是放弃了。

T2 就比 T1 舒服多了，做法比较显然，先算出购买清单，然后根据要求排除一些不能为 $1$ 的二进制位，最后算出总方案数后减去 $n$ 就行了，不过要开 unsigned long long，算是一个坑点，而且说实话 $k\le 64$ 这种数据也恶心了一点，明摆着就是要卡你啊，另外，最后五分钟的时候我把代码在 NOI Linux 虚拟机下测了一发，发现 scanf 的 %u 格式控制符报 Warning 了，意思是 %u 是 unsigned int 的格式控制符，但这里我用的是 unsigned long long，急急忙忙改成了 %llu，还好对了，不过听说 mzx 大佬打的是 %ull，恐怕会 CE。

T3 看了一下，不怎么会做，打了一发 DFS + 分块的暴力，T4 拿了两个堆维护了一下最大值和最小值，小样例过了，但大样例不知道为什么有些答案会多 $1$。

总体来说这次 tg 就是十分爆炸，考完后果然很多人都在说 T1，老实说一开始我是想问候格里高利十三世的，不过后来决定还是问候出题人好了。

回学校的车上没什么事干，就开始打几何冲刺，没想到旁边那个高中的巨佬居然也打，还跟我聊了几句，过了一会 ZJK 神仙也发现我在打几何冲刺，居然借我的手机自己打了几把，而且还是最难的那几关，而且手法十分熟练，一看就知道是被几何冲刺虐了千百遍心态，熟练的让人心疼，我也终于把第二关给打通了，上一关还是在初赛回来的车上打过的看来我必须要在考完试后才能随机打通一关，这个手机我是不扔了，哪天换了之后把它供起来，每逢考试就拜一拜，毕竟不是谁都能拥有国集爷玩过的手机。

晚上跟着父母去吃了烧烤，回来后洗了个澡，就睡了。

总结

这次考试总体来说不是很理想吧，在 lg 上测了 pj 的 T1，T2，T4 果然还是写挂了，lg 上只有 40pts，还好前两题都 AC 了，tg 的 T2 没看到居然还有 $k=64,n=0$ 的恶心数据，不知道最终能拿几分，T1 很多人问候出题人外公的女儿，还有人想见见他的全家我都差点控制不住要发帖子了。

如果 pj T3 没写挂的话，1= 应该是有了，tg 就只能拼 rp 了，希望 SC 不要又搞初赛那样的迷惑操作。

补充：刚刚有位大佬分享了 pj 组的代码，测了一下，除了 T4 写挂之外，其他三个题都 AC 了，应该 1= 是稳了。

再补充：目前 pj 和 tg 代码都拿到了，pj 估分 100+100+100+40=340pts，应该没问题，但 tg 估分只有 0+65+40+20=125pts，恐怕在 SC 拿不到 1= 了，就算能拿也去不了 NOIP，只能明年再看了。。。

一些想法

正如上面所说的那样，这次考试算是爆炸了，伴随着考试爆炸，停课集训的三周也结束了，今天晚上就得回归到班上，开始整 whk 了，虽然不用考期中，但落下的功课总归还是得补起来，尤其是没有背的英语课文，期末考试还要考的啊，得背熟才行，另外，数学的三角函数也要把式子背一下，化学不是特别需要担心，因为没有什么太难的内容，而且停课期间我也下去听了几堂课，物理的欧姆定律主要就是得多做些题，基础知识我还是大部分都了解的。

停课这三周，虽然也不是没有收获，但个人觉得进步还是太少了，最后的几次考试跟最开始的几次分数和 rank 几乎一样，甚至还要更低，也没有学什么新的算法，题刷得也不够多，完全没有在这宝贵的三周里干什么特别有意义的事情，每天 TF 的时间还是多了一些，尤其是越到后来越明显，这不是很应该，虽然说其他的大佬也要颓，但人家好歹是大佬，比我可强多了，这是不能比的。

初三一过，马上就升高中了，到时候时间会更紧迫，如果不能抓住初中这最后一年，到 AFO 的时候可能还是只有一个 tg1=，甚至连 1= 都没有。说真的，我觉得竞赛生应该可以说是一个比较矛盾的群体，既要搞好 whk，也要抽时间出来学竞赛，两边都不能放弃，而且可能明知道自己没有办法获得一个比较高的荣誉或成就，但还是愿意为此付出，虽然不被理解，但还是努力前行，如果没有兴趣作为支撑的话，我个人认为是很难坚持下去的，但是，我还是不后悔自己加入了 OIer 的队伍，并且感到很光荣。

结束啦，接下来就是看有没有机会去 NOIP 了，如果能去的话，可能还要再停课，不过那应该还比较远吧。

又及：最后这段可能思路有点乱，凑合着看看吧，博主语文不太好又喜欢瞎想，所以经常写出这种离题万里的文字。。。