我过了,但我不理解
  • 板块学术版
  • 楼主underline__jian
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/1/18 19:17
  • 上次更新2023/10/28 12:01:43
查看原帖
我过了,但我不理解
494992
underline__jian楼主2022/1/18 19:17
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=2e7+15;
int n,sz=2,ans,ch[maxn][5],pre[maxn],dp[maxn],suf[maxn],a[maxn];
inline void insert(int str){
	int u=1;
	for(int i=31;i>=0;i--){
		int k=(str>>i)&1;
		if(!ch[u][k]){
			memset(ch[sz],0,sizeof(ch[sz]));
			ch[u][k]=sz++;
		}
		u=ch[u][k];
	}
}
inline int find(int str){
	int u=1,res=0;
	for(int i=31;i>=0;i--){
		int k=(str>>i)&1;
		if(ch[u][k^1]){
			res+=(1<<i);
			u=ch[u][k^1];
		}
		else u=ch[u][k];
	}
	return res;
}
int main(){
	scanf("%d",&n);
	sz=2;
	memset(ch[1],0,sizeof(ch[1]));
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pre[i]=pre[i-1]^a[i];
	}
	for(int i=n;i>=1;i--) suf[i]=suf[i+1]^a[i];
	for(int i=1;i<=n;i++){
		dp[i]=max(dp[i-1],find(pre[i]));
		insert(pre[i]); 
	}
	sz=2;
	memset(ch[1],0,sizeof(ch[1]));
	for(int i=n;i>=1;i--){
		ans=max(ans,dp[i-1]+find(suf[i]));
		insert(suf[i]);
	}
    printf("%d",ans);
	return 0;
}

原题来自LOJ

2022/1/18 19:17
加载中...