WC2026 游记

· · 生活·游记

实际上每天我都写了一些东西，但不过太具日记性质了，就没有放到这里。

拿到题目，仍然是考虑正序开题。

T1 看起来就很可以做。首先肯定是要倍增 x 直到 x \times 2^{k + 1} \ge y，然后再进行调整。这个时候给 x 加上 2^i，i \le k 的代价是 1，其他的代价是 2^{i - k}。那么就是一个 popcnt 就能解决的东西。

selfeval 出了 24 分。问题在哪？原来是，我们可以给 y 加上一些数，这样就能让 popcnt 变少。并且，这个变化量是 O(\log V) 的，所以给 y 增加的量就是 O(\log\log V) 的了。总复杂度 O(T\log\log V)，也就是 3 \times 10^8 左右。

selfeval 出了 96 分。卡常？？？

再看 T2，按照 (x, t) 建立坐标系，可以发现我们要使 t = 0 到 t = +\infty 至少隔 k 条线。也就是最小割是 k。

看看 C 性质，这些点只用求出最小割的大小。我们旋转坐标系 (i, j) = (x - t, x + t)，这样就貌似可以 dp 了。需要做的操作包括区间加减 1，二分。看起来很能写的样子。

（两小时后）

这么**难写！（可能因为我太菜了）

还是拼暴力吧。把 A 和 CD \land k = 1 写了看 T3 去了。

T3，感觉变成菊花再变回来对完了，获得 38 分。然后考虑神秘优化，把相邻能合并的操作合并成一个，这样就 41 分了。如果相邻不能合并，那就往前找能合并的。并且我们有充足时间枚举每一个点为根的情况。这样就有 43 分了。

然后最后 40 分钟没有任何进展。wtcl。

赛后我们几个人聚在一起讨论，发现我们年级几个人一共通过了 0 个题。用 lhf 前一天讲的方法得出其中四个人总分 \bmod\text{ } 301 = 2（注：后续发现其中一个人非常高）。

然后和非常厉害的学长讨论，发现他把 T1 过了。原来，最后那 O(\log \log V) 完全可以用打表替代。怎么我第一步就把 init 函数忽视了 /ll。

T3 因为是随机数据，也不知道会挂多少。说不定总分就变成粉兔常数了。

现在还没出成绩。

upd：出了，随机数据太强了，T3 获得了 44。同班的同学有比我高十多分的人，还是太恐怖了。

upd：获得了银牌，但是同班的那位同学获得了金牌。