首页 > 其他分享 >#10051. 「一本通 2.3 例 3」Nikitosh 和异或

#10051. 「一本通 2.3 例 3」Nikitosh 和异或

时间:2023-02-26 21:15:52浏览次数:41  
标签:insert ch int 10051 异或 tot 2.3 find

求两段不相交子序列,他们异或和的 和最大

 

 

#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 const int  N =4e5+4;
 int ch[N*32][2],ans; 
 int tot=1;
 int n,a[N],g[N],f[N];
 
 void insert(int x){
 	int u=1;
 	for(int i=31;i>=0;i--){
 		int c= (x>>i)&1;
 		if(ch[u][c]==0) ch[u][c]=++tot; 
 		u=ch[u][c];
  	}
 }
 int find(int x){
 	int t=0;
 	int u=1;
 	for(int i=31;i>=0;i--){
 		int c= (x>>i)&1;
 		
 		if(ch[u][c^1]){
 			u=ch[u][c^1];  t=t*2+1; 
 		}
 		else{
 			u=ch[u][c]; t=t*2;
 		}
  	}
  	return t;
 }
 signed main(){
 	int i,t;
 	cin>>n ; 
 	tot=1; t=0;
 	insert(0);
 	for(i=1;i<=n;i++){
 		cin>>a[i];
 		t^=a[i]; 
 		insert(t);
 		f[i]=max(f[i-1],find(t));
	 }
	 
	 memset(ch,0,sizeof ch);
	 tot=1; t=0;
	 insert(0);
 	for(i=n;i>=1;i--){
 		t^=a[i];
 		 insert(t);
 		 g[i]=max(g[i+1],find(t));
	 }
	 
	 int ans=0;
	for(i=1;i<n;i++){
		ans=max(ans,f[i]+g[i+1]);
	}
	cout<<ans;
 }

 

标签:insert,ch,int,10051,异或,tot,2.3,find
From: https://www.cnblogs.com/towboa/p/17157672.html

相关文章