NOIP2022 游记

· · 个人记录

风水轮流转。

凭借着纯纯的狗运，我见过 T4 的原题。但是我的脑子还是有硬伤，竟然直接莽了一个三模数 + CRT 的做法，然后没时间卡常了。于是在时限边缘徘徊。

自测结果：100+100+100+[76,100]=[376,400]。看看 T4 能不能跑过去。

不过 FJ rk1 应该是没问题了。

考试过程什么的先咕着。 写完了 Day1 及之后的部分。

UPD：100+100+100+96=396。

\Large{\text{Day }???\ (???)}

咕咕咕。

\Large{\text{Day }1\ (11.26)}

昨晚 9:30 睡的，早上 5:00 就醒了，然后躺到了 7:00。这一觉是真的痛快。

进了报告厅，我身旁的同学们开始讨论可能会考什么，我表示非常反感。我拒绝一切可能影响心态的东西进入我的大脑。我心中的湖应该平静如镜，容不得半点波澜。 考场里的其他人是谁，他们为什么会存在，我不得而知。全世界应该只有我一个人，他面对着四道题目奋战，而他只有一个目标，那就是不挂分。我不断地在心中如此默念着，尝试将心态调整至最佳状态。 进考场，发现我坐在最后一排最右侧的那一桌（可能是倒数第二排？），简直是阴间。考前几分钟，下发文件发下来了，竟然只有 `pdf` 题面是加密的。还有，这是什么奇怪的英文名称。 $8:30$，比赛正式开始了。密码是 `solo@2022`。前三题 $1$ 秒，第四题 $2$ 秒，所有题都是 $\text{512 MB}$。 先看完了所有题的题面，然后开始想 T1。从大到小枚举 $y_0$，再从小到大枚举 $x_2$，前缀和优化即可。直接开写，过了所有样例后，又从大到小把所有样例拼起来，也能过。那多测清空应该没什么问题了。又对着代码盯了一会儿，感觉这不可能有问题。这时大约是 $9:00$。 开始想 T2。NOIP 竟然会在 T2 的位置放一道构造题。又看了一遍数据范围，才发现 $k=2n-2$ 或 $2n-1$。积极地在草稿纸上手玩，很快就会了 $k=2n-2$ 的情况，但是这为什么才 $15$ 分/fn。 $n\le 3$ 竟然有这么多分，但我觉得这应该和正解差不多。主要的问题在于如何处理 $n-1$ 个栈都填了两个元素，剩下一个栈为空，又来了第 $2n-1$ 个元素的情况。但是我手玩了半天，都没有找到方法。我告诉自己，该遵循自己的考试策略，去想想 T3 了。 这是什么震撼 T3 啊，这不是直接建出边双树然后 DP 就行了吗？于是又回去想 T2。发现可以讨论下一个非栈顶元素出现的位置。如果它是第 $2n-1$ 个元素，直接消去即可；否则讨论它对应的栈顶元素在这一期间内的出现次数的奇偶性，分别有一种维护方法。 然后就是一个大模拟了/px，感觉要用 `set` 维护大小为 $0/1$ 的栈的编号集合。不想写啊/px/px，就先去上了个厕所，然后硬着头皮开始写。 写了好久。一测大样例，没有 RE。然后输出了一下每个栈最终是否为空，发现我写挂了。于是从头到尾认真检查了一遍代码，发现似乎只有分奇偶性讨论的第二种情况写错了。改了一下，每个栈最终都为空了，就先把这题扔在一旁。这时大约是 $10:35$。 然后开始写 T3。写完缩点部分后，我想去上个厕所。但是我坐在最后一排，每当我起身时，总有一个人同时起身，直接往厕所走了，完全没有注意到已经排了许久的队的我。我就在一直憋着的状态下写完了 DP 部分。 DP 状态就直接设 $f_u$（没有第二维），在统计答案时才考虑减去不合法方案数（$u$ 不选，且只有一个子树选了）。不知道为什么很多人的 DP 都好复杂。 T3 过了样例后，我开始想 T4。天哪，这不是前几天的模拟赛题吗？NOIP 竟然轮到我来 AK 了？？？线段树维护区间乘、区间历史和即可，虽然需要逆元，但这是我唯一能理解的做法。这时我积极抢先起身，终于得以去了厕所。 去完厕所回来，我发现模数是 $2^{64}$，这也太恶心了吧？这时我的脑子不经思考就做出决定：分别维护模三个大质数时的答案，然后 CRT 求出精确值。需要用到 `__int128`。 这时大约是 $11:10$。由于我唯一的目标就是不挂分，我决定无论如何都要留出半个小时检查前三题：我必须在 $12:30$ 前写完 T4。 但是这个历史标记实在是太抽象了/px/px/px，我从来没有写过维护历史信息的题目。我胡了若干个打标记的方法，最后终于过了样例二，这期间还有一次单调栈写挂。但我终究还是不够熟练，CRT 一直写不对。这时候已经 $12:30$ 了，我还是决定先调完 T4。我的考试策略开始崩塌了。 发现直接乘会爆 `__int128`，于是写上龟速乘，但还是过不了样例三。最后发现我合并时没有乘以第一个同余式的模数。这下终于过了所有样例，这时大约是 $12:45$。 随了一组极限数据，发现要跑 $4$ 秒，但是 $10^5$ 的数据可以跑过去。发现瓶颈在于 CRT，于是减少了取模次数，最后卡到了 $2.5$ 秒。虽然还有很大的优化空间，但是已经没有时间留给我卡常了，必须去检查前三题以及 `freopen` 之类的东西了/ll/ll/ll。 T1 我瞪过了，应该没有问题；T3 就是 Tarjan 板子 + 简单 DP，应该出不了问题。T2 我之前认真检查过一遍了，那就验证一下大样例的输出吧。然后发现程序输出了一大堆 `ERR`，大危/jk。 但结果是，我用于验证的程序忘记判 “插入的元素与栈顶相同” 的情况了，加上就没有问题了。然后检查 `freopen` 和文件夹。不一会儿，比赛就结束了。 感觉我又打得太激进了，要是挂分了怎么办？？？ 出了考场，我马上跟 18Michael 说了我 T4 的奇怪做法。18Michael 没有告诉我他打得怎么样。然后碰到了 Linshey，他说他大概有 $310\sim 370$ 分。Linshey T4 写了个分块做法，我觉得非常神秘。但他 T2 写了个奇怪东西，好像是 $n\le 3$ 的部分写了个 DP 套 DP/jk，$n$ 大的部分没写。 我和 Linshey 的 T4 都跑了两秒多。他告诉我，Windows 下读入数据需要 $0.4$ 秒左右（真的吗？），再加上 CCF 的机子很快，所以我的程序应该可以跑过去。 这时候我[去年 NOIP](https://www.luogu.com.cn/blog/chen-03/noip2021-you-ji) 的 PTSD 开始发作了。先是担心我的程序有没有收上去。我们考场的第一张回收结果贴出来了，我仔细找了一遍，没有找到我，危。随后第二张回收结果也出来了，在上面找到我的准考证号后，我才松了一口气。 然后想到 T4 可以不用 CRT，应该维护形如 $a\times 2^b$ 的信息就可以了。我觉得这又好写又跑得快，当时为啥直接莽了 CRT？如果我写了这个做法，留出了更多时间检查前三题，说不定还真能查出错误呢？如果我写了这个做法，是不是就能稳稳地过掉 T4，而不用寄希望于评测机速度呢？ 现在好了，我脑子的硬伤又给了我一次重击。同学们问我考得怎么样，我都拒绝回答，我写了多少分并不意味着我能拿多少分。我本来应该是最开心的人，现在却因为担心挂分显得无比痛苦，在走廊里不断地徘徊。 回到家时已经两点了。根本吃不下饭，吞咽全靠硬塞。吃完饭，我询问什么时候会发代码，rsy 告诉我大概要到一周后/yun。后来学弟通过物理方法（直接拷走）得到了附中考场的代码，我就直接要走了自己的。但一个小时后，官方就发代码了。 看见 U 群里有人说 T3 大样例缩完点后是一条链，我的心一下子就揪起来了，这不就是恶心人吗？？？然后冷静地回忆了一下我的 DP，感觉应该没问题。 三点多去剪了个头发，准备平复一下心情，但是只花了半个小时，根本没有平复过来/fn。发现 InfOJ 上有 T3 民间数据了，马上交了一下，过掉了。随后又有了 T4 民间数据，我除了六组满数据外都能稳过，得到了 $76$ 分。在本机（Windows）上试了一下满数据，发现去掉输出只跑了 $1.7$ 秒，那不是大概率就过了？ 随后在 “日爆” 的洛谷上交了 T1。在十几分钟的等待后，发现没问题。后来 InfOJ 上也有了 T1，也过掉了。 现在只剩 T2 了。先是交到 CF Gym 上测了一下样例，没问题。考场上发现大样例没有涵盖到我代码中的所有情况，就鼓起勇气再看了看没有涵盖到的那两种情况，感觉也没问题。 时间来到了晚上。18Michael 造了 T2 的 $100$ 组数据扔到了校内 OJ 上，然后交了我的代码。我帮他修了一下 SPJ，然后发现我的代码全 WA/jk。但是 SPJ 信息显示 `Stack 302 isn't empty`，这绝对是 SPJ 挂了而不是我挂了（确信）。 但是我硬是找不出来这 SPJ 哪里写挂了。这时 18Michael 在群里发了句 “T2 可以评测了”，不会真是我挂了吧？？？然后发现我的代码正在被重测，跑了几十个点都是 AC 的/ohhh，然后就真的 AC 了。18Michael 告诉我，原 SPJ 里的一个 `bool` 类型的函数没有返回值。 我开始怀疑这个数据的强度。又交了一发，发现我代码中的六种情况都被涵盖到了，那就没问题了！然后发现 18Michael 把他的数据投到了洛谷上，这就是 18Michael！ 那我大概就没挂分了吧，$100+100+100+[76,100]=[376,400]$，不出意外的话应该是 FJ rk1。考试结束后我真就摆了一整天，什么事情也没做。 发现 18Michael 有 $352$ 分，稳得不行。Linshey 的 T2 出了点事情，RE 了，只有 $20$ 分。我看了看，发现他一个大写 `I` 打成小写 `i` 了。我帮他改了一下，发现还是只有 $35$ 分。他在 InfOJ 上另外三题是 $100+100+60$，那不是一共只有 $280$ 分吗，感觉他有点寄啊/ll/ll/ll。 $\Large{\text{Day }2\ (11.27)}

rsy 发了 FJ 的民间排行榜（就是 InfOJ 上的那份），是用他的机子测的。

？？？为什么 300+ 才 5 个人？为什么没几个人过 T2？这个榜好抽象啊。

我的 T4 跑了 2.2 秒，那在 CCF 评测机上估计就过了。而 Linshey 的 T4 直接过了，于是总分变成了 100+20+100+100=320。那就提前祝贺 SDFZ 包揽 FJ 前三吧。

Nesraychan 在这个榜上有 320 分，但是他今年初三，不和我竞争/cf。另外一位 300+ 是 FZYZ 的 lzq，但是我不认识他/kk。

但是我的其他同学们考得有点惨淡。zc_li 和 defKaeru 都挂惨了，可能连奖都拿不到了，我的 lzc 桀桀和 zyx 桀桀！！！/ll/ll/ll/ll/ll 我校女队 Rainy7 也寄了，碰上了不该碰上的 CLYZ 教练。

至于我的高一学弟们，总体上表现得还行，但是 gwx 从 335 分挂到了 188 分，简直是离谱，这就是 yylOI 吗？

\Large{\text{Day }10\ (12.5)}

初评成绩是 100+100+100+96=396，我要申诉！！！！！/fn/fn/fn

\Large{\text{Day }13\ (12.8)}

T4 TLE 的那个点比其他点慢了好多。最后还是没去申诉。

祭之。