A6468. 极差最大化
编程题
入门
知识点
题目描述
给定一个长度为 $n$ 的数组 $a$。你可以进行任意多次如下操作（也可以一次都不做）：
- 选择下标 $i,j$（$1\le i,j\le n$）和位编号 $b$（$b\ge 0$），将 $a_i$ 与 $a_j$ 的**二进制表示**中的第 $b$ 位进行交换。
请你在若干次操作后，使
$$ \max(a)\;-\;\min(a) $$
尽可能大，并输出这个最大值。
**说明：**
- 位从右向左编号，最低位为第 $0$ 位；
- 可以认为任意数的二进制表示前面都有无限多个前导 $0$；
- 例如：$4=100_2$ 与 $3=11_2$
- 交换第 $0$ 位后得到 $101_2=5$ 与 $10_2=2$；
- 交换第 $2$ 位后得到 $000_2=0$ 与 $111_2=7$。
这里，$\max(a)$ 表示数组 $a$ 的最大元素，$\min(a)$ 表示数组 $a$ 的最小元素。
- 选择下标 $i,j$（$1\le i,j\le n$）和位编号 $b$（$b\ge 0$），将 $a_i$ 与 $a_j$ 的**二进制表示**中的第 $b$ 位进行交换。
请你在若干次操作后，使
$$ \max(a)\;-\;\min(a) $$
尽可能大，并输出这个最大值。
**说明：**
- 位从右向左编号，最低位为第 $0$ 位；
- 可以认为任意数的二进制表示前面都有无限多个前导 $0$；
- 例如：$4=100_2$ 与 $3=11_2$
- 交换第 $0$ 位后得到 $101_2=5$ 与 $10_2=2$；
- 交换第 $2$ 位后得到 $000_2=0$ 与 $111_2=7$。
这里，$\max(a)$ 表示数组 $a$ 的最大元素，$\min(a)$ 表示数组 $a$ 的最小元素。
输入格式
- 第一行一个整数 $t$（$1\le t\le 128$），表示测试用例数量。
- 对于每个测试用例：
- 第一行一个整数 $n$（$3\le n\le 512$）；
- 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i<1024$）。
- 保证所有测试用例中 $n$ 的总和不超过 $512$。
- 对于每个测试用例：
- 第一行一个整数 $n$（$3\le n\le 512$）；
- 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i<1024$）。
- 保证所有测试用例中 $n$ 的总和不超过 $512$。
输出格式
对每个测试用例，输出一个整数，表示在允许操作下 $\max(a)-\min(a)$ 的**最大可能值**。
输入输出样例
输入 #1
4 3 1 0 1 4 5 5 5 5 5 1 2 3 4 5 7 20 85 100 41 76 49 36
输出 #1
1 0 7 125
说明/提示
- 样例 $1$：不做操作已最优，答案 $1-0=1$。
- 样例 $2$：数组无法通过操作改变，答案 $5-5=0$。
- 样例 $3$：可选 $i=2,\ j=5,\ b=1$，数组变为 $[1,0,3,4,7]$，之后无法再提升，答案 $7-0=7$。
- 样例 $2$：数组无法通过操作改变，答案 $5-5=0$。
- 样例 $3$：可选 $i=2,\ j=5,\ b=1$，数组变为 $[1,0,3,4,7]$，之后无法再提升，答案 $7-0=7$。