XSY5053 数（number）

真不会线性基。

题目大意

黑板上有 $n$ 个非负整数，每次操作你可以擦掉黑板上的两个数字并将他们的异或和写在黑板上。

这样未免太无聊了，你决定加一个操作：在任意时刻，你可以选择黑板上任意一个数字使其+1，但是这个操作最多只能进行1次，求黑板上只剩一个数的时候这个数最大可以是多少。

$n\le 10^6,a\le 2^{60}$。

题解

如果没有+1操作那么最后剩下的数字肯定是所有数字的异或和。

对于一个数字+1操作，用2进制表示就是删掉结尾一段连续的1并把前面的一个0替换成1。最后的结果只与+1操作时那个数结尾有多少个连续的1有关，可以理解为在原异或和的基础上再异或一个 $2^k-1$。

考虑枚举结尾1的个数，判断是否能异或出这样一个数，然后判断最大值即可。

题解就这么写的，也是我赛时花半小时想到的。也就是说我半小时已经把这题的解法想到了。那么为什么没有写出来呢。因为题解曰：“这个可以用线性基来解决。”然而我不会线性基！！！更讽刺的是两天前我刚时隔3年写了一道线性基的题！！！然后赛时猜到了可能要用线性基但就是想不到具体怎么搞！！！

后来知道其实很笨。从低到高位加入线性基，询问的时候每一位判一下需不需要异或即可。

dbq我错了我太菜了我痛定思痛我从今天起一定好好学线性基呜呜呜呜呜。

Code

#include<bits/stdc++.h>
using namespace std;

const int N=60+5,M=1e6+5;
typedef long long ll;

int n;
ll ans,sum,a[M],p[N];

void add(ll x){
	for(int i=0;i<=60;i++){
		if(!((x>>i)&1)) continue;
		if(!p[i]){
			p[i]=x;
			return;
		}
		x^=p[i];
	}
}

void solve(){
	ll res=0;
	for(int i=0;i<=60;i++){
		if(p[i]){
			ans=max(ans,sum^((1ll<<i+1)-1));
			if(!((res>>i)&1)) res^=p[i];
		}
		else if(!((res>>i)&1)){
			ans=max(ans,sum^((1ll<<i+1)-1));
			break;
		}
	}
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum^=a[i];
		add(a[i]);
	}
	ans=sum+1;
	solve();
	printf("%lld",ans);
	return 0;
}