GTA 6 最优信号匹配

算法思路

设当前已经确定要保留的二进制位组成掩码 $m$。最终答案包含这些位，当且仅当存在一种配对，使每一对设备在这些位上都不同，即

因此，可以按已选位上的模式分组：每组包含模式相同的 A 组元素，以及模式与其互补的 B 组元素。各组两侧的元素个数相同，组内可以任意配对，组间不能配对。最初没有选定位，所有元素属于同一组。

从第 $29$ 位到第 $0$ 位依次尝试加入答案。在每个现有组内，记 A 组当前位为 $0$ 的元素个数为 $x$，B 组当前位为 $1$ 的元素个数为 $y$。只有每组都满足 $x=y$，才能让所有配对在当前位上不同。由于两侧总数相等，A 组当前位为 $1$ 的数量也必然等于 B 组当前位为 $0$ 的数量。

若所有组均满足条件，就将当前位加入答案，并将每组分成两组：A 的 $0$ 与 B 的 $1$ 对应，A 的 $1$ 与 B 的 $0$ 对应；忽略空组。否则不选择该位，保持原来的分组。

实现时用两个数组和一组区间表示各组。先检查所有组，检查成功后再分别按互补的位值原地划分两个数组。数组内部的调整只是用于维护分组，不改变原问题中固定 A 组位置的要求；每个元素仍可对应回其原位置。题目只要求输出最大值，无须构造排列。

正确性证明

**引理 1：**在选定位掩码为 $m$ 时，一种配对满足所有选定位，当且仅当每对元素位于同一个对应组内。

**证明：**满足这些位要求等价于 A 元素在 $m$ 上的模式与 B 元素在 $m$ 上的模式互补，这正是分组依据。因此组内任意配对都满足要求，跨组配对则至少违反一个已选位。证毕。

**引理 2：**在当前分组可行的前提下，能够额外选中第 $k$ 位，当且仅当每组中 A 的该位为 $0$ 的数量等于 B 的该位为 $1$ 的数量。

**证明：**由引理 1，只需考虑各组内部。若当前位也必须为 $1$，A 的 $0$ 必须与 B 的 $1$ 配对，因此数量相等是必要条件。该条件成立时，由两侧总数相等可知另两类数量也相等，分别任意配对即可，所以也是充分条件。划分得到的非空子组仍满足引理 1 的分组不变式。证毕。

**定理：**算法输出的信号强度最大。

**证明：**从高位到低位进行归纳。初始时空掩码可行。处理某一位时，若引理 2 的条件成立，就存在保持已选高位且选中当前位的方案；选中当前位的收益大于所有更低位的收益之和，因此最优答案应当选中该位。若条件不成立，任何保留已选高位的方案都不能选中该位，只能跳过。算法始终保留可行的最大前缀，处理完所有 $30$ 位后即得到最大答案。证毕。

复杂度分析

每一位的检查与划分都会使每个元素被访问常数次，各组互不重叠。每组测试数据的时间复杂度为 $O(30n)$，额外空间复杂度为 $O(n)$。所有测试数据的总时间复杂度为 $O(30\sum n)$。