GDOI2023游寄

· · 个人记录

游：广大附二日游

寄：GDOI2023 寄

Day0

体测+收到了早凉制作的手工巧克力+把学校里的书堆搬回家。

Day1

开考前吃了两块早凉制作的手工巧克力，很甜，希望早凉保佑我不挂分。

先用大概半小时看题，看了发现 T1 和 T2 居然都是看完之后感觉 T1 签到，T2 和 T3 读完题都是博弈，差点昏古七。暂时没思路。

因为一些智障问题 T1 写了半小时，感觉树可能比图更好上手，就开了 T3。

看到神奇的 5\operatorname{s}，n,m\leq10^5，我有点蒙。

很快想到了 O(m(n+k)\log^2 k) 的启发式合并做法。

之后试图想正解，但没想到。马上打了这个做法就接着看 T2 了，此时已过去 2.5\operatorname{h}。

看到 m=n-1 的部分分，我就想到了dfs树，之后就有了 k=0 的 O((n+m)d(n)) 做法：

跑dfs树，枚举连通块大小 s，要删去的树边 (x,fa[x]) 满足 s|\operatorname{size}(x)，每个连通块里只能有一个向外连边的点。

打完拍 T1，之后结束。又吃了两块早凉制作的手工巧克力。

考完知道了 T2 是圆方树，我不会。也有人说 T2 的 k=0 是点双边双啥的，让我有点蒙。

估分：100+40+48=188。

实际成绩：100+40+48=188

Day2

开考前再次吃了两块早凉制作的手工巧克力，早凉好像真能保佑我不挂分。

先用大概半小时看题，看了发现 T1 和 T2 居然都是博弈，T3 好像真一分都拿不到，差点昏古七。

冷静下来发现 T1 应该是搜索或者是SG函数，忘记用迭代加深了。

我看部分分挺多的，就直接用普通的 dfs，深度到 12 直接返回平局，这样有 55\operatorname{pts}。

写完之后卡了卡常，发现 5\sim6 应该要推一下结论，而且也已经 1.5\operatorname{h} 了，就先暂时跳过了。

发现 T2 好像和博弈没太大关系，再次试着去思考正解，再次没想到。

发现性质 A 和 C 是二分图（最小权）最大匹配，性质 B 的 \operatorname{Bob} 只有两种选择，马上就开敲了，最后挂上拍就只剩 \operatorname{1h} 了。

吐槽：途中想去上厕所，等了 \operatorname{1h} 才排到我。

费用流跑二分图最小权最大匹配，每条边权值和流量都 \in\{0,1\}，这样应该也是 O(|E|\sqrt{|V|}) 的吧。

开 T3，试图去想完美序列的性质，没想到，忘记要去补 T1 了，随便搓了个暴力就去补 T1 了，但是没补完。

考完听说学弟切了T2，膜拜。

估分：55+52+10=117

实际成绩：20+40+10=70

寄，数据很强。

总结

菜是原罪，NOIP T2T3T4，省选 D1T2,D2T1 这些题是人均都会的题，但是考场上这些一道都没过。

D2T3 这种不可做题该早点写暴力跑路的。

明年再来吧……