MX22 测 C 题

· · 个人记录

ABD 都是基本题，加起来就打了 150 值得反省。

主要说一下 C 题。

注意这个做法的本质，就是我们不断的根据最高位将当前的边集合 $E$ 分为 $E_0$ 和 $E_1$。 如果 $E_0$ 就能让图连通，我们肯定是选 $E_0$ 的，并在这上面继续这个过程；否则，我们当前的边集仍然是 $E$。 我们的答案就是按照这个过程走得到的答案。 我们发现很难独立考虑新边对每一位的贡献。 考虑每一位