Anu Has a Function

题目链接

Codeforces Round 618 (Div. 1)

A. Anu Has a Function

思路：

我们把每个二进制位上的 1 1 1 看作是集合的不同的元素，二进制的位运算（按位与，按位或，按位异或）其实可以看作是集合上的与或异或。

这个题 两个集合先或，再完全减去其中一个集合的元素，这正好就相当于两个集合的差集。不妨设 S ( a ) S(a) S(a) 表示 a a a 含有的所有二进制 1 1 1 的集合。而 f ( f ( … f ( f ( a 1 , a 2 ) , a 3 ) , … a n − 1 ) , a n ) f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n) f(f(…f(f(a1​,a2​),a3​),…an−1​),an​) 这个东西看似复杂，其实就是第一个集合不断减去后面的集合，即 S ( a 1 ) − S ( a 2 ) − S ( a 3 ) − ⋯ − S ( a n ) S(a_1)-S(a_2)-S(a_3)-\dots-S(a_n) S(a1​)−S(a2​)−S(a3​)−⋯−S(an​)。

所以 a 1 a_1 a1​ 为 1 1 1 且 a 2 ∼ n a_{2\sim n} a2∼n​ 为 0 0 0 的二进制位最后才能是 1 1 1，其他位置都会被置为 0 0 0。我们只要枚举这个 “ a 1 a_1 a1​”，然后快速算出其余的数的或的和，就有办法算出结果是多少。算其余的数的或的和可以用前后缀和来预处理。

code：

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+5;

int n,a[maxn];
int pre[maxn],suf[maxn];

int main(){
	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>=1;i--)suf[i]=suf[i+1]|a[i];
	
	int idx,ans=-1;
	for(int i=1,x;i<=n;i++){
		x=(((1<<30)-1)^(pre[i-1]|suf[i+1]))&a[i];
		if(x>ans){
			ans=x;
			idx=i;
		}
	}
	cout<<a[idx]<<" ";
	for(int i=1;i<=n;i++)
		if(i!=idx)
			cout<<a[i]<<" ";
	return 0;
}