NOIP 2023 如 AK 记

djwj233 · 2023-11-20 08:54:06 · 个人记录

简介：再次痛失 AK 良机。 好像 AK 成功了。

出分前原标题：NOIP 2023 小丑记 II。

NOIP 啥时候能改成 IOI 赛制？？？

Day -1

NOIP 前最后一场模拟赛，在我的建议下换成了 yyandy 的。（但是这天我在打胡策）

大家普遍得分有点低。问了几个人，大家普遍觉得 yyandy 这场是 NOIP 前模拟赛的钻石马桶。

前情提要：yyandy 在 CSP 前的场被大家公认为 CSP 前质量最高的一场，在 NOIP 前的场被大家公认为 NOIP 前质量最低的一场。

简单看了眼题，感觉 C 的质量还不错！是 XXI Opencup GP of Korea 的 B，写了一下但调不出来，明天再说。

Day 0

终于调出来了。（伏笔）

下午出发去杭州，入住了阿里巴巴的亲橙酒店。

房间里有个天猫精灵，感觉非常高级，但是一用才发现是人工智障。

和称贾黏一间房，拉张花上来点了蜜雪冰城和叫了个炸鸡。漏雨带大家看了碟中谍 7，但是看到一半就睡觉了。

赛前定了策略。

由于某些原因，今年的联赛我可以乱打，因此决定一个题不拍，全力冲正解，相信出题人和自己。

Day 1

我校有“联赛那天早上开考前见过 djwj233 的人都会爆蛋”的说法，因此我在早饭时和我校每个人都打了招呼（混 乱 邪 恶），还特意没照镜子。

见到了 XJ 高三老同学，时间过得真快，初见他们时他们还在初三升高一的暑假，现在已经是他们的最后一次 NOIP 了。

非常遗憾的是，只有灰鹤还没拿过省一所以还在打，祝他好运。

座位对面是 zaky，恐怖了。

开考前看了一下大样例，感觉大样例至少数量很多，感恩！

题目名有点莫名其妙，有一个字符串题叫 dict 不知道是啥，tribool 三值布尔非常神秘，还有 expand 和 run 两个相对正常的。

开题！dict 原来是 dictionary 的缩写，和我模拟赛里 archaeology -> archaeol 一样，广义上也是押题成功！

读完 A 感觉有点神秘，想了 1min 会 \mathcal O(n(n+m)\log m) 的哈希，感觉不是确定性做法于是接着想。

发现字符集很小，于是可以 \mathcal O(nm+n^2|\Sigma|) 必然能过，打算写。

写到判断时才发现可以 \mathcal O(1) 完成，于是改写 \mathcal O(nm+n^2)，一遍过大样例。感觉这题难度适中，质量挺高！

一看时间才 15min，感觉没啥拍的必要，直接开 B！

读完 B 感觉肯定能做啊！然后仔细想了想好像扩展域并查集一下直接做完了。

写到一半感觉总有点不放心，于是换成了连边跑连通块然后二分图染色的写法，稍微长一点但是不可能假。

写完才发现大样例给的不知道是啥，咋只有两个特殊性质点啊？？？

这时候还不到 1h，上了个厕所回来想 C。读完题就知道 \mathcal O(Qn^2) 可以直接 DP，考虑推点性质。

然后用调整法证了半天，花了 0.5h 证明出来这么个东西：

若有解，一定存在一种合法解使得合法解是如下形式：

而且可以证明必定存在一组解使得这个段必定是上下交替的。

这个东西的调整过程非常漫长，要是假了也说不定。反正当我推出这个东西时惊喜地发现这东西咋只能做 \mathcal O(n^3) 了，恐怖。

上了个厕所冷静一下，这次联赛为啥会有两个较难的题？

回来打算先跳题，但是定睛一看对面 zaky 已经在一侧趴着睡着了（睡觉的姿势非常显眼所以我马上就注意到了），这么恐怖？？？

简单推理了一下：

• 现在是 10:00 左右，离开考 90min 左右；
• 感觉 zaky 必不可能没 AK 就睡觉，而且极大概率是每个题都挂了拍子；
• 由于 B 的拍子感觉不是特别好写，综上所述，zak 大概率是在 80min 以内 AK 了。
• 对应一下，本场 NOIP 的题的难度总和毛估估大概和 CF div1 前四题相当。

由于这个 C 有点神秘，那感觉 D 不会太难啊。

看完 D 的题面感觉有点奇怪，在纸上推了一小会，这为啥不能直接线段树优化 DP 啊？？？

吐槽：根据 CCF 出版的《信息学奥林匹克辞典》，使用线段树等数据结构优化 DP 属于"复杂动态规划模型的优化"，是 9 级的 NOI 级知识。为了 CNOI 的健康发展，希望出题人下次不要超纲了。

又想了一小会，感觉这么显然的东西肯定对啊！于是写写写，一会儿就过了大样例。

这时候 2h15m 的样子，赛程刚过半我就三个题了，感觉稳得很。

感觉我刚才推的这一车东西完全没法做，因为要保留 DP 状态起码就得 \mathcal O(n^2)，拿什么数据结构维护感觉至少也要 \mathcal O(Qn\log n)。

于是就先写了个 T3 的 \mathcal O(Qn^2) 暴力。

一写完发现形式非常简单，完完全全就是在网格图上求 (1,1) 能否到 (n,m) 的问题，而且一点信息都没漏。

定睛一看，一个格子 (x,y) 合法的条件是 a_x<b_y，这不是和我们 yyandy 模拟赛的 a_x+b_y\ge 0 等价吗？那不是 sxyz 今年赢麻了！

回忆一下，模拟赛里还需要计数，更强一点。我直接写写写，写完有一车锅，调调调终于过了所有大样例，

这时候 3h30m 左右，还剩 1h，感觉非常稳！

回来测了一下 C 的极限数据，0.3s，D 的极限数据是 0.8s，不可能卡常！

本来打算拍一下 B，但是感觉 B 的数据非常难造，于是开摆了。

大致读了一遍 B 的代码，还剩大概 20min，测了一遍所有大样例，然后开始吃东西。

目击到 zaky 在 12:50 分起床了。

13:00 结束了，一问 zaky 发现他 70min AK，非常恐怖！

mermer 只写了 C 的 \mathcal O(Qn\log n)，所以不到 400。

yyandy 好像写 T4 没调完，只有 352，感觉有点寄。除此以外，我问到的别的几乎所有人都声称自己 AK 了。

看到芸豆数据出了，一测发现 100 + 100 + 75 + 100 = 375，怎么会是呢？

拿了漏宝的拍子拍了半天，终于拍出锅了。

调完回来一看芸豆出了第二版数据，我成 85 了；又过了一会儿出了第三版，我直接 100 了，难蚌。

在 xtl, xyd 上我都是 100，在锣鼓上是 95，听天由命了。

我究竟写挂了啥

• （我的做法钦定了 a_1<b_1）

  若 a 中最小值出现了至少两次，则我的代码在维护两边的单调栈时只会找最前面的最小值和最后面的最小值，中间部分会被我忽略。

  （不过这个锅修不修好像）

• 有个地方本来要在 b_x\ge a_y 时返回不合法，我写成了 b_x>a_y。

感觉不会挂特别多分。

Day 2

得知开考前最后一个见到我的 zaky 文件夹建错爆蛋了，有点难绷。

很多人都有或多或少的挂分，像极了我所认识的 CNOI。

Day ?

官方数据好像没卡我，大概是 AK 了。

小猴 FST 成 365，让我们拭目以待。