【题解】StarryCoding P211 勇闯高塔

题目传送门：P211 勇闯高塔 | StarryCoding算法竞赛平台

题目描述

很久很久以前，宇宙混沌一片，一天，一位神祇出现，凭借一把巨大的神斧将混沌撕裂，混沌渐渐分开，形成了天和地。在那之后，神祇并没有把祂的开天斧带走，那只巨斧被留在了地面上，化形成了一座高塔。

传说中，在高塔的顶端，遗留着开天神的宝藏，关于宝藏，有的人说是无数的金银珠宝，有的人说是绝世神斧，众说纷纭，但是宝藏的真面目，没人看到过，也没人知道。但是人们清楚的是，在高塔内，有长期待在里面的生物吸收了开天斧留下的灵气，作为了守护神守卫着高塔的宝藏。

这天，有一位勇者为了看清宝藏的真面目，闯进了高塔内，$n$个血量为$a$的怪物出现在了勇者面前。

勇者有两个技能:

• 血量交换：选择$i$、$j$、$b$，交换$a_i$ 和$a_j$的二进制表示中的第$b$个数字。
• 斩击：发出一次斩击。造成一次值为$\max (a)-\min (a)$的伤害。

勇者希望节省力气，尽量少的发动斩击，而血量交换因为不消耗体力，可以执行任意次。

求发动一次斩击能达到的最大伤害量（）。

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

例如，将$4=100_2$ 和$3=11_2$的第$0$位交换将得到$101_2=5$和$10_2=2$。将$4=100_2$和$3=11_2$的第$2$位交换将得到$000_2=0_2=0$和$111_2=7$。

其中，$\max (a)$表示数组$a$的最大元素，$\min (a)$表示数组$a$的最小元素。

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

输入描述

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

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

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\dots ,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

思路

对于最大的元素，我们希望它的每一位都尽可能地设置为$1$；对于最小的元素，我们希望它的每一位都能尽可能地设置为$0$。

因为是无限制地交换，对于二进制中某一位上的数字，我们都可以通过两两交换换到另一个数字上。换句话说，对于二进制中某一位上的数字，只要有$0$出现，我们都可以将它换到我们所需的最小数字的二进制对应位置上面。对于最大数所需的$1$也是如此。

因为数据范围很小，本题解法较多。这里介绍写法相对简单的一种。我们可以利用与运算有$0$得$0$的性质，通过对所有元素两两进行与运算得到最小数；利用或运算有$1$得$1$的性质，通过对所有元素两两进行或运算得到最大数。最后相减得到答案。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1000;

int a[N];

void solve()
{
    int n; cin >> n;
    for(int i = 0; i < n; ++i) cin >> a[i];
    int mi = a[0], ma = a[0];
    for(int i = 1; i < n; ++i)
    {
        mi &= a[i];
        ma |= a[i];
    }
    cout << ma - mi << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _; cin >> _;
    while(_--) solve();
    return 0;
}

本题由codeforces上的1763A改编而成