Codeforces Round 618 (Div. 2)C. Anu Has a Function

题目大意

定义 $f(x, y) = (x|y)-y$ ，有一个数组 $A$ 可以为 $[a_1, a_2, …, a_n]$ ，重排 $A$ 中的元素使得 $f(f(…f(f(a_1,a_2),a_3),…a_{n-1}),a_{n})$ 的值最大，输出重排后的 $A$

题解

思路1:

对于式子 $f(x, y)=(x|y)-y$ ，考虑 $x$ 和 $y$ 的二进制位

当 $y$ 的第 $i$ 位是1的时候， $x$ 的 $i$ 位是0还是1对结果的第 $i$ 位都没有影响，结果的第 $i$ 位都是0

当 $y$ 的第 $i$ 位是0的时候，结果的第 $i$ 位等于 $x$ 的第 $i$ 位

最终的结果只和把谁放在 $A$ 中第一的位置有关，也就是说对于 $a_1, a_2, a_3, …, a_n$ 如果想把其中的一个数字 $x$ 放在第一个，那么当 $x$ 的第 $i$ 位是1的时候，数组中的其他数字的第 $i$ 位必须全部是0函数的结果的第 $i$ 位置才能取得1，如果 $x$ 的第 $i$ 位是0的话，那么函数的结果的第 $i$ 位一定是0，所以对与每一个 $a_i$ 我们都算一下函数的最终结果，然后把最大的位置的那个放在第一个即可。

以上思路来自Akura_Mea

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
#define dbg(x) cout << #x"=" << x << endl;
const int MAX_N = 1e5+100;
int a[MAX_N];
int bit[60];
 
void in(int a){
    int idx = 0;
    while(a){
        if(a&1){
            bit[idx]++;
        }
        a >>= 1;
        ++idx;
    }
}
 
int out(int a){
    int idx = 0, ans = 0;
    while(a){
        if((a&1) && (bit[idx] == 1)){
            ans = ans + (1 << idx);
        }
        a >>= 1;
        ++idx;
    }
    return ans;
}
 
int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    int mx = 0;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        in(a[i]);
    }
    int idx = -1;
    for(int i = 0; i < n; ++i) {
        int tmp = out(a[i]); 
        if(tmp > mx){
            idx = i;
            mx = tmp;
        }
    }
    if(idx != -1) cout << a[idx] << ' ';
    for(int i = 0; i < n; ++i){
        if(i == idx) continue;
        cout << a[i] << ' ';
    }
    return 0;
}

思路2:

官方题解的做法是 $f(x, y) = (x|y)-y = x \& (\sim y)$ ，

要求 $f(f(…f(f(a_1,a_2),a_3),…a_{n-1}),a_{n})$ ，

等价于求 $a_1\&(\sim a_2)\&(\sim a_3)\&…\&(\sim a_{n-1})\&(\sim a_{n})$ ，

从式子可以看出最终的结果只和哪一个放在第一的位置有关，所以维护一个取反的前缀和还有一个取反的后缀和，就能算出哪一个放在 $a_1$ 的位置得到的最终结果最大

def wrapper(func):
    def inner():
        return next(func)
    return inner

#input = wrapper(open('in.txt'))

n = int(input())
a = list(map(int, input().strip().split()))
INF = (1 << 60) - 1
pre = [0] * (n+1)
pre[n] = INF
for i in range(n):
    if i == 0:
        pre[i] = ~a[i]
    else:
        pre[i] = pre[i-1] & (~a[i])
suf = [0] * (n+1)
suf[n] = INF
for i in range(n-1, -1, -1):
    if i == n-1:
        suf[i] = ~a[i]
    else:
        suf[i] = suf[i+1] & (~a[i])
mx, id = -1, -1
for i in range(n):
    tmp = a[i] & pre[i-1] & suf[i+1]
    if tmp > mx:
        mx = tmp
        id = i
print(a[id], end=' ')
for i in range(n):
    if i == id:
        continue
    print(a[i], end = ' ')

总结

可以看出上面两种思路实现方法不一样，但是原理都一样