NOIP2024爆栈游记

kkxacj · 2024-11-30 23:08:25 · 生活·游记

Day -1

明天就考试了，开始复习，把一些常用的都打了一遍。

下午三点去八中试机，感觉显示屏有点小，键盘还可以，速度感觉看机子，不一样。

Day 0

省流：您即将看到的是忘记如何开栈空间被暗杀的选手。

发了解压密码，开 T1，每个位置贡献都是一样的，直接贪心就行了，8:55 左右过了大样例。

开 T2，一开始想直接算，发现算重了，直接改为 dp，f_{i,0/1} 表示第 i 个数是否确定了值，打了是对的。

然后离散化后每次快速处理一段都没赋值的，转移即可，11:00 过完大样例。

开 T3，想想发现没什么思路，去打了个树形 dp 发现有点问题，不过感觉能过 k=1 的，测试第三个大样例，咦？怎么只输出了一个还是错的？我一想肯定是报栈了随便返回了一个错误值就没管了，因为我不会开栈空间。

看 T4，很经典的结论，区间 lca 就是 dfn 序最小和最大的数的 lca，打了暴力和特殊性质 B。

然后一测第三个，咦？怎么又不行，又爆栈了，只好拿暴力拍了一下感觉特殊性质 B没问题就不管了。

然后继续想 A，突然想到可以倒序枚举 x，将所有 dep_i \ge x 的染色，询问就变成了区间最长染色数是否 \ge k。（赛后才知道可以整体二分，但当时唐完了一直在想怎么倒序加）

又回去想 T3，想啊想啊想，实在不会，先去把性质 A,B 写了，k=1 实在测不了就没管。

当时预计得分 100+100+[16,40]+32=[248,272]。

事实是一出来重构就发现有问题，而且爆栈是直接RE会不返回东西，也就是当时其实没过，希望数据给个机会。

说实话心里还是有点难受的，不过都过去了，就不去想了，感觉还是自己做的题太少了，很多算法都不太熟练，现在多暴露一些问题也是好事，起码在下一次能够避免。