GDKOI 2024 游记

Day 0

和同校大佬~~小南娘~~（他要求改的）大佬（他要求改的），嗨到一点睡觉，这下比赛的时候尴尬了。

Day 1

起大早起来悠闲吃早餐，然后坐在床上发呆 10min，着急吃早餐，着急上大巴，着急进考场，然后坐在考场发呆 30min。

T1，给一个二分图，边是黑白的，求一组完美匹配，使得黑色边的个数是偶数。

T2大分块，哈人。

T3神笔计数 DP，哈人。

打完暴力看了一圈好像只有 T1，可做，然后开始莽 T1，一直找有解的充要条件，考虑到了染色，如果有解一定无法染色成功，但是反例就是 000 的情况，发呆到结束。

下午讲解，T1 我的思路好像有点碰上了，考虑找到一组完美匹配，然后如果偶数条边就直接输出，如果没有就直接输出无解，否则建新图，然后判奇环，答案就是奇环上的边，没看懂怎么建的图。

T2 大分块，阿巴阿巴，T3 神仙 DP，阿巴阿巴。

发成绩之后发现 B 题的 $O(qm\log n)$ 20pts 挂了，全 TLE，怀疑对拍的时候把暴力代码交上去了?。

Day 2

晚上又是12:00 睡的 ?。

进考场前看了最小链划分，然而并没有考到。

T1 给你一个牌堆，每张牌有赚费和亏费，初始有 E 费，问有多少区间组成的手牌在随机排列时可以无限。

显然每一轮都必须不掉费，不然显然无法无限，此外，不能在中间过程中费用为负数，考虑 $c_i$ 表示打出一张牌之后费用的变化量，那么只有两种情况，即打出所有负数牌，在打一张正数牌前寄了，另一种情况时保留一张负数牌，最后打出它。

两种情况可以写成 $\max_{i = l}^rd_i$，当 $c_i > 0$ 时，$d_i = a_i$，否则 $d_i = a_i - c_i$。两种情况可以合并成 $sum - \max\ge E$，然后去掉 $l = r$ 的情况，观察到有单调性，预处理 $q_l$ 表示最大的 $r$，计数：$ l < r, s_l\le s_r, q_l\ge r$，三维偏序 CDQ分治即可。

T1 码了 3h，感觉很寄，T2 感觉很毒，打了暴力跑了，T3 感觉很经典，但是不是很经典，打了暴力跑了。

最后 30min 瞪出 T2 35pts，码不出来了。

出来讨论发现 T1 式子好像推错了，这下尴尬了，幸好留了部分分。

T1 好像不用 CDQ，这下不懂了。

T2 是 $f(x) = (1 + x)(1 + x^2)...(1 + x^?)$ 的应用，单位根，多项式什么什么的，放心了。

T3 是推性质，一个十字在周围做四遍会变成大十字，可以看作把图奇偶缩小一半后新图上的一次小十字操作，这样分支下去，直到 $n = 2$ 的边界情况。

总结：光荣挂分。