309942: CF1763A. Absolute Maximization
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Absolute Maximization
题意翻译
给定一个长为 $n$ 的数组 $a$，你可以执行一种操作： 选择 $i, j, b$，交换 $a_i$ 和 $a_j$ 二进制表示上的第 $k$ 位。 要求经过若干次操作后，最大化 $a$ 数组中最大值减去最小值的值，请输出这个值。 By @hswfwkj题目描述
You are given an array $ a $ of length $ n $ . You can perform the following operation several (possibly, zero) times: - Choose $ i $ , $ j $ , $ b $ : Swap the $ b $ -th digit in the binary representation of $ a_i $ and $ a_j $ . Find the maximum possible value of $ \max(a) - \min(a) $ . In a binary representation, bits are numbered from right (least significant) to left (most significant). Consider that there are an infinite number of leading zero bits at the beginning of any binary representation. For example, swap the $ 0 $ -th bit for $ 4=100_2 $ and $ 3=11_2 $ will result $ 101_2=5 $ and $ 10_2=2 $ . Swap the $ 2 $ -nd bit for $ 4=100_2 $ and $ 3=11_2 $ will result $ 000_2=0_2=0 $ and $ 111_2=7 $ . Here, $ \max(a) $ denotes the maximum element of array $ a $ and $ \min(a) $ denotes the minimum element of array $ a $ . The binary representation of $ x $ is $ x $ written in base $ 2 $ . For example, $ 9 $ and $ 6 $ written in base $ 2 $ are $ 1001 $ and $ 110 $ , respectively.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 128 $ ) — the number of testcases. The first line of each test case contains a single integer $ n $ ( $ 3 \le n \le 512 $ ) — the length of array $ a $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i < 1024 $ ) — the elements of array $ a $ . It's guaranteed that the sum of $ n $ over all testcases does not exceed $ 512 $ .
输出格式
For each testcase, print one integer — the maximum possible value of $ \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说明
In the first example, it can be shown that we do not need to perform any operations — the maximum value of $ \max(a) - \min(a) $ is $ 1 - 0 = 1 $ . In the second example, no operation can change the array — the maximum value of $ \max(a) - \min(a) $ is $ 5 - 5 = 0 $ . In the third example, initially $ a = [1, 2, 3, 4, 5] $ , we can perform one operation taking $ i = 2 $ , $ j = 5 $ , $ b = 1 $ . The array now becomes $ a = [1, 0, 3, 4, 7] $ . It can be shown that any further operations do not lead to a better answer — therefore the answer is $ \max(a) - \min(a) = 7 - 0 = 7 $ .Input
题意翻译
给定一个长为 $n$ 的数组 $a$，你可以执行一种操作： 选择 $i, j, b$，交换 $a_i$ 和 $a_j$ 二进制表示上的第 $k$ 位。 要求经过若干次操作后，最大化 $a$ 数组中最大值减去最小值的值，请输出这个值。 By @hswfwkjOutput
题目大意：
给定一个长度为 $ n $ 的数组 $ a $，可以执行以下操作任意次（可能零次）：
- 选择 $ i $, $ j $, $ b $：交换数组中 $ a_i $ 和 $ a_j $ 二进制表示的第 $ b $ 位。
要求通过上述操作，使得数组 $ a $ 中的最大值与最小值之差最大化，输出这个最大可能值。
输入输出数据格式：
输入格式：
- 第一行包含一个整数 $ 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 $。
输出格式：
- 对于每个测试用例，输出一个整数——数组 $ 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
```
说明：
- 在第一个例子中，不需要执行任何操作——数组 $ a $ 中最大值与最小值之差的最大值是 $ 1 - 0 = 1 $。
- 在第二个例子中，任何操作都无法改变数组——数组 $ 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 $。题目大意： 给定一个长度为 $ n $ 的数组 $ a $，可以执行以下操作任意次（可能零次）： - 选择 $ i $, $ j $, $ b $：交换数组中 $ a_i $ 和 $ a_j $ 二进制表示的第 $ b $ 位。 要求通过上述操作，使得数组 $ a $ 中的最大值与最小值之差最大化，输出这个最大可能值。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $ 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 $。 输出格式： - 对于每个测试用例，输出一个整数——数组 $ 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 ``` 说明： - 在第一个例子中，不需要执行任何操作——数组 $ a $ 中最大值与最小值之差的最大值是 $ 1 - 0 = 1 $。 - 在第二个例子中，任何操作都无法改变数组——数组 $ 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 $。
给定一个长度为 $ n $ 的数组 $ a $，可以执行以下操作任意次（可能零次）：
- 选择 $ i $, $ j $, $ b $：交换数组中 $ a_i $ 和 $ a_j $ 二进制表示的第 $ b $ 位。
要求通过上述操作，使得数组 $ a $ 中的最大值与最小值之差最大化，输出这个最大可能值。
输入输出数据格式：
输入格式：
- 第一行包含一个整数 $ 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 $。
输出格式：
- 对于每个测试用例，输出一个整数——数组 $ 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
```
说明：
- 在第一个例子中，不需要执行任何操作——数组 $ a $ 中最大值与最小值之差的最大值是 $ 1 - 0 = 1 $。
- 在第二个例子中，任何操作都无法改变数组——数组 $ 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 $。题目大意： 给定一个长度为 $ n $ 的数组 $ a $，可以执行以下操作任意次（可能零次）： - 选择 $ i $, $ j $, $ b $：交换数组中 $ a_i $ 和 $ a_j $ 二进制表示的第 $ b $ 位。 要求通过上述操作，使得数组 $ a $ 中的最大值与最小值之差最大化，输出这个最大可能值。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $ 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 $。 输出格式： - 对于每个测试用例，输出一个整数——数组 $ 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 ``` 说明： - 在第一个例子中，不需要执行任何操作——数组 $ a $ 中最大值与最小值之差的最大值是 $ 1 - 0 = 1 $。 - 在第二个例子中，任何操作都无法改变数组——数组 $ 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 $。