GDOI2025 游寄

· · 生活·游记

day -114514

NOIP 348pts，GD rnk 16。

day 0

GD-016。

12点半出发前往考点，雀魂四麻连续点炮，最后剩 300 点勉强保住一点脸面。

机房信号不是很好，导致看不了 loj 那个帖子，所以没有和评测机对比速度，我的线性筛 1s 能跑 1e8。

day 1

A 是容易的，eps h 切了。

B 是困难的，思考了很久也只会在无修改的情况下做到 O(\dfrac{n^2\log n}{\omega})，感觉很完蛋啊。

带着压力看了看 C，没有研究出什么东西来，连链都不会做，感觉这把完蛋了啊。

强迫自己冷静下来，发现至少 B 我还是会无修改的 O(n^2/w) 的，可以多拿 4pts/qiang。发现此时修改 A 可以用分块来维护，具体地，D_{x,y} 表示 a_y 在前 x 个块中。查询的时候差分一下即可。这样可以过特殊性质 B。

这确实缓解了我紧张的心情，考虑对 b_y 施以同样的分块，记块长为 B，可以先二分所属块，再暴力找，如此可以做到 O(\dfrac{n^2\log \dfrac{n}{B}}{\omega}+nB)，当 B 取 \dfrac{n}{\log n} 时可以做到 O(\dfrac{n^2\log\log n}{\omega}+\dfrac{n^2}{\log n})。这个东西看起来很厉害啊！写+调大概用了 1h。最后一个大样例用了 6.01s。

但是注意到我没有测速。。。我尝试卡了一下自己，极限数据要足足 10s！由于 bitset 开到 10^5 可能导致 8\times 10^4 过不去，我不得不放弃后 12pts，可恶。

此时仍有 1.5h。但是拼尽全力无法战胜 C 除 8pts 外的任何分数。

最后是 100+88+8=196，虽然不算很低，但感觉不是很够啊。

转进打牌，但是无法战胜 alex_liu。

day2

先看 A。不是怎么这么奶龙，直接开写，9:00 就写完了。

但是过不了大样例，并且只错了大数据，这并不好笑。

debug 了一年发现是多测没清空。相信一下大样例强度吧？

转进 B。不是怎么这么难啊。想了一会，并不会性质 C。甚至不会 n\le 9。这个性质 B 真的有用吗，感觉破产了。

转进 C，找了半天性质，写了个性质 B 的代码，发现假了/qiang。心态有点小蚌。最后写了个裸的暴力。

然后我 B 性质 A 居然还要找最小叶向树？这个我哪会啊。最后写出了 O(4^m3^n\text{poly}(n))，如何呢。想了一会发现 B 性质简单容斥即可，取之。

然后开始坐牢，拼搏 C 更多分未果，哎，我咋这么菜。

最后 100+88+8+100+24+8=328，没有队进了/ll。