CF1945H 题解

EuphoricStar · 2024-03-20 09:00:11 · 题解

感觉是这场唯一比较有趣的题？

首先明确一点：先手只会选 2 个数，因为数多了 \gcd 会变小，而且对方的 \text{and} 会变大。

所以对于某一位，若 0 的个数 \ge 3 那么对方的按位与这一位一定是 0。

所以若 0 的个数 \le 2，那么可能会选这一位是 0 的，导致对方的按位与这一位是 1。把它们加入一个集合 S 中。

对每一位做这一步后 S 的大小为 O(\log V)。枚举 S 中的每个元素，再 O(n) 枚举另外一个选什么，O(\log V) check 一下即可（O(\log V) 是因为要算 \gcd。还要写一个 ST 表查询区间按位与）。

令 T = \{1, 2, \ldots, n\} \setminus S。此时还没有考虑选 T 中的数。但是因为选 T 中的任意两个数，剩下的数的按位与都等于原序列的按位与，所以我们只可能选 T 中两两 \gcd 最大的两个数，设它们为 a_x, a_y。特殊考虑一下它们即可。

总时间复杂度 O(n (\log n + \log^2 V))。

code