NOI2023 游记

zhoukangyang · 2023-07-26 20:47:40 · 个人记录

节选自 cnblogs。

7.22

坐飞机

7.23

开幕式的时候出了学考成绩，3A1B，对我来说挺好。

笔试，简单的。写了个 noipt3。

听说有像 uoj 那样一键测样例的东西，这么牛！不过不知道笔试的时候就有，所以没用。

不打板子。

7.24

看 t1 马上会了，三十分钟搞定，但是 selfeval 怎么一直测不出来啊？

然后有个工作人员帮我把 selfeval 敲命令关掉了。

看 t2，画了几下也就会了，过了样例就扔了。这个时候还不到 1h，怎么输！！

推了推 t3 很快会了一个 \operatorname{poly}(n) 的做法。但是因为做了一个不太好的转化，导致没法做这题！甚至没法做 B 性质！然后搞了半天也只会点分治 2log。

然后试图想一些其他方法，想到了一个看似很高妙的拆贡献做法？

写了下，过了前两个样例！

测第三个，wa 了？

测了一下，发现结论假了！！

感觉又把优势全打没了啊？？？？？？？

这个时候还有 100 分钟的样子。先把 n \le 300 写了。然后试图冲 2log 做法，最后二十分钟感觉调不出来了就拼了个 A 性质跑路。

期望得分 100+100+72，实际得分 100+100+72。

刚开始感觉考得挺平凡，出场的时候甚至听有人说一堆人 ak；但是问了一圈好像没有 ak 的，查完分之后甚至听说只有 4 个 270+ 就感觉不错。

听讲题，感觉好像 t3 挺憨的啊！算了可能我更憨。

7.25

嘉年华去得比较晚。

玩飞盘高尔夫，飞不进。

玩高尔夫，好难。

玩瞎子敲锣，玩之前感觉很简单，不过玩的时候很小丑啊！不过还是过了。

玩眼疾手快，怎么只抓到两个啊！

这个时候还剩大概二十分钟的样子，摆烂了。

于是不停地玩飞盘高尔夫，飞了若干次后过了。

然后玩飞盘，好像只扔了两次 0+2 就给我过了？

于是就有纪念品了。

然后去玩高尔夫，进了。

7.26

t1 很快秒了。30 min 搞定。

t2 想了会儿，发现事实上本质是要对回文串算一个偏序啥的。

建回文自动机，用经典套路可以做到 2log。

但是 2log 看起来过不去的样子。但是发现同一个等差数列的节点上，权值是有单调性的，因此可以直接二分。

感觉很对。于是写写写，先写个暴跳 parent 吧。

赛前没打板子，还是回忆了一下 SA 和回文树怎么写。SA 写了 2log。

测测样例，发现 T 了。但是竟然是因为 SA 太慢 T 的！于是把 SA 改成 1log，不过改了好久才改对。改对之后就过样例了。

然后写倍增。写完后测了几组好像都挺快的？

想了想，发现等差数列的 \sum \log len 是 \Theta(\log n) 级别的，所以是可以过的！

感觉大样例有点弱，就先写了个对拍，改了个错以过了几万组的拍。这个时候 2.5h。

看 t3。理性分析，推推性质，猜猜结论，得到了一个复杂度是拆分数乘以 \operatorname{poly}(n) 的做法。

感觉能过 n \le 28 啊！写个先。

写完之后发现怎么样例都这么大啊！

于是先写了个暴力，调了几下就能过手捏小数据了。

然后我测了一下 n=20，飞快啊！