526互联

Codeforces Round 882 (Div. 2) C. Vampiric Powers, anyone?

发布时间 2023-07-08 11:11:50作者: 突破铁皮

由题目观察可得，a[m+1]=a[i]^...a[m],，结合异或的性质a^b^a=b,可得如果在末尾添加一个a[m+1],a[m+1]会和末尾几个抵消掉，求得i~k这一段的异或和，k<m,因此通过该操作实际上我就可以求得所有长度连续区间的异或和，求其最大值，n=1e5+10，如果暴力求解肯定会超时，我们观察发现a[i]的范围为0~2^8,因此异或和最多不超过2^8,因此我们从a[i]方向考虑

根据异或的性质可得sum[i~j]=sum[j]^sum[i]，其中sum的数值为0~2^8,两层循环的话，最多为2^9时间复杂度

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,t;
int a[N];
bool p[N];
void solve(){
	memset(p,0,sizeof p);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int  res=0,sum; 
	for(int i=1;i<=n;i++){//我们枚举每个sum[i]
		if(i>1) sum^=a[i];
		else sum=a[i];
		res=max(sum,res);
		p[sum]=1;
		for(int j=0;j<2<<8;j++){//枚举前面出现过的sum[i]
			if(p[j]){
				res=max(res,sum^j);
			}
		}
	}
	cout<<res<<endl;
	
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
		cin>>t;
		while(t--){
		solve();
	}
}

区间和的范围和元素范围密切相关