Problem - 1299A - Codeforces

题目大意：

定义一个函数f(x,y) = (x∣y)−y。

给定一个长度为 n 数列 a，定义 f(f..f(f(a1​,a2​),a3​),...an−1​),an​)

为这个数列的值。

现在，请你将数列改变一种顺序，使得最后的值最大。 输出你改变后的数列。

思路：

那么对整个序列的操作其实也就是。

f(f..f(f(a1​,a2​),a3​),...an−1​),an​) = f(a1​,(a2​∣a3​∣…∣an​))

即从第一个数字的二进制中抠掉后面所有数字的二进制。

也容易得知，最后的结果跟 除第一个数字外 其它数字的顺序是无关的。

那么，我们只需要让第一个数字最大（含有最高二进制位的）就好了。

但是有共同的最高位时，这个最高位会被抠掉！

所以最终答案是：让含有最高且唯一的二进制位的数字到最前面就好啦。

代码：

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>using namespace std;
#define endl '\n'
#define int long longint n,g,b;void solve()
{int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i ++ ) cin >> a[i];for(int i = 30; i >= 0; i --)  // 从最高位开始枚举{int tt = 1 << i, cnt = 0, idx = 0;for(int j = 0; j < n; j ++)  // 遍历每一个数{if(a[j] & tt) idx = j,cnt ++;  // 如果这个数存在当前进制位}if(cnt == 1) // 并且所有数中只存在一个{swap(a[0], a[idx]);break;}}for (int i = 0; i < n; i ++ ) cout << a[i] << " ";
}signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);int T = 1;//cin >> T;while(T --){solve();}return 0;
}