求两段不相交子序列,他们异或和的 和最大
#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