← 返回题目

题库练习极差最大化

← 上一题下一题 →

A6468 | $极差最大化$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定一个长度为 $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$ 的最小元素。

输入格式

- 第一行一个整数 $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$。

输出格式

对每个测试用例，输出一个整数，表示在允许操作下 $\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

C++ 编辑器

输入

输出