GDOI2026右击

· · 生活·游记

day -2

感冒了，进入在家 lululu 环节。

day 0

前往学校坐车。Z 早上问我有没有看他发的 CF *3000~3500 构造/交互题单，我说省选应该不会出交互吧？构造感觉也不会出是不是。

酒店就在中山纪中门口，但是设施较为简陋（我到晚上洗澡的时候才发现由于没有干湿分离纸巾会被淋湿），价格还不便宜。

下午打球，打的比较搞笑。

晚上被 xnb 请吃饭了，乳鸽和脆肉鲩（天啊这个字原来读 huan）都还可以。

很【】的是要求 7:40 前进入校门，是想让我进去罚站半小时吗？

晚上成功睡觉。

day1

好像咳嗽加剧了一点，无所谓，头不晕。

看题，发现 A 是传统小数数，B 怎么是字符串+构造？C 怎么是纯粹的构造？感觉要死了。于是先做 A，很快胡了一个做法，写完发现过不了样例。调了一会发现原来是假了，心脏骤停。不过好像套个多项式除法即可，缝缝补补了一年才过。

然后想 B，先会了全 0，然后忽然有了一种倒着扫的思路，此时要记录长度，总之是 O(\text{poly}(nk)) 的。好像只有 \varepsilon 分，想了一年发现这个自动机还很难建。咦那我为啥不直接正着扫呢，这样可以把状态改成最短长度，少一维，bfs 一下直接 O(nk\sqrt{k}) 了。好像空间吃紧，但是随便卡卡就行了。大样例 1.2s，应该能过吧。

然后做 C，发现 m=2 好像可以按住一个位置不劈，剩下的是一个前缀到左边状物，能否移动到另一边只跟模 3 有关。那这个是不是可以扩展的？看小样例也不太好验证结论，于是我直接写了个 O(tn^3) 上去。写完发现咋过不了最后一个样例？完蛋。最后拼了前 12 分，但是怎么感觉 O(2^nn) 过不了前两个点啊。

下午继续打球，晚上跟父母一起吃饭。感觉龙利鱼不太好吃。

晚上睡得稍微晚了一点。

day2

咳嗽咳疯了。

上来看到一个交互一个构造一个神秘定义 ds 直接破防了。

想了一会发现 A 好像只需要关心所有前后缀的 mex，那有效值好像只有 n-1 个，随便写写就能过。然后每个数有一个 [l,r] 的位置限制，可以从左往右扫，然后贪心地选目前 r 最小的即可。我不会在 devc++ 下测交互题，最后开虚拟机完成了工作。

不会 B 咋办。思考一下感觉 k=3 存在一个使得答案一直变小的操作方案，写了一下发现是对的，应该能跑过去？

C 更是难以刻画，本来想的是每层 \times\ \omega，不过并不行。想了一会发现可以每次 x\gets \omega^x。不会维护，写了个 O(nm\log n) 跑路。

继续拼包。发现 C #2 也是容易的，哇又多了 4 分。但是第一个点这个链咋做啊。好像有点复杂。于是去思考 B n\le8，发现答案可能是 \binom{n}{2}-O(n)，于是可以线性基后爆搜？总之写了，可能获得 8 分。然后没时间了。没事，死不可怕，死是凉爽的夏夜，可供人无忧的安眠。

最后是 100+100+[4,12]+100+[0,20]+20=[324,352]，有点弱。

唉不是没人告诉我 d2t3 第一个点是菊花啊？？？