GDOI2023 游记

· · 个人记录

去年的游记：https://www.luogu.com.cn/blog/LHF/xing-xuan-bao-zha-ji

Day 1

8:00 左右来道赛场外面，然后在那里和各位大佬见面，为了充足调整，所以我 8:20 才进场。

然后是公布密码，密码居然不是“愚人节快乐”！？

第一层密码是四个 up，第二层好像没什么特点。

开题，先看 T1。

不会吧不会吧，怎么会出这么简单的题目？

不可能，一定读错题了，再读（\times \infty）。

然后事实证明，题目确实很水。

于是就去看题面中是否有坑。

不过没有。

很快就写完了，大样例也一遍过。

然后去看 T2，感觉 T2 有点抽象。

于是又去看了一眼 T3，看了一会儿也没什么思路。

于是先去看 T2，从部分分入手。

首先不难观察选出的点集一定是一个连通块。

考虑 k=0,m=n-1 的情况，然后不难发现固定连通块大小 p 的情况下，直接从下往上选点即可，并且此时划分方案最多一个。

然后看 k=1，发现划分方案可能不唯一，考虑枚举连通块计算答案。

但枚举连通块多半是要变成树上背包的，无法接受。

突然观察一下，不难发现重心一定会被选，于是钦定重心为根，对于每一个子树，如果大小大于等于 p+1 那么这个子树的根节点一定要被选。如果 <p 那么一定不会选，=p 需要一点点特殊处理。

然后不难发现稍微处理一下，遍历到的点数为 n/p。

于是这样复杂度就是 O(n\ln n)。

从另一个角度想，考虑对于一个简单环，如果环上大于等于两个点被选，那么整个环都要被选。

于是建出圆方树，同样是找重心，然后还是按照之前的做法。

然而细节好多。

写完了 T2 后还有两个多小时，有两种选择，想 T3 或者拍 T2。

先去想了几分钟 T3，突发奇想测一下 T2 极限数据，结果卡住不动了。

然后发现是爆栈了，开大栈之后还是不行。

结果发现做法没处理好，单次有个地方退化成了 O(n)，总复杂度 O(n^2)，直接寄。

还好问题不大，很快就弄成了 O(n\ln n)。

此时距离比赛结束还有两个多小时，我突然感觉应该有人能 AK DAY1。

然后看 T3，先考虑策略，然后发现可以看作先开除一些人，然后要求剩下的人都能匹配。

这等价于每一颗子树内员工数 \le 子树大小。

于是如果没有删除操作（特殊性质 A），就可以直接树剖了，复杂度 O(n\log^2 n)。

然后再看，发现直接用可并堆暴力处理每次询问居然可以拿 48 分，拼一下特殊性质 A 能拿 62 分。

不管了拼命堆暴力就是了。

于是先写了暴力，然后开冲特殊性质 A，然而最后没调出来，于是只有 48 分。

不过好像能过同时满足特殊性质 AB（特殊性质 B：fa_i=i-1）的点，所以可能拿更多分分（有道小图灵测得 52 分）。

然而我是 nt，事实上特殊性质 A 套一个线段树分治就可以了，复杂度 O(n\log^3 n)，不过时间不是非常充足的情况下不建议写。

出赛场后发现人均 200+，有些暴力大师 T2 拼暴力拿 75 分 T3 再拿 48 分，MoQZ 说他 T2 写了 O(\texttt{玄学}) 还带哈希表，他说应该会挂，不过小图灵上他依然拿了 248 分，wlx 估了 262 分，Bird 直接 AK 了（他 T3 O(n\log^3 n) 跑得嘎嘎快）。好像很多人 T2 都想的是 O(n\sqrt n) 的，那种做法据说细节挺多。

Day 2

今天的题偏难。

先开 T1，直接来一个开幕雷击，我根本不会分析博弈题，而且策略看起来非常麻烦，估计要寄。

然后看了眼 T2，好像还比 T1 好做。

一看数据范围：T,n,m\le 10，哦那就没事儿了。

于是思路就出来了，先建出有向图，转化成挪动棋子游戏，因为有奇偶性，于是就变成了公平组合游戏。

然后思考一下，发现好像并不能直接爆搜解决。不过做法还是挺显然的，考虑从后往前倒推，做一个类似拓扑排序的过程。

这样复杂度 O(T(nm)^3)，反正本地跑得飞快。

然而写完之后一看时间，发现已经过了一个半小时了，感觉耗时有点久（代码长度 2.7k）。

又去完善一下 T2 思路，先建出图，然后考虑基环树就对环暴力，否则的话……

然后我发现我不会了。

于是又想了一下，其实题意变成了这样：

给定一棵树，每个点有点权，对于一些边，你可以将这条边的某一边的子树整体加 1，最大化最小点权。

首先可以树上背包做到 O(n^2)。

考虑对于一条边，把哪边子树 +1 就把边定向到哪边。

思考一下，可以得出一个结论，存在一个点满足所有边都指向这个点。

然后就可以换根 dp 了，然而细节贼多，就换根那几行我盯了差不多半个小时。

然后发现基环树有个部分写错了，居然又是 WC 犯过的错误，还好发现及时。

反正 T2 总共写了 5.1k，我突然挺佩服自己的代码能力的。

然后把 9 个样例都过了，然后发现第九个样例虽然过了但是运行时间有点长。

于是开了个 O2，结果直接挂了。

此时距离比赛结束还有不到一个小时。

于是就去开虚拟机，结果虚拟机还没成功开机就查出错误了：我有个地方临时变量没赋初值，由于我代码中有个地方写得比较特殊所以很难查出来。

于是就嘎嘎乱过。

然后有两条路：检查 T1&冲击 T3。

不过 T3 我看了几眼发现基本不可做，于是干脆去检查 T1，事实证明这个策略是正确的。

我看了一会儿 T1，发现我手写队列的指针没归零，可能会爆数组。

于是赶紧改一改，还好最后没出问题。

然后也懒得对拍了（其实基本无法对拍，T1 这种题正解就是暴力）。

出赛场后听说 Bird 拿了 160 左右，据说很多人都没切 T2，不过 MoQZ 切了，他还冲了一手 T3 暴力（10 分），于是他 DAY2 就 210 了。

据说 T1 大家都花费了超过两个小时，我突然感觉我 T1 还算是写得比较快的。

最后估分是 DAY1：100+100+48=248，DAY2：100+100+0=200，总分 248+200=448，反正 yundouxueyuan.com 上测试我是这个分数。

希望不要挂分。

有道小图灵上 D2T2 挂了 TAT，挂成 60 分呜呜呜。Bird DAY2 好像挂大分了。lby（去年集训队）打得很迷惑，他 D2T1 把文操注释掉了，所以 GD 省队今年是不是没有原集训队了。

另外，疯狂 Orz 初二学长 wtc，他切掉了 D1T3，但遗憾的是他的 NOIP T1 和省选两天的 T1 都挂掉了（悲）所以无缘省队。

最后，疯狂膜拜 MoQZ大师。

关于 D1T3 我为啥小图灵上 252，其实我特殊性质 A 中唯一出错的地方是一个函数返回了节点编号，但我直接当 DFN 序来使用了，所以理论上同时能过特殊性质 AB，但因为我赛场上手贱调代码时没删调试所以直接白给了。 小图灵上可能刚好没有调用到我使用输出调试的地方所以多拿了一点分。

总结

这次省赛打得不错，但还是有一定的提升空间：

  1. 减少代码的出错率，争取做到零挂分。

  2. 增强代码能力、细节处理能力，减小写代码的时间。

还有一点非常重要，考前一定要腐败！！！！！！DAY0 晚上我在复习知识点，结果很晚都没睡着（好像只睡了 4h），DAY1 晚上我从 7:30 腐到 11:00 结果躺下去几分钟就睡着了。