NOI2024 游记

前情摘要

对于一个没有水平的 YRQ 来说，NOIP 和省选表现出了符合角色的水平。对于一个极有水平的学会来说，让 YRQ 通过了 D 体现了符合其角色的水平。

[7.2,7.15)

在南京。此处不宜出现【数据删除】。故未写。

7.15

坐了 8.5h 的高铁/hanx。

中国剩余定理二号线上没有见到任何广告牌/ng。

7.16

十一点吃过中饭来到育才，被告知成为了 JS 第一个报到选手。萌新第一次来 NOI，大佬求带/dk/kel/kel/kel。JS 第二个报到选手是 yh。我们意识到了可以从报到处顺水，遂拿了三瓶。去食堂吃了点串串题。食堂有碳酸饮料。

人来很少，遂开雀歹人场。

徽章和省代表队大概都比较齐了，换了十几枚。告急。

成为了卷室最摆的人。

下午和晚上随机游走，去沙东 A 队宿舍找到了 cxm 和 gqh，打了个左偏树板子，挂了 3 发，被 gqh 一点一点调过去了。

7.17

开幕式，dzd 喜提全场 mvp。

下午是选手练习赛，试机打了一个 fft 以防 23D1T2 这种部分分。调不出来，被 yyc 和 cxm 一起 debug。开始笔试，点进试题，发现选项已经选好了。遂晚点十五分钟，发现试题完全没改。AK。有人直接抄然后没满分因为显示的是去年同账号的选项，太乐了。幸好我没有祸害 25 年某选手。

晚上开慌了。摆到了七点半，打算写道题练点手感。挑了 21D1T3 庆典去做。训一下缩点虚树，写了一个小时。神秘 WA。被 zyf 大神指出是虚点建了 2n-2 条边/hanx。我无敌了。

7.18

08:00 观察第一页，看到了交互题/ng。16,19,22 年以后再次出现非传统题，怀疑身在 25 年。

08:01 第一眼觉得 T1 是字符串题。

08:03 考虑最小表示出序列的元素，去哈希一个子串。复杂度 O((n+m+q)\log n)。开写。

08:10 肚子疼。

08:18 写好了，彻底假了，喜提 0 分。T1 不过你过啥子啊，你不过题你打锤子啊？

08:20 开始想一点靠谱的，发现它有很强的霍尔定理背景。但这是 D1T1，但凡是 D2T1 我就往霍尔去想了。得想点靠谱的。还是考虑一个支持右加入左删除的哈希去双指针。几分钟发现了题目中的“置换”相当于只保留不同颜色的出现位置的集合的集合。

08:35 肚子的疼，去了趟厕所。

08:45 开始写 T1，15 分钟写完了一个不靠谱的哈希。过了大样例但是 selfEval 80 分。大危险。

09:30 换上了一个靠谱的哈希过了 selfEval，通读了一遍代码觉得非常靠谱遂不进行对拍。

09:45 看懂 T2 在说啥，有预感这道题会成为类似 APIO T3 的不得不做题。只有通过或者拿到极高分才能不像 APIO 彻头彻尾遗憾离场。写了个 \binom{n}{2} 的暴力过了 15，以 2 为底的归并过了 11。

10:00 降低询问批数肯定是要换底，考虑 2 几次再 3 几次，嚯嚯了 47 分。

10:10 进一步调参，搞到了 63 甚至 57 分。

10:30 考虑加入一些原始暴力以及 4 甚至更高的不可确定的底。加上神秘调参搞到了 t=9 的 78 分。

10:40 观察到接下来的部分分几乎一分一档。极有可能是某种神秘最优化或者是极难的数学推导。大概是超出我的能力的，于是看 T3。

10:45 听到对面电脑的 chw 在和红牌讨论不知道什么东西，遂举个 WC 牌感叹一下。

10:50 回到电脑前开始推 T3 的任何一点东西。首先得到了一个 k-SAT 的高妙做法。顺便开看性质 B。觉得能做。

11:05 写 12 分纯暴力。

11:20 发现 B 性质下 2-SAT 建图后 x\to y,\neg y\to\neg x，只需要保留前者。缩点建 DAG，按位确定答案，相当于在 DAG 中判断能够达到的点中是否存在 tag 0，能到达该点的点钟是否存在 tag 1，对于平方档可以 bitset。开写。

11:50 写好了。完全对不了一点点。调出了十个锅。我服了/hanx。下次得把赛时手残给算进时间里去。

12:30 调出来了，测了一下发现 T3 获得了 20 分。花了快两个小时就有点幽默了。

12:35 意识到 bitset 是多余的，可以以均摊 O(n+m) 的复杂度进行判定。五分钟写完再过 8 分。

12:40 才发现 A 性质是搞笑的，写了一个 dfs 就再加 8 分。

12:50 意识到 T1 可以哈希表优化到 O(n+m+q)。但是没时间不敢写，而且我问过了红牌说是最终评测会在本机进行，自信 600ms 安全哒！开始想一些非比赛内容干坐等到比赛结束。

13:05 收草稿纸速度令人红温。

13:10 得知 chw 喜提 255 分。JS 年度 D Au 的产生。

查分前一直在干打雀。索然无味。

15:10 进入了体育馆，血压高了。100+78+36=214 没挂分，血压低了。听说对线 \sim 230。但这跟我有什么关系。

7.19

上午睡到了 9:00。

上午去了校内陶行知纪念馆，认识了三个志愿者（讲解员）。逛了半小时，聊了两小时。

下午去三峡博物馆社会活动日。在车上看到了一对人 win，真的可怕完了。

晚上打算写一道题练练手，调了 20D2T1 结果被 zyf 一步一步透。

7.20

起来之后就感觉留给我的时间不多了。

08:00 NOI 久违考了一次传统题，真是复古。

08:05 我抄考数论了我死了。

08:10 这玩意我不会判定啊我是不是糖丸了。尝试写一个看起来有点靠谱的 O(n^2) 的 “DP”。结果全错了。

08:30 发现这个可以改成类似于辗转相除的形式 O(\log) 判定。遂过 50。

08:40 开始仔细推一下性质，发现判定的 dfs 反过来跑就能有 O(ans) 的做法。开了 \max(n,m) 个 vector。过了 70。我觉得有前途。

09:10 发现在后期使用 dfs 可以大幅优化。在 4.5s 内稳定通过 90 分。

09:30 弃掉 T1。

09:40 这个 T2 感觉很有水平，我想切它。想出了一个 O(n^2) 的 DP，暂时不想写。

10:00 我会了。

10:30 我假了。

10:35 这个可以过 l=r，理论分数 45。

11:30 我写好了/ng。喜提 45 小丑分值。开 T3 了。

11:50 T3 写完了 10 分，图论非常的不擅长啊，不推了。滚回去继续打 T2。

12:00 会了链上的 h=0，继续开干。

12:20 过了 59，赢赢赢。我发现我顺带会了非链情况，启发式分裂可干。

12:50 调完过了 60，爽。

旁边是沙东 A 队 zyz，$225$。听完他成绩，我会 T2 了。在赛时不能够写出来，我觉得这完全就是实力的欠缺。 下午听讲，T1 没有 AC，笑硒了，大于等于 $85$ 的有大约 $370$ 个，我觉得 CN OIers 还是太恐怖了。T2 过了 $70$ 个，那靠这题还怎么翻？T3 没区分度是吧好好好。 队线是 $538$，果然是和我没啥关系了。进队得把所有有区分可能性的题目都给做出来，简直是烂透了。 Ag 确定。