NOIP2023 最后一战

省流：没调出 T4。

书接 NOIP2022。
去年因为 T1 多测没清空 + T2 没输出步数挂了 \(100+\) 分，然后喜提省二。
所以接下来高一下学期都在 whk，完全没碰过键盘，所以这个学期刚开始状态还是挺生疏的。

CSP2023

因为没写游记所以提一嘴。
当时可能脑子有点抽，一上来就把 T1 题面看错了，接下来整场都没有看对，导致心态爆炸，后面 3 题没怎么仔细想。
喜提 2=。

赛前准备

10.29 开始停课。
大概是因为最近皮肤病比较严重，10 月到现在几乎没怎么睡好过，导致这两个月精神状态堪忧。
所以刚开始停课的时候完全没有 OI 状态。
接下来一段时间状态略有好转，不过经常挂分。
从 rating 大概就可以看出来。

（最后一场掉了是因为 T1 把输出 \(2^n\) 搞成了 \(2n\)，rk5 \(\to\) rk15）。
倒数第二天把最近做的题全部过了一遍，总结了一下思路，然后最后一天写了点板子（虽然最后还是什么都没有用上）。

Day1

上午 6:50 起床从家里出发，在车上吃了早餐。
大概 7:40 到了机房，但是机房没网，所以就休息了一下，顺便想点题启动大脑。
从人体工学椅起来走到考场只要 10s，不用和外校的人一起在考场门口等，这就是主场实力！！1
大概 8:20 左右进了考场。
但是不给带吃的和保温杯，这么冷的天你让我喝冷水 /qd

经典提前 3min 开始，提前 3min 结束。
8:27 公布了压缩包密码，但是没有公布 pdf 密码。
因为好像只有一块白板，而考场机位分成了两边，我们这边甚至监考口头说密码，逆天。
听了 3 遍终于听懂了，原来他念 t 我听成了 p /hsh
然后 pdf 仍然没有密码，旁边有老哥急急急，但是我要打 my_std，我不急急急。
接下来就开题。为了避免去年卡 T2 没看 T3 的惨案，今年策略是前 30min 不碰键盘，先把所有题看一遍。

8:30 开题

T1 对于一个串显然要么顺序排，要么逆序排，然后就可以推出一个串 \(s_i\) 不合法当且仅当存在 \(j \not = i, \max\limits_{a \in s_j} a \leq \min\limits_{b \in s_i} b\)，直接扫一遍即可，复杂度 \(O(n(n+m))\)，期望得分 \(100\)。但是我先不写。
T2 看起来要建图？第一眼没什么好的想法，先放着。但是看起来很好做。
T3 大概是个 dp，很快看出了 \(O(qnm)\) 的 dp，期望得分 \(35\)，然后问题就转化为了平面上 ban 掉一些点，从左下角走到右上角是否可行，接下来就没什么好的思路了，先跳。（没错这个人甚至没想到贪心）
T4 一眼线段树优化 dp，哦 \(O(n\log n)\) 有 \(56\)，哦离散化就可以做到 \(O(m\log m)\)，哦然后就做完了。？？？这是 NOIP T4？？？

9:00 左右

憋不住了，我要开始写代码。
大概 3min 写完了 T1，然后花 10min 测了大样例顺便挂了个拍子（因为去年 T1 挂了所以这种题也不敢不拍/ll），看起来没问题，看 T2。
迅速发现不可能对着赋值过程做，并且可以直接模拟赋值过程。
那么最后就相当于对于每个变量 \(x_i\) 有一个和某个变量 \(x_j\) 或 \(\neg x_j\) 相等的限制 或者 直接等于 T/F/U 的限制。
考虑使用扩展域并查集，每个变量拆成两个点表示取反和不取反，连边之后贪心地把所有 \(x_i\) 与 \(\neg x_i\) 所在的连通块全部赋为 U 即可。复杂度 $O(n \log n) $（懒得按秩合并），期望得分 \(100\)。
写写写，期间有几个细节没处理好，但是良心的出题人给了个比较小的样例，很快就调好了，谢谢出题人。
过了大样例，然后也花了点时间写了一个指数级暴力拍上，这个时候大概 10:10。

T1+T2 大概用了一个小时左右，感觉今天很顺利啊。

10:10

接下来 20min 继续花在 T3 上，还是没什么好的想法，想到还剩很多时间，大概能过 T4，所以先抓紧时间把 \(35\) 写了，过了前两个大样例。这个实在没得拍。
同时发现 T1 拍子造的数据答案好像都是 \(1\)，调整了一下 gen。

10:40 左右

开 T4。
在纸上重新把转移方程梳理了一下，开始写写写。
写到一半发现有问题，发现转移错了，改改改，这下大概没问题了。
20 多分钟写完了，过了第一个样例，优势在我。
然后第二个样例就挂了，赶快写了一个 \(O(nm^2)\) 的纯暴力对拍，顺便验证了转移的正确性。

11:10

调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调调。

12:30

卧槽怎么就剩半个小时了。
急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急急。

12:50

md，调不出来。没时间写 \(O(n\log n)\) 了，只好交了一个 \(16\) 分的 \(O(nm^2)\) 上去，我是纯小丑。
最后检查完文操，在 linux 底下把 4 道题全部过了一次编译，加了 -fsanitize=address,undefined，大概是没什么问题。
T1T2 都拍了几十万组，感觉挂不了啊。
然后就下考了。
期望得分 \(100+100+35+16=251\)，省一肯定是稳了。
但是如果早点放弃 T4 的话我觉得还是可以有 \([291,356]\) 的。
不过本来就没打算继续打省选，对我来说其实也没什么区别，但是省排名可能会差 40~50 名吧 /ll

赛后

出考场之后还进不了机房，因为里面有人在打同步赛。
lzy，wzy，zlt 应该都 AK 了，初中同学 zsh 应该也是 AK，wcj \(375\) ，大家都好厉害。
我预言 zlt 成为 GF 历史上第一个 E 队选手！！1
ybx 会 T4 但是懒得写，大概也是 \(200\) 多分。
高一很多学弟都有 \(300+\)，初中学弟感觉好几个都打得不错。今年 GF 上一等线的感觉可以有 \(20+\) 个啊！

晚上回家只有在云斗上自测了一下，一分没挂，就是 \(251\)。洛谷上前两题也过了。
而且我只写了该拿的分，没有什么骗分的奇技淫巧，所以大概最后就是 \(251\) 了。

尾声

\(5\) 年 OI 生涯大概就这么落下帷幕了。虽然和自己初中立的目标相差甚远，但是也不是一个太差的结局吧。
清空了机房的电脑和机位上的东西，以后大概是不会怎么来这里了。
这个博客可能也不会继续维护了（不过本来就没写什么有价值的东西/hsh
可能大学会打 ACM？
接下来的 \(1.75\) 年就成为一个完全的 whker 力，祝我好运。
祝 lzy,wcj,wzy 今年都可以顺利 Au ，祝学弟们以后都能取得理想的成绩。

剩下出分后更。