GDOI2025 游记

· · 生活·游记

技不如人，甘拜下风。实力就摆在那里，没什么好狡辩的。

Day 0

抵达佛山。

在试机的时候见到了一些老熟人。

Day 1

有点小感冒。据某人说我前一天晚上没盖被子，但是我记得我盖了的/jy

开题。先是通读全文并默写缺省源。思考一下 T1，似乎是简单题，拆出来两个限制再判断是否合法就好了。开写，中间突然发现限制好像列错了，不过这不重要。最终在 9:03 通过大样例。

然后做 T2。观察了一下题目，感觉非常不可做啊？？？看完数据范围后发现最后有一句“请注意本题特别的时空限制”，那就是 O(\frac{n^2}{\omega}) 没跑了。先写了个 O(nq)，然后开始思考做法。一直没想分块，因为感觉这个东西对优化复杂度没有任何用处，所以一直想直接做。然后显然做不出来，所以开始乱搞，给 B 性质手写了个 bitset 从上往下找到最大的，大样例只跑了 2s 左右，假装他过了。然后尝试故技重施去乱搞 A 性质，但是写出来 60000 都跑了 11s，破大防。此时已经 10:00 了，准备去看 T3。

看完之后感觉 T3 就是神秘东西，好像只会一个爆搜/jk。写完爆搜后看了一下有啥性质，发现有一个树，感觉应当会比较好做。猜了一些乱七八糟的做法后面发现可以直接对于每个子树求然后贪心合并，于是直接就可以过 n\le 2000，再发现比较字典序只用比一位，所以精细实现一下就可以过掉树。不知道为啥写完已经 12:30 了，思考能不能去掉 A 的限制，发现直接对于每一个连通块先求一次，排序后做一个 dfs 状物就可以了，开 rush。12:52 的时候写完并且不 segment fault 了，但是大样例第一个是对的，后面随机输出了一些 0 与负数。急急忙忙去查哪里多测没清，但是根本查不出来。最后遗憾离场。

Day 1 得分：[0,100]+[0,36]+[0,32]=[0,168]。

下午去买了点感冒药，喝了以后感觉神清气爽。据【数据删除】称 172 是队线，感觉很假吧。

晚上 weiger 大战奶龙失败。

Day 2

早上头有点晕乎乎的，但是酒店水喝完了就没打算喝药。

开考。仍然是通读全文并默写缺省源。观察了一下 T1，越看越觉得直接按 t 贪心就是对的，再注意到只用判可行性那不直接对完了。感觉 d2t1 不能有这么唐，所以先写了个暴力。结果在暴力写挂成只调整当前点而不调整其他点的情况下通过了大样例 30 组数据中的 29 组，有点逆天了。不过改完之后就正常了。后面的部分直接就是 ABC 原题，贺了一个 CHD 的写法在 9:25 左右过了。

然后看 T2。想了一下发现这不是矩阵树水题吗，然后发现看成算生成树个数了 /lh。重新想，感觉 B 就是一个简单结论，C 就是一个 DAG 容斥，正解应该就是 C 再上一个 Kruskal，准备打完爆搜之后开始大战。结果这个爆搜一直调不过样例？？？破大防，先去看 T3。

T3 越看越神秘啊，似乎只会爆搜和一个看起来比较平凡的 AB。不过好在这次爆搜一遍写对了，然后尝试大战 AB。写了一下一直不对，而且越想越红温，感觉差不多就能做出来却一直过不了。此时 12:15 了，根据经验及时弃掉去调 T2 爆搜了。

在草稿纸画画突然在 12:30 发现 Prim 求有向图 MST 是错的？？？不是哥们我最开始还想不能用 Prim 求这玩意结果你转头就忘了？？？于是马上重构换成爆搜 MST 然后高维前缀 OR 的东西，最终在结束前 1min 调了出来，检查了下文操就结束了。

Day 2 得分：[0,100]+[0,12]+[0,8]=[0,120]。

两天得分：[0,168]+[0,120]=[0,288]。

很难想象我是怎么打出来这么唐的省选的，3h 大战 12pts 爆搜也是没谁了，两题签到的场连 300 都没有上。

【数据删除】说我大概在边缘地带，姑且认为是 D 类边缘吧。

也许是我太眼高手低了。就算再给我一年，我又能有多少胜算呢？

那么多如果 可能如果我 可惜没如果

只剩下结果

Day ?

Day 1: 100+0+28=128。