CSP-S2-2020 游记

· · 个人记录

CSP-S2-2020 游记

Day -？

给高一的小朋友们抽空考了 yLOI2020 day2，并且翘了一下午的课讲了题。day2 的 D 题是一道涉及 STL 基础知识的提答题，涉及 priority_queue，set，multiset，map，bitset，另有 5 分常识填空题，包括「常见的开启编译警告指令」，「bool 数组占空间大小的计算方法」，「windows 下开栈的编译开关」。这一提答题提前考了并且在周六晚上讲完了。

（flag：bitset，priority_queue，set）

Day -4

拿到山东省选手须知，发现与往年有一些不一样的地方，于是在机房分析了一下这些变化。包括文件要求和试机时间该边等等，重申了各种注意事项。在晚上翘了晚自习在机房和 sy 一起整理了一份注意事项清单。在写清单的时候，我给 sy 说，「今年大概不会出二分答案题，因为这并不是特别的签到，而对于水平一定的选手又没有足够的区分度，往年比较合适放在 day2A 的位置，但是今年题本来就少，大概不会浪费位置放个二分答案上来」。

（flag：二分答案）

Day -2

翘了晚自习来机房摸鱼。正好碰上最后一场模拟赛，一共两道题，秒了 A 题的式子，要除以三，答案对 10^6 + 7 取模，我的答案要除以 3。万万没想到这个模数不是质数，于是爆零了。B 题是个弱智的缩点板子题，写代码的时候莫名其妙存了一份反向边，判可达性的时候用反向边判断的，但其实应该用正向边判断（事实上我有两个做法，做法 a 要反向边，b 要正向边，我最终选择了写做法 b，但是把边的方向搞混了），喜提 20。

评测的时候我把爆零选手的逐一拉出来处刑，发现了各种诡异的问题，比如有人在我的反复强调下仍然开出了 10^4 \times 10^4 个 int 的数组（256 MB 内存限制），还有人把 A 题和 B 题的代码直接交反了，即 count.cpp 内是题目 eng 的源代码，eng.cpp 内是题目 count 的代码……还有一车 CE 的，没写文件的，输出写成 .ans 的。赛前两天还会出这种问题简直不可原谅。重新强调了空间、文件等问题，走人了。

Day -1

翘了晚自习来机房摸鱼学习。真正写起代码来才发现退役以后水平正在断崖式下跌，开始焦虑今年要丢人现眼了，突然明白了为什么 18 年邱学长来打了一场校选以后就放弃了 NOIp2018，也明白了 19 年的 zzh 是咋回事。平时做做嘴巴选手真的感觉不到水平的明显下降，上手才发现要完蛋。和 zwy，苏子鹤，zzh 交流了一下，然后写了写 LCA 和 dijstra 的板子就爬回家了。

赛前

做了一上午的高铁到了日照，中午在餐厅等到了 J 组的题面，把题面传上了 luogu，发现题面竟然是拿 word 写的，离谱。怎么和 yLOI 一样简陋。加题的时候看起来 C 比较毒瘤的样子，也没有仔细想就跑了，顺便面基了 actinoi。中午啥也吃不下去，随便喝了两口汤，想着下午一定会饿，于是就想着买点吃带进去。正好有家长送了一块巧克力，于是随手放进了笔记本包里。

进场以后才发现完蛋了，巧克力没有拿出来。要饿一下午了。

从餐厅出来的时候买了两瓶冰红茶，一瓶给了 cuc，一瓶自己带着。进场时都给了 cuc 保管，我们从二楼机房门口分开时我并没有意识到喝的也不在自己手里，核验身份进场时看到 sy 到了男洗手间门口接水才想起来没有吃的和水。赶尽跑下去找 cuc，幸好他因为找错考场被没有走，不然大概就要又渴又饿一下午了。

赛时

入场试机，写了快读和一个倍增 LCA。发密码时，监考给出的密码是 ke2YI0gong2YU0，考场里所有人都解压失败了，监考迷惑了一万年，最后发现原来括号也是密码的一部分 (ke2YI0gong2YU0)。这时已经 2 点 28 了，开始看题。这个题面看起来还是比 J 组好看的。

开场觉得第一题比较友好，觉得这种闰年题已经被出烂了，应该比较好写；然后看了看 B 题，发现没看懂，没看懂的主要原因是数据规模里没有给出 p, q 等有关范围，导致我没法佐证对题意的理解。这从侧面证明了 ouuan 整理的题面规范的重要性（；C 长了一张数据结构的脸，以为在明示线段树，维护个贡献啥的；最后 D 题是个有点鬼的博弈。于是决定开 A 题，此时的我完全没有意识到问题的严重性。

A

首先考虑 day by day 的模拟，发现只有很低的分数，然后考虑 year by year 的模拟，发现仍然只有很低的分数。再考虑四年一组暴力，发现还是只有很低的分数。于是开始考虑正儿八经讨论着算。首先显然把公元前的年份绝对值都 -1，那么闰年就和公元后的统一起来了，然后分 1582 年以前，1582 年，1582 年以后三种情况讨论。半小时过去了，讨论了一半的情况，发现情况不对，非常恶心。重新思考发现可以先二分年份，把问题转化成某个公元纪念距参考日多少天会减少一部分讨论，于是整理了一下之前的部分，继续讨论。到代码写完已经过了多于 1h 了，测了下样例发现小样例都过不去，输出中间变量时使用了 printf("%d %lld\n", ans, clc(ans))；此时输出第二项是一个巨大的明显不正确的数字，但是当单独输出 printf("%lld\n", clc(ans)) 时答案又看起来很正确。自闭了很久，最后发现是 ans 是 long long 类型，printf 的第一个占位符应该用 %lld 而不是 %d，怀疑是压栈之类的时候有一些奇怪的覆盖。解决问题以后调出了一万个小 bug，修改后过了小样例，但是死活过不去大样例。有一部分的输出的日总是比答案大 1，手算无果当场自闭，认为 A 题都这样子那今年就要这样结束了。强作镇定重新调试大样例，开始胡乱调参数，寻找挂的年份的规律，在计算天数的函数里加了一句 if ((x % 4) == 2) ++ret;，发现多过了一些询问。继续仔细观察和各种尝试后，发现如果写 if (((x % 4) == 2) || ((x % 4) == 3)) ++ret; 就可以过所有样例。修改完后重新测样例，发现根本不更新输出文件，非常的慌，过了十分钟，发现是控制台的 fc 指令没有执行完，是被我以选中的方式强行暂停的，fc 一直占着输出文件不让更新。此时已经过去了两个多小时，决定不再挣扎，过了大样例以后就扔到一边，能拿到多少就听天由命叭。

B

扔掉 A 以后，在开 B 和开 C 之间犹豫了一会，因为 ds 一直是我相对擅长的部分，但是考虑到退役后码力的下降，还是选择了开 B。事实证明这是个正确的决定。先去洗手间洗了把脸，回来仔细阅读题面并理解题目意思以后的第一反应：「嗯？我读错题了？」仔细阅读题面并分析样例解释后，我从内心深处开始亲切的问候组（注：这里不是错字）题人家人的身体健康。

因为数据规模严重的阻碍了快速理解题目，一开始把 c 也当成了 64，认为这就是个不需要脑子的题目。仔细看数据范围后发现 c \leq 10^8，好叭把相同的 p 值对应的 q 扔到 std::vector 里或者挂成链表从而达到总枚举复杂度 O(m) 也勉强算得上是一点技巧？然后犹豫了一下要不要开 10^8 大小的 bool 数组。虽然理论上机算是没啥问题的，可毕竟省选时 day2A 我理论空间计算也没爆 512MB 然而评测爆零了，从而导致了我 MLE 恐惧症。犹豫了一下用了 std::bitset。写完以后，又万分小心的把可执行文件扔到 MinGW 提供的 size.exe 同目录下，装模做样地命令行运行了一下 size zoo.exe，虽然我并不十分确定控制台上的显示是不是我认为的意思。

在写 B 的时候（也可能是写 A 的后半程或者是 C 的前半程，记不清了），考场里有人开始砸键盘。因为比较烦躁，想让他安静点，所以我也跟着他一起开始砸键盘（（，不过键盘好像并不能敲得很响，大约敲了两三分钟，感觉会引起反感，于是就收手了，另一个人一直砸到了结束（。

做完这一切时，距离我开 B 题，只过了十来分钟。

C

过掉 B 题并没有对拍，因为时间不足，而我对一等没什么刚需，加上手头的分数实在是太丢人了，于是自然就选择了尽可能争取更多的分数而不是求稳。

仔细分析 C 题题意，发现修改是单点加法和全局乘法。那么这显然不是什么数据结构题。最暴力的做法显然是 O(qmn) 的模拟，发现只能过 3, 4 两个点的 10 分。把加法和乘法放在一起自然而然想到了「【模板】线段树 2」中维护结点标记的方法，即对于一次 +v_i 操作，它对该位置的贡献是 v_i \times \prod_{j > i, T = 2} V_j，其中 \prod_{j > i, T = 2} V_j 表示该操作后所有乘法操作权值之积。这样只要倒着执行指令，就可以维护每一时刻乘法的后缀积，加法的贡献就可以直接算了，这是一个复杂度为 O(q \times (1 + \sum C_i))。期望得分 30 分。

写完以后不能过第二个样例，手算一下发现调用其他函数时的调用顺序也要和指令相反，修改后跑了下大样例，发现秒出，看了下大样例是 10^5 级别的，感觉很离谱。第二天和同学交流时听说暴力线段树这种比朴素暴力还多一个 \log 的做法都能秒出大样例，觉得更加离谱。

事实上在得到这个做法以后我已经大概明白了怎么从这个做法推广到树上，但是因为时间紧迫，加上对码力并没有信心，于是并没有仔细想，选择了开 D 题。

D

分析题意后发现结论比较显然，先按顺序模拟决斗过程，如果某次决斗过程中最菜的蛇之前吃过别的蛇，那么为了它的生存，它就会放弃那次吃蛇的机会转而结束决斗。这个过程显然用 std::set 直接模拟即可做到 O(T n \log n) 的复杂度，好像分数很高，有点离谱。最后一点分猜测大概是优化成线性数据结构，因为有自知之明，所以没有去想。

代码很好写，但是开题时已经只剩不到二十分钟了。写完以后过了前两个小样例，但是 wa 了第三个样例。尝试调试无果，到比赛结束也没有调出来。

想想 OI 生涯，NOIp2018 时 day2C 的弱智 44 分没有看到；十二省联考 2019 时 day2C 干脆就没看；CSP2019 时 day2C 的链部分分明明很弱智可是赛时没能调出来；省队联测 2020 时 day2C 的矩阵树定理明明就是板子可是也没调出来，这次 CSP2020 时的 D 又没能调出来。好像和比赛的最后一题有仇一样，总要以各种各样原因挂分。想想大概是心态的原因，就像现在文化课考数学最后五分钟必算错数一样。

赛后

最后估分为 [0, 100] + [100, 100] + [30, 50] + [0, 20] = [130, 270]，分数大头取决于 A 题到底挂了多少，以及亲爱的 D 题出题人会给我多少分。

和高一学弟学妹交流了下，发现普遍不是很理想，于是晚上在群里进行了一定的心里开导，希望能起到一定的作用。

出场后，和 cuc 约好了在实训楼门口左侧等他，然鹅他来的特别晚，并且在等他的过程中我惊讶地发现身份证找不到了，于是等到他以后又拉着他回去找身份证，发现被压在了键盘底下。找身份证的时候监考给我看了另一个身份证问是不是我的，我发现时 shq 的，这时才发现原来 shq 和我在一个考场（

晚上去蹭了 cuc 和 drz 以及他们家长的晚饭，有一盘螃蟹，一盘爬虾，一盘扇贝，一盘大虾、一盘炸鱼，还有一盘菜。作为一个土生土长的内地人还是第一次吃到这么丰盛的海鲜宴（

回去的时候 jzk 在群里说 A 题 day by day 模拟就有 80 分，突然意识到了自己弱智到忘记了可以离线询问把复杂度变成 O(q + \max r_i)。这样的话如果 year by year 模拟是不是就有 90 分了啊 /fad。感觉很夸张，我的两个多小时写了个寂寞。

送我回宾馆的路上 cuc 给我他的耳机听歌，他歌单里的歌我一个都没听过，除了一首「see you again」。于是我又莫名的循环起了这首歌，甚至包括我在写下这篇游记时也在听着这首歌。也许在一个月后的 noip 结束时，我循环这首歌会更恰当一点？

晚上回宾馆以后打了一通宵王者，先和 lyp 打，再和 lml 打，然后拉了 anguei 来打（我才知道原来 anguei 会玩王者）。一直到了凌晨五点，实在是困得撑不住了，于是睡了一个小时，六点起床准备赶火车。

火车上 jzk 说 B 题爆 ull，我以为我凉了，仔细分析了一波发现 ull 的运算是在模意义下的，所以啥事没有，是 jzk 谎报军情试图恐吓我（。

在回去的火车上 7 个王者玩家打起了内战，因为人数是奇数所以只能 3 打 4。显然 3 人一方都输了，并且前两把输的特别惨（。

结语

首先请允许我谨代表我自身向本场比赛的组题人和 A 题出题人的身体健康和家庭情况致以诚挚的问候。

今年的题目整体感觉上得分偏易？但是因为组题的原因，我不认为今年的分数线会很高。

对自身的发挥并不满意，尤其是如果达到了估分界面 130，那么大概就是真的身败名裂了。水平下降的很严重，这套题拿给去年没有退役的我做的话大概能提升几十分，至少第一题不会写这么久然后可以留出时间给 C 和 D。如果将 A 题放到 C 题的位置，那么也许我的得分也会提升几十分。不过水平下降既是无法避免的事实，便也不那样的沮丧。

回校又是艰难的 whk 生活，语文英语历史化学倒是已经勉强可以接受了，但是数学物理仍然因为一年的停课差着一大截，希望能尽快赶上来叭。希望今年 csp 少挂分，希望大家能拿到预期的分数。

by 一扶苏一

2020.11.8

upd1

A 题挂成了 40 分，B 题 1ll << i 写成 1 << i 了，估计要挂 60，加起来挂了 100。

luogu 数据 40 + 75 + 40 + 25 = 180，山东省 rk 43，感觉有点离谱。

牛客数据 40 + 95 + 80 + 20 = 235，山东省 rk 17，感觉更加离谱。这个 B C 两题的脚造数据有点过分，B 题左移没 ll 就卡了 5 分，C 题 O(Q \times \sum C) 的做法拿了 80。

目前看起来不是特别丢人。

—— 11.11