链接
https://codeforces.com/contest/1300/problem/C
题意
$f(x,y)=(x\mid y)-y$
已知数组 $a$ 可以任意顺序排列，求 $f(f(f(f(a_1,a_2),a_3),…,a_{n-1}),a_n)$ 的最大值
思路
易得 $f(x,y)=(x\mid y)-y=x&(\sim y)$
可以发现对于二进制下的每一位,当 $x$ 为 $1$，$y$ 为 $0$ 时，才对答案有贡献
所以可以预处理 $prefix[1 \sim x]$ 和 $suffix[x \sim n]$ 的或运算和
然后枚举 $1 \sim n$ 作为第一个数：求出 $a[i] & \sim (prefix[1 \sim x]|suffix[x \sim n])$ 的最大值
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],pre[N],suf[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) pre[i]=pre[i-1]|a[i];
for(int i=n;i;i--) suf[i]=suf[i+1]|a[i];
int res=0;
int x=1;
for(int i=1;i<=n;i++)
if((a[i]&~(pre[i-1]|suf[i+1]))>res) {
res=a[i]&~(pre[i-1]|suf[i+1]);
x=i;
}
cout<<a[x]<<" ";
for(int i=1;i<=n;i++) if(i!=x) cout<<a[i]<<" ";
cout<<endl;
return 0;
}
|