NOIP 2023 游记

Day 0

打了一场模拟赛，分数中规中矩。原定计划是在 NOIP 前一天把 11 月做的题目写一下题解，做一个整理，但是下午还是摆了。晚上回家简单看了几道之前做过的题目，然后看了两集番，11 点钟睡觉。

Day 1

在家里睡的真是好，早上完全不想起，然后一直睡到七点多，八点钟才到达 hust 门口。上了八楼之后又悠闲的上了个厕所才进入考场，此时已经是 8:20，等我坐到位置上压缩包密码都发了。总之时间卡的很极限，符合我的作风。

808 机房这个电脑没有之前 csp 那个好用，不能在 windows 下用 vscode + wsl 了，只能打开虚拟机用 noi linux，不过现在共享文件夹都已经提前建好了，这倒是比以前人性化不少。打了一个 template，然后就开考了。

先看 t1，感觉是白给，肯定是让当前字符串尽量小，其余字符串尽量大，然后维护一下前缀后缀 min。排序使用计数排序，字典序比较直接用 std::string 的运算符，这样总复杂度是 $O(n(m+|\Sigma|))$ 的，非常好写。当然我还是写了大概 30 min 才搞完这道题。如果稍微观察一下还可以发现只需要比较最大或最小的字符即可。

t2 感觉还是不困难，首先模拟一下赋值过程可以将最终的 $x_i$ 表示为 $\texttt{T/F/U}$ 或 $(\lnot)x_j$ 的形式，这样部分变量的值已经被确定下来，此外还形成了若干约束，形如 $x_i$ 和 $x_j$ 的值必须相等或不等，这可以用 2-sat 做，但注意到连边都是双向的，所以可以直接并查集。也可以建图然后黑白染色。最后想了想还是并查集最好写，所以就用了并查集的写法，但是这样多一个 $\log n$ 或 $\alpha(n)$，不过也无伤大雅。此时时间是一个小时。

t3 我先看到 $\sum k\le 5\times 10^5$ 还以为希望让我做一个类似动态 dp 的东西，后来看到 $q$ 很小才意识到可能这种输入方式只是为了减小输入量而已，那么目标就是思考一个单次线性的做法。我的思路是不做转化直接从原始题意入手。模拟这个匹配的过程，将 $x$ 序列从前往后扫，每个元素能匹配到的 $y$ 中的元素应该类似一个区间，前往 $A$ 序列下一个元素的时候这个匹配区间的左端点会向右移，右端点可能左移也可能右移，过程中一个端点越过了另一个就意味着无解。这样就有了一个 $O(n^2)$ 做法，打了一下发现样例能过，那么就接着往下想，目标是只移动一个端点，并且总是向同一个方向移。想了一段时间发现左端点是不需要的，无解的时候 $x_i$ 一定比 $y$ 中右端点左边的所有数都大。

此时又过去了一个小时。简单看了一眼 t4，当时并没有太多想法，但是觉得至少部分分可以打很多，暂时定下的计划是至少得给 t4 留下两个小时左右的时间，这样才比较稳妥。不过总是觉得可能距离 t3 正解并不远，所以没有放弃 t3。这时候内心很紧张，害怕自己做 t3 上头导致 t4 出现重大失误。

其实类似去掉左端点的思路可以发现右端点的移动也并没有维护什么有效信息，在 $x$ 序列全局最大值的左侧右端点左移是没有意义的，再经过一系列转化后做法就变成了只用向右推右端点，并且从左往右和从右往左分别做一遍。代码极其简单，写完时还剩下 1 hr 40 min，并没有偏离计划太多。

再仔细想想 t4 发现直接线段树优化 dp 就行了，直接开打。打完后发现过不了样例 2，这下出大问题了，这个题要是出问题了不太好调。本来准备写个暴力对拍一下，于是先删掉了离散化，结果突然发现这个时候线段树的答案是对的，看了一眼离散化原来是没把区间右端点插进去，改完后就对了。

考试还剩半个多小时，这时候才恍惚的意识到自己已经 AK 了 NOIP，这是我 OI 生涯中的最好成绩，对我来说也是极大的鼓舞。NOIP 成绩为省选奠定了相当好的基础，高一可以心无旁骛的备战接下来的比赛。

最后的时间把所有题目重新编译，并且重新测了一遍所有大样例，非常激动。

出来后问了一圈发现大家的情况不尽理想，lyz wlj lty 等人的分数远低于其实际水平。再次警示在考试中什么意外情况都可能发生，不能够掉以轻心。

下午和以前 hsy 的学长 cyy 玩，逛了一圈 hust，然后去吃饭看电影，还晃到光谷去看了 lol 高校争霸赛的决赛（hust vs. whu，只看了最后一小段），hust 顺利捧杯 /bx。

各个地方的估分都出来了，简单测了一下，云斗、小图灵、洛谷都是 400，应该没啥问题了，感动。

Day 2

玩了一整天。

T1 薄纱 WBG 了。

Ending

务必抓住今年的机会，不可能年年都有这般状态。

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。