2026 GDOI 联合省选

· · 生活·游记

GDOI 2026（联合省选）

Day 0

直接来试机，试了半天 sublime 尝试下载插件寄希望于明天不还原，监考老师看到告诉我会还原的别下了。后来紫玮哥告诉我 vs 好用就用了，这两天看来好像帮了我大忙。

Day 1

开 A 题，操作看着就比较复杂。一开始想到求 l 的期望，写完了才发现求不了，因为上一步 l 的具体值会影响选中的概率，到这里花了 1.5h。思考到可以 f_{i,j} 表示 i 号点 l_i=j 的概率，这样就可以向上转移，每次转移就是将该点的所有儿子合并。

赛时想到这个了，但是没有想明白具体的实现和转移就没写，用了错误的转移方法和统计答案的方法还导致多算了一个复杂度。这里浪费了一定时间为了想这个过渡做法，大概 0.5~1h。实际上再加一个 g_{i,j} 表示 l_i=j 时子树内的总答案就可以做完了。

看看 B，毫无思路，这个条件实在是太抽象了完全想不到进一步，过。

C 直接看性质，m\leq 2 好做，=1 不用说，=2只有可能是一个是一段子串另一个是其余的部分。继续看，发现奇异的条件好做，所有的数最后都要回到右边，这样看每次就是能删掉 3x 个数并将这些数异或到最后一个位置上，对于 x\equiv 0/1\pmod{2} 的不同情况好像要用不同的操作方法，样例非常厉害给了很好的解决方法帮助我完善 x\equiv0 的情况。这个 C 的暴力消耗了我比较长的时间，大概有 2h。

回去看 B，思考了全为 0 发现很好考虑，开始写。只剩半小时了，唐爆了写了个贪心还没过样例不知道为啥，一出门就想到了好像要 dp 不管了。

Day 2

看到两道交互坐不住了太诡异了（其实是一道）。看着 A 似乎比昨天好做了不少，也只是似乎，还是没法做正解。题目好像是要求在 2n 内解决都算不错的分数了，考到了双指针，如果找到 0 的位置后往左，往右扩展到更小的更新 mex，就说明更新的位置是关键位置不会变，除此之外在扩展过程中的值和位置就属于一个区间的范围，由于我们枚举的区间内的 mex 值本身就是从 1\to n 这样的，所以有空位就以任意顺序选也没问题。这个写完好像比较快，一个多小时吧。

这个题目里给的这个 grader 有点难蚌，编译后运行完瞬间消失没有 pause。干脆手动在文件里添加 system("pause")，方便。

byd 很晚后面才发现我忘了用 vscode 的终端直接无视这个问题唐完了。

还不够优秀，思考了能否二分，但是考虑到会求每个测试点里最大的操作次数，有可能扩展的次数很多，每次都是 \log n 次操作会慢（？赛后祭文说他用二分写的，我感觉有可能是我不优了。

B,C 看着就很难，跟昨天没法比。

这个 B 的操作跟昨天也挺类似都是怪异的 k 的限制啊。想了下 k=3 是否可以找反图上每个连通块上最大的环，结果不会统计这个。

C 菊花图似乎能做，但是分讨太多了就 4 分看着时间也不多了就再看看。好像能写个 O(n^3),o_x=o_y=0 发现竟然没给点道心破碎，实现也是难得很，肯定写不完了，放弃了。

倒回来看 A，发现 AB 性质好写，写了这两个点应该能满，这时发现了 vscode 的方便编译运行，也看到如果二分 C 性质应该能满，我的会丢一点分。不过无所谓了最后一个点还是分低。