← 返回题目列表

Codeforces · 1763/A

A. 绝对最大化

中文机器翻译题面 查看原题

给你一个长度为 $$$n$$$ 的数组 $$$a$$$。您可以执行以下操作多次(可能是零次):

- 选择$$$i$$$、$$$j$$$、$$$b$$$:交换$$$a_i$$$和$$$a_j$$$的二进制表示中的第$$$b$$$位。

求 $$$\max(a) - \min(a)$$$ 的最大可能值。

在二进制表示中,位从右(最低有效)到左(最高有效)编号。考虑到任何二进制表示形式的开头都有无限数量的前导零位。

例如,将 $$$0$$$ 位交换为 $$$4=100_2$$$ 和 $$$3=11_2$$$ 将得到 $$$101_2=5$$$ 和 $$$10_2=2$$$。将 $$$2$$$-nd 位交换为 $$$4=100_2$$$ 和 $$$3=11_2$$$ 将得到 $$$000_2=0_2=0$$$ 和 $$$111_2=7$$$。

这里,$$$\max(a)$$$表示数组$$$a$$$的最大元素,$$$\min(a)$$$表示数组$$$a$$$的最小元素。

$$$x$$$ 的二进制表示形式是 $$$x$$$ 以 $$$2$$$ 为基数编写。例如,以 $$$2$$$ 为基数的 $$$9$$$ 和 $$$6$$$ 分别是 $$$1001$$$ 和 $$$110$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 128$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 512$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 1024$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$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

注意

在第一个示例中,可以证明我们不需要执行任何操作 - $$$\max(a) - \min(a)$$$ 的最大值为 $$$1 - 0 = 1$$$。

在第二个示例中,任何操作都无法更改数组 - $$$\max(a) - \min(a)$$$ 的最大值为 $$$5 - 5 = 0$$$。

在第三个示例中,最初$$$a = [1, 2, 3, 4, 5]$$$,我们可以执行一个操作,取$$$i = 2$$$,$$$j = 5$$$,$$$b = 1$$$。该数组现在变为 $$$a = [1, 0, 3, 4, 7]$$$。可以证明,任何进一步的操作都不会产生更好的答案 - 因此答案是 $$$\max(a) - \min(a) = 7 - 0 = 7$$$。