GDOI2025 游记

acb437 · 2025-03-04 14:05:24 · 生活·游记

GDOI2025 游记

Day 0 2/28

中午大概 1100 出发去佛山，中午随便找了家店吃了午饭，然后就去石实实验等着报道和试机。试机时发现考场的电脑上居然有配置好的 VS Code 可以用，非常惊喜。第一次试机，也不知道有什么讲究，随便打了点东西就准备走。但是机房里还有很多人不知道在打什么，听他们说话好像在测时间之类的性能问题，本校的其他人也还没走，所以我就继续随便打了点东西。

接着就去酒店办入住，然后玩了一下午，成功出货了碧蓝的新彩，我们意系终于站起来了！

晚上写了一下平衡树板子，以免显得我今天什么都没干，大概 2300 睡的。

Day 1 3/1

早上 0700 起床，大约 0810 进场。非常让我惊讶的是考场不让带纸巾进去，只能用考场里面的纸巾，体验了一把高层次比赛的反作弊手段。

解压码是：keeP*drEAm&iNg。

一看就知道 T1 不会做，瞪眼瞪了半天，考虑了枚举每个数检验，然后想出来一个假的 O(n) 检验，然后就一直干瞪着。

接着看 T2，发现 T2 的暴力简单一点，就直接打了 20pts，然后考虑了每个性质，结论就是这些性质我都不会写，不知道怎么维护每个点可以到达的点的信息（后来听同学说用主席树就可以，然后就可以过一些部分分了，只能说主席树这么用确实没怎么见过，脑子也比较废，想不出来）。不会做之后就把 T1 的 20pts 写了。

最后的时间看了 T3，更是一眼不会，什么都没看出来，最后连暴力也没来得及调出来。

不出问题的话，应该就是 20+20+0=40 了，说实话这个分数我是一点都不奇怪的，毕竟水平摆在那里。但是当我被指早早放弃的时候，仔细想想好像是有点道理，毕竟后面那些时间基本在干瞪眼，我有没有思考呢？如有。

下午和晚上继续呆在酒店玩，看了碧蓝这次活动的剧情，更喜欢马可波罗小姐了。

晚上没睡好，一直到 2400 之前都睡睡醒醒迷迷糊糊的。

Day 2 3/2

仍然是 0700 起床，0810 进场。

解压码是：ReM#Ain(LoVinG。

这回 T1 好像会做了，感觉直接按照时间贪心是对的，想了想好像道理是对的，但是不太严谨的样子，然后好像要用线段树。把线段树的大概框架打完之后决定先用暴力验证一下贪心的正确性，就用暴力过了一遍大样例。

写线段树的过程中发现一处查询的复杂度会上升至 \log^2_2 n，虽然有 6 组数据，但是我还是决定相信单组 2\times 10^5 规模的数据能放我过去（这么一想起来，一个点不就是 1.2\times 10^6 级别的？当时居然没加快读）。

写完之后调了很久，调完之后已经大概 1200 了。出于对 \log^2_2 n 的不信任，我让程序对 move5 的前 5 组数据只读入不处理，只处理第 6 组数据，最后跑了接近 0.5s，也就是说跑满 6 组可能要 3s。

我只能希望这多出来的 1s 能被评测机的性能掩盖掉，虽然早就听说评测机挺差的，因为我真不会优化掉这个瓶颈。所以分数在 [72,100]，但是听说正解是 O(n\log_2 n)，很可能就只有 72pts 了。

T2 简单扫了一眼，发现有概率之后就不太想细看了，虽然后面写完 T3 暴力发现好像 T2 的暴力是可以写的，但是已经来不及了。

T3 看了下，发现如果我把搜索和 B 性质写了的话就有刚好 28pts，可以确保 Day2 能上 100pts，但是不会写 B 性质，决定写了搜索然后找规律。然后最后 20min 我根本找不出规律。

最后本来想开 NOI Linux 虚拟机跑一下程序看看的，结果发现由于之前根本没研究过，我压根不会把 Windows 下的代码拷到虚拟机里，考虑到我写的代码里应该也没什么 UB 或者语法问题，所以就放弃了。

不出意外的话 Day2 应该是 [72,100]+0+8=[80,108] 了。

结语

确实存在这样一个问题：做法要是想到了就会，没想到就不会，然后也不会对做法进行积极地探索。当然其中一个原因确实是早在开考前就做好了这次两天总分不上 100pts 的心理准备，所以当 Day1 看起来无路可走时，由于心里相信这就是我能做到的全部，所以基本上就是在干瞪眼了。

Day2 不算受到了这个问题的影响，因为 Day2 是真的调了太长时间，说明对数据结构还是不太熟练，一些常见信息都不太会维护。

记于 2025/3/4。

Update 2025/3/14

上周找到代码之后交到洛谷上发现 D2T1 只有 4pts，怎么回事呢？还记得前面说的

出于对 \log^2_2 n 的不信任，我让程序对 move5 的前 5 组数据只读入不处理，只处理第 6 组数据

吗？

代码中的 if(n < 1e5)continue; 忘删了，删掉之后洛谷上就有 76pts。