WC 2026游记

lbdontknow · 2026-02-09 16:08:25 · 生活·游记

T1 瞪了半天没思路，遂写暴搜。
写一半机子还死机了，喜提 5min 加时。 想了想 B 性质，是不是后几位的 popcount 就对了。
selfeval 怎么挂了怎么挂了怎么挂了。
哦原来后几位 popcount 是假的，可以通过加一让一的数量减少。
枚举加几个一就好了，最高枚不超过 popcount 个即可。
过 B 性质了。
发现暴搜搜四个操作太蠢了，发现每次可以只对小的数搜，这样就只有两种状态了。
还是想想性质吧，观察到，对于较大的那一个数做乘二的操作一定不优，于是发现较大的数只有加一的操作。
于是枚举大数加几个一，发现枚举的上限不超过大数，否则效果等同于乘二。于是就得到了一个 O(tn) 的做法。
观察 A 性质，发现两数之差也是答案的上届，于是有了 O(1000t) 的做法。
想想办法，发现枚举太多 1 是无用的，注意到对于 y 的前 len 位，肯定是由 x 去凑，于是分讨 len - 1， len， len + 1 几种情况，然后再枚举 popcount 次就做完了。 复杂度 O(t\log n)。
嗯？ 怎么只有 84 分？
原来有三个 t \leq 2.5 \times 10^7，一个 t \leq 5 \times 10^7 的点。
仔细思考，发现只有在最后一个 1 的位置加 1 才会对答案产生改变。所以只需要每一次把 y 加上 lowbit(y) 即可，复杂度 O(t \log\log n)。
嗯？96？
？
？
？
时限 3 秒，我多了半秒。
卡常。
卡常。
卡常。
give up。
看看后两题。
t2 臭老鼠不知道怎么动，拿不到分。
t3 没发现部分分 k 不用取最小值，看错题了，寄。