2022 CSP-J 游记

· · 个人记录

Round 1 Day \bold{-\infty}

先来占个坑到时候连投三篇直接拿小本本。

广告：洛谷网校的课好得不得了，尤其是 rxz 老师的，算法一听就学会。

注：本游记数天数从 0 开始。

Round 1 Day \bold{-49}

今天是 rxz 名师优训营的最后一堂课。就要结束了，好伤心。

AC 数快到 300 了，加油！

Round 1 Day \bold{-1}

临时抱佛脚，看了一晚上初赛知识，看得最多的是组合数学。

Round 1 Day \bold 0

坐车到认证场地。

门口的警卫很认真地检查着核酸证明和健康码。

找到了教室，坐下来歇了会。监考老师凶巴巴的，紧张。

考场的小伙子们都很帅气，姑娘们都很漂亮。可惜不敢要 QQ，回想起来，真是伤心。

发卷子了。

先看选择题：第 1 题，面向过程和面向对象，简单！

…………

第 9 题，连通？那不就是树吗？直接 \sout{N-1}。

看阅读程序。

第一题，位运算，简单。乱算一气，完事。

第二题，看了看，是递归和迭代对同一个动态规划的实现。还用了 Modern C++ 的模板求类型最大值，吓人。

先把无脑判断题做了。猜判断题有技巧，欢迎跟我讨论。

选择题，复杂度？简单。

输入算数？不会，随便蒙一个看起来像的。

第三题，solve1 一眼二分；solve2 试了一下，答案越来越逼近 \sqrt n，看来是牛顿迭代法，我两年前学语法时还学过。

判断题挂了：鬼知道 cout 输出浮点数省略末尾的 0……

完形填空。

枚举因数？还用了 std::vector？不符合 CCF 的风格呵。

还用 vector::reserve？有点激进。不过代码还是很好填的。

floodfill？BFS 模板？无脑写。

做完题跟隔壁选手交流：“今年线肯定 80+。”“不拿 90 都对不起这套题。”

静候分数线。

Round 1 Day \bold 9

分数线出来啦！托 rxz 老师的福，我拿了 90\ \text{pts}！

机房好友 wyc 在 S 组拿了 52\ \text{pts}，然而分数线是 52.5。而且他在初三，这就是说他要退役了。他说，今后不再打 OI，要做一名 whk 选手，我不禁为此感到悲凄了。一个很有可能进省队、打 NOI 拿金牌的选手，就这样断送了他的 OI 之路。

从今往后，身处弱校的我便只有一人孤军奋战。这条本就不易的道路，对我来说，势必会更加艰难。对其他 OIer 又何尝不是呢？虽然这是不可能的，但祝愿每一位 OIer 都能取得理想的成绩。

Round 2 Day \bold{-8}

我做了一个长梦。

篇幅所限，若感兴趣，请看这篇文章。

人们常说“梦是反的”，希望这个梦能给我带来好运，也祝各位 CSP RP++。

Round 2 Day \bold 0

6:30，便起床了。

吃完早饭，乘车向认证地点驶去。

到了认证场地的大门，工作人员检查了核酸检测和行程卡，我便往里走去。

按着指引，我到了认证的楼里。爬了 \sout{6} 层楼，还得找到隐藏的电梯，累\~。

监考员死活不让带食物和水进机房。但凡看过一眼考场纪律也不会这样啊。

但是这难不倒机智的我。我去问另一个监考员，他同意了，然后全考场的人顺利把食物和水带进来了。

看了看桌面，发现 NOI Linux 是个虚拟机。 想退出，但是怕算作弊，没敢退。

认证开始！我顺利从内网下载到了压缩包，密码是 mountain2022。

打开题面 PDF，看到编译指令里有 -std=c++14。多此一举。

看 T1。

woc？这什么玩意？上来就高精？我不会又要像去年一样 80\operatorname{pts} 遗憾离场罢？……

冷静！我告诉自己。这可是入门组 T1。

认真分析，发现：考虑到 a\leqslant 10^9，如果 a^b>10^9，则把 1 乘 b 次 a 的过程中，一定有一次的结果大于 10^9 且不爆 int64。所以对于 a=1 时特判，其余情况迭代地乘 b 次 a 并每乘一次判断即可。

看 T2。

一看题目，蒙了：这是个数学题！

再次提醒自己：丝毫不能慌。数学题就是要推式子。

在草稿纸上狂写，最后得出个 n-ed=p+q-2。注意到题目上限定了 m=n-ed+2 的范围，就考虑在 p\leqslant m 且 p^2\leqslant n 的前提下枚举 p，生成 q。

然而这两个枚举在数据规模最大时都是 10^9 数量级的，只能得 60 分，先扔一边去。

看 T3。

咦？这题怎生跟 CSP-J 2019 那样像？连英文题目名都一样。

一眼表达式树。然而不会建，遂怒打 1.5\operatorname{k} 分类讨论 n\in\{1,3,5\} 的情况。期望得分 20 分。

看 T4。

我想 k=0 的时候应该有一个类似于传递闭包的贪心算法，可惜写挂了，只好去写 k=0 且 n\leqslant 10 的暴搜部分分。期望得分 10 分。

看了眼表，10:30 了。现在只拿到了 100+60+20+10=190 分。这个分数，想要拿一等，是不够的。看了一眼，只有 T2 最可做。于是去想 T2 的优化。

发现 p+q 和 pq 都已知，则把 q 用 p 表示，得 p(m-p)=n。整理，得 p^2-mp+n=0，其中 n,m 是常数。解这个一元二次方程即可。这时候我才明白，出题人告诉我们 m\leqslant 10^9 的良苦用心。

预估分数：100+100+20+10=230。对于一个只学了两年的蒟蒻来说，足够了。

为了避免喜报，特地又检查了一遍，发现了一个错误！

改好后，放心地去了个厕所。然而并不像某些大佬一样玩起了扫雷。 而且 NOI Linux 里也没有。

到点了，检查了文件，放心地离开了。

Round 2 Day \bold{0.5}

回到家，赶紧打开电脑，自测已经开始了。

到了 14:00 左右，我省的代码出来了。赶紧交到洛谷上测民间数据。

洛谷估分：100+100+15+35=250。（cz 出的 T4 数据不给力）

小图灵估分：100+100+15+10=225。

总体还行，T3 挂分了。

静候官方评测分数。

Round 2 Day \bold 9

查成绩。

CCF 为了搞什么“旗帜交接仪式”推迟了发成绩的时间。

中午 12 点，我一查，果然没有发成绩。

反转了：放学路上我用手机查了，能查到了，但是字太小看不到。

又反转了：回家打开电脑一看，发成绩的时间改成第二天早上 9 点了。

再次反转：晚上 QQ 群里有人发了个查分链接。

分数查到了。100+100+10+20=230（果然 T3 挂分）。

一等稳了。

Round 2 Day \bold{10}

CCF 今天发测试数据。

回到家，下载了测试数据，发现 T3 的两个变量写反了。

我向来是仔细的，未曾想竟折在这里。

倘若这错误出现在 T2，那是不可想象的。

希望我和其他所有选手下次一定细心检查，不要再犯这样的错误。

Round 2 Day \bold{10}

今天出分。

上 NOI 官网查了查，是一等无疑了。

本人现在初三，所以暂时从竞赛退役了。

感谢两年的陪伴。

OI，明年再会。

致谢

是深夜了。

我在电脑前，细数要致谢的每一个，并从心底里感谢他们。

首先感谢我的学校教练。他教会了我编程语言和一些基础算法。

感谢同机房的 wyc（就是上面那个）。他作为学得比我早的前辈为我提供了许多帮助和嘲讽。

感谢机房团宠（可能是？）zsy。她为全机房带来了许多欢笑以及我帮她调代码时的愤怒。

特别感谢阮行止老师。他对我的帮助可以说是最大的。他纠正我的代码风格，以最易懂的方式教给我实用的算法。如果没有他传授的“通用”二分，我根本无法在考场上写出二分求平方根的代码。

感谢洛谷网校的其他讲师。他们尽自己所能让我掌握了算法知识。

感谢 ShanCreeper 同学，他创立 DILL 集团，带领团员出了很多有意思的题目，让我们在紧张的训练之余感到些许欢乐。

感谢我的电脑。它从未因自己的原因而蓝屏过，出色地完成了它应有的任务，让我不会因为写到关键处时蓝屏而暴躁。

感谢我的家长为我提供了经济支持。

感谢曾帮助过我的所有人。

祝看到这里的各位天天开心！

完稿于 2022 年 11 月 18 日