NOI 2024 游记
_LHF_
2024-07-02 18:38:51
省流:$5+100+100+100+64+90+100+20=579$。
一年前,我在 NOI 赛场上折戟沉沙,一年后,我在我跌倒的地方爬起。我已经不再是以前那个我了。
#### UNR DAY0
笔试,好多坑啊。
差点就 $99$ 了,还好听到有人在叫,于是检查了一遍,查出来了。
#### UNR DAY1
看完 T1 觉得很抽象,会不了一点,然后简单思考了一下,发现只需要操作长度为 $2$ 的区间即可,然后简单感受一下,直接从后往前用一个堆维护一下即可,$7min$ 通过。
然后看 T2,刚开始转化错了,转化成了 $(x^{-1}+x+(a_i-2))$,然后觉得不可做,还好发现及时,于是变成了算 $\prod_{i=1}^{64}(x^{-1}+x+(2^i-2))^{a_i}$。
直接爆算 $\prod(2^i-2+x)^{a_i}$ 复杂度是 $O(n^3)$ 的,考虑利用 $2^i$,发现式子可以写成 $(x^{-1}+x-2+2^i)=(x^{-1}(x-1)^2+2^i)$,从大到小乘复杂度就是 $O(\log^2 p)$,前半部分再写一个线段树,复杂度 $O(n\log n\log p)$。
于是写写写,交上去发现 T 了,原来是线段树常数太大了,思考了一下,果断换莫队,然后就过了。
然后看 T3,简单观察一下,显然是建 DFA,然后暴力跑匹配,现在需要做的是加速匹配。
然后发现钦定重链是最上面那个元素往前走的状态即可,这样不用显示建 DFA,链剖之后是一棵树,所以还要求一个 $k$ 级祖先。
复杂度 $O(2^nm+qn+SA(nm+L))$,为了方便,我先把除 SA 的部分写了(其实并不长),此时过了 $3$ 个多小时,然后开始写 SA, ~~结果不出意外的写了 40 分钟,果然我是 shaber。~~ 终于在 $4$ 小时过一点的时候通过了 T3。
一看:人均 AK 场啊,大家多太恐怖了。
突然发现自己的 SA 太慢了,跑极限数据有概率被卡常(没想到吧,我 SA 写的是倍增完两次基数排序的那种),想再交一发,结果一看,发现再交一发我罚时就高了,就不是 Rank 1 了,~~于是心一横,干脆不交了。~~
不过 DAY1 官方数据还是 AK 了。居然只有两个人 AK,据说 T3 一堆假做法,标算是 $O(n^2m\log m+SA(nm+L)+qn^2)$,不过实质是差不多的。
后来想了一下,发现我建 DFA 的时候可以暴力进行第一次匹配,这样子复杂度就变成了 $O(\phi^nm+qn+SA(nm+L))$,其中 $\phi=\frac{\sqrt 5+1}2$,不过不重要了。
最后只有我和 hos AK 了,看来不能太信任 pretest。
#### UNR DAY2
看完 T1 果然还是不会做,于是想了一会儿打算先写一个暴力试试,结果还没动手写,想了想 dp……咦,好像会了。
于是速通了,整个过程大约花了 $20$ 分钟。
然后看 T2,第一眼想到二分,加点剪枝 pretest 能跑 $80$ 分。
然后看 T3,想了一下,感觉挺可做,突然想看一下榜,发现有人 T3 已经 $100$ 了,又想了一下,想出了一个 $O(q\sqrt{n\log n})$,看看数据范围,好像能过!?
于是打算开冲,突然想想 T2 这会儿还没拿到比暴力高的分,要不再想想。
于是想了一下线性的做法,想了好久,突然发现四分树查询好像是 $O(C)$ 的,其中 $C$ 是周长。
那是不是可以四分树上二分解决?但很快就叉掉了,但很快又想了一个,先倍增,然后 $2^i$ 分一块(为了方便,不妨假设 $n$ 是 $2$ 的整数次幂),然后每次把可能的那些块加进来,然后把 $i$ 减小,可以证明复杂度是 $O(n)$ 的。
然后写了一发,结果常数贼大,不过能过 $n=8\times 10^4$,有 $60$,算了不管了。
然后到了大型唐氏现场,我并没有去思考倍增能不能换成常数更小的分治,而是直接把 $n$ 不断增大直到其为 $2$ 的整数次幂,于是常数就原地起飞了。
然后去写 T3,此时其实只剩下了不到两个小时,不过好在我 T3 思路十分清晰,大致就是询问分块,然后大力单调栈处理,细节很多,写了很久、调了很久,但总算在比赛结束前调完了。
于是拿下了,看到 T3 有一堆 AC 的,我以为大家都秒了。
赛后发现,只有我 $100$,FXT $70$,其余的都 $\le 40$……
去问标算,标算居然是 $O(n\log^2 n)$ 和 $O(n\sqrt n)$,~~不过没关系,我实际跑的比标算快。~~
然后去看了看 T2 题解,发现我只要把倍增改成两维交叉分治就行了,感觉自己糖丸了。
最后居然混了个 UNR RK1,~~是不是我 NOI 要没 RP 了。~~
#### NOI DAY -1
报道日,居然下午才拿到徽章,差评。
定了一百个徽章,一天之内换出了 $\ge 30$ 个。
(好像还欠了 by_chance 一个徽章)
下午跟 ZJ,FXT 打球,观看 ZJ 大战衢州二中 OI 教练。
#### DAY 0
开幕式,又是喜闻乐见的 dzd 讲话时间。
> 我已经牺牲自己女儿好多次了。
>
> 我杜子德被全国人民吊打。
差评:怎么没有波特表演。
下午笔试。
嗯……出现了一点类似 Zayin 的行为,据说是去年对应编号的选手的作答(我还以为是 std),不过我很素质,全程是自己做的,据说有人被误导了。
pzr 笔试不是 $100$,没关系,差 $1$ 分而已。
qbf 也没满分,据说就是过度信任上一届的对应选手导致的。
不知道谁在说 xqw $98$,最后 xqw 亲自在我面前辟谣。
然后又去跟 ZJ,FXT 打球。
晚上居然没有失眠。
#### DAY 1
早上 $5:20$ 醒来,然后睡不着了……
快进到进入考场。
我的策略是:先用尽量短的时间拿下 T1,然后后两题自由发挥。
结果一看 T1:咋办啊,根本不会啊。
想了一想,$p_i=j$ 当且仅当 $i$ 在 $A$ 中的位置集合 $=j$ 在 $B$ 中的位置集合。
于是哈希一下,外层用一个 map 维护即可。
然后写写写,很快写完了,过了大样例,然后又到了喜闻乐见的差评时间:
打开 Self Eval,测了一下,结果…… CE。
于是举手向监考员求助,监考员来说是我个人的问题。
为了验证自己的猜想,我先挪走了 set.cpp,然后此时显示找不到文件,然后新建了一个 set.cpp,内容为 `int main(){return 0;}`,结果交上去还是 CE。
于是又向监考员求助,终于,过了一会儿,传来广播:Self Eval 配置错误了。说真的,当时想骂人。
不管了,先去看 T2,怎么是交互?
刚看完:直接分治不就行了。
再看一眼:怎么只能拿 $20+$ 分啊。
于是先想一下交互库应该如何自适应,发现相当于找出每次询问的点集的一个最大独立集,然后递归下去。
于是一种想法就是每个连通块都是一个团,这样每个连通块的最大独立集都是 $1$。
想了一想能不能 $>1$,想了半天都没构造出来。
于是直接写了个划分 dp,写完一看,发现距离 $100$ 的次数差得挺小的,大概只有 $\le 50$ 次,再一看……只有 $70$ 分左右,瞬间火了。
这个时候 SelfEval 能用了,于是去测了一下,wtf T1 只有 $80$ 分!?
思考了一下,可能是 map 常数太大了,换成 unordered_map 就过了。
其实当时我还有一个备用方案:把每个的哈希值随机映射之后加一起,看两边是否相等,但既然哈希表能过那就不用管了。
于是又去给 T2 调调参什么的,搞到了 $91$ 分,此时还差 $3$ 次。
然后我开始胡思乱想了,感觉是要构造一个最大独立集 $>1$ 的图,结果想了半天都没想出来,又想了一下,发现好像优化出来了,小的时候枚举划分成多少组就行了,跑了 $O(1)$ 秒就跑出最优划分方案了。
于是前两题都拿下了。
此时还有两个多小时。
然后看 T3,第一眼:这不是差分约束的板子吗?随便写写就可以得到 $O(n(n+m))$ 了,拼一个 B 可以获得 $64$ 分。
然后就 GG 了,虽说差分约束可以轻松拿到 $64$ 分,但该做法无法优化到低于 $O(n(n+m))$,于是就 GG 了。
于是开始想怎么优化,果然,想了好久都没有想出来。
还剩一个小时的时候我 T3 还是 $56$ 分,其实这时我并不想去写 B 性质,只不过不想睡一个小时,于是就把 B 性质写了。
还剩一分钟的时候突然感觉我 B 性质有个地方写错了,心想:算了,就 $8$ 分而已,不要也罢。不过最后还是过了(后来想了想好像没问题)。
出场之后突然感觉 $256,264$ 天差地别,刚才谁说 $8$ 分不重要的来着?
刚开始说队线 $264$,我也感觉周围有一万个 $264$ 的和十几个 AK 的,后来慢慢降到了 $230$ 左右。
好像 GD 只有我和 Bronya 是 $264$。
赛后才知道大家的 $64$ 分基本都是一种贪心,就我写的是差分约束,后来随便想了想,发现那个贪心优化到 $O(n\log n)$ 有一万种做法,欸……感觉最错误的地方就是一开始就往差分约束上想。
然后听 ZJ 讲述的他那紧张刺激的过程:$11:00$ 分数还是两位数,剩下两个小时直接冲到 $264$,不得不说我也为他捏了把汗,希望他 DAY2 别干这种危险事了。
然后又是打球时间。
#### DAY 1.5
社会活动喵,社会活动谢谢喵。
感觉有点抽象。
下午先在自习室把几道我做过的比较好的数论题过了一遍。本来想跟 ZJ 打球的,结果传递信息出现了一点错误。
晚上本来想去看一下 Alex_wei 的数论专题,点开一道题,发现不会,于是就开摆了。
#### DAY 2
$3:58$ 醒了,然后一直躺倒 $7:00$。
快进到进入考场。
开 T1,一想,感觉没有任何思路啊。
于是决定先打表,写了个 $O(nm)$,突然发现答案好像很小的样子,于是写了个搜。
结果 $8.9\times 10^5$ 的样例也搜过去了。
加了点优化,直接冲到 $8\times 10^6$,拿下 $90$。
感觉已经很高了,于是先去看 T2,感觉这是最正确的决定。
然后去看 T2,结果刚开始题目看错了,看错后的题目非常抽象,大家就不用关心我是怎么个错法了。
然后就像,要是题目是条件改一下(改成看对后的题意),那这就是水题了。
想了一会儿,没思路,于是再读一遍题,才发现自己看错了,于是就秒了。
大致就是观察一下,每次冲刺之后的 $\min(d_x-h_x)$ 均为冲刺后的那个点的 $d_x-h_x$。于是直接设 $f_x$ 表示点 $x$ 的答案,然后变成了如何快速转移。显然有很多做法,为了让代码简洁明了,我写的是离线线段树合并,然后又到了大型唐氏现场:
DFS 过程中实现 $[l,r]$ 级祖先的 $f$ 值之和怎么做?
我:树状数组维护树上差分就行。
别人:直接维护前缀和就行了。
是的,因此我复杂度凭空多了乘个 $\log$(别为我为啥这么唐),不过不要紧,可能是实现优秀,最慢的点也就 $1.4s$,简单卡常一下后变成了 $1.2s$,想必是没问题的。
此时只过了不到两个小时。
又折返回去看 T1,突然一想:我昨天已经比队线高很多分了,实在不行就当是白给 $10$ 分,反正 T2 已经过了,只要花点时间把 T3 暴力打满少这 $10$ 分也没关系,~~毕竟 T2 不会有人分数高于 100~~。
然后看 T3,$O(n+m)$ 判断一个点是否是一类点很简单,拼上特殊性质 A,就有 $20$ 分了,再拼一个暴力就 $25$ 了。
然后我又花了很长时间想出了特殊性质 C 的做法,算了一下,拼一下有 $55$ 分,很赚,直接开写。
先写了 A,又写了 $n\le 1000$ 的 B 性质,因为一些脑瘫问题调了一段时间。
然后开始写 C,感觉 DAY2 如果能 $245$ 那肯定稳了,结果 C 性质写了接近 $5k$,小样例一遍过大样例过不了,手造的数据也能过。为了方便,我打算先调过 B+C 性质。本来想写一个拍,但遗憾的是我连指数级暴力都没写,好吧其实是我太唐了,当时没有意识到我已经 $O(nm)$ 解决 B 性质了,于是也没拍,此时距离比赛结束还有半个小时,我满怀希望的进行调试,一行一行读代码。直到时间一分一秒的过去,我逐渐由充满希望变成了绝望,最后几分钟,我也不想调试了,干脆关掉电脑,默默的看着比赛屏幕的倒计时……
于是 DAY2 $90+100+20$ 结束了,T3 连暴力都没打满,感觉有点遗憾。说真的,感觉考 DAY2 有一种考期末考试最后一科的感觉,考场上也并没想着像 DAY1 那样拼死拼活去拿分,更多的是想着只要能金就行了。
讲个抽象事:没人过 DAY2 T1。
感觉 DAY2 最重要的决定就是 T1 写到 $90$ 就跑路。
其实回过头想一想,我 DAY2 打得挺唐的,首先是 T2 明明前缀和能做的东西我偏偏用了个树状数组,其次我到底也没意识到我 T3 暴力已经写好了,可以对拍了,感觉使用对拍 $30$ 分钟调出来特殊性质 BC 问题也不是很大。
有点难受,感觉已经吃了一正常好吃的比赛了,所以没吃午饭。
打完之后,就和 $O(1)$ 个人一起打 UNO,结果打到一半冲进来一个抽象人,声称要请 ZJ 队长去讲课,费用 $1500/h$,但他不愿意透露姓名和所在学校,问他,他就说是涟水中专的。
我:离查分不到一小时了,为啥不等查完分再说?
他:我怕你们坐地起价。
然后他被 FXT 锐评了一波,被 DX 现场开合,最后被用神奇的方法请走了。
感觉查分前的一个小时,是人生中最漫长的一个小时。ZJ 的 $O(1)$ 个人在打一种奇怪玩法的牌,我因为不会规则所以在旁边帮 ZJ 刷《皇家守卫军》,时不时帮大家报一下“距离查分只剩下 XX 分钟”。
然后查分,没挂。
跟着 ZJ 去打球,结果打了一堆非常抽象的球,能上桌并且 ZJ 接不住,用 ZJ 的话说就是用 RP 打球。不会吧,考前 UNR 先把 RP 用完了,然后考试中一点 RP 都没用,考后又把 RP 用完了。要是能用点 RP 在 DAY2 上那就好了。
晚上嘉年华去看了一下,突然感觉没啥兴趣,于是绕着篮球馆转了 $O(1)$ 圈就走了,想起初中一篇的阅读理解,大概讲的是,一个老父亲邀请别人来看电影,但他不看电影,他觉得看电影的这些人对他来说就是一场电影。
#### DAY3
本想参加一下《我与 NOI》,结果走到一半想了想干脆不去了。
回去的路上碰到 ZAK,他怎么两天都 $300$ 啊。
颁奖典礼经典:给银首鼓掌。
然后就是著名的 [虚奇文家长横扫重庆]([JiazhangNews的博客 - JiazhangNews的博客 (qoj.ac)](https://qoj.ac/blog/jiazhangnews)),大家快去点赞,遗憾的是,我没注意到比赛结束后 xqw 家长们拍了个合照。
虽说有点遗憾,不过还好,最后还是苟进了集训队,也算是顺利上岸吧。
![徽章](https://s2.loli.net/2024/07/30/cgPauRoJTFiBObW.jpg)