1 条题解

  • 0
    @ 2025-4-28 9:06:05

    枚举中点,然后预处理出前缀最大和后缀最大,然后取个max就好

    #include <bits/stdc++.h>
    using namespace std;
    long long R(){
    	long long x = 0, f = 1;
    	char ch = getchar();
    	while(!isdigit(ch)){
    		if(ch == '-') f = -1;
    		ch = getchar();
    	}
    	while(isdigit(ch)){
    		x = (x << 1) + (x << 3) + (ch ^ 48);
    		ch = getchar();
    	}
    	return x * f;
    }
    
    const long long N = 4e5 + 10;
    
    long long n;
    
    long long a[N];
    
    long long mx[N], t[N*30][2], cnt;
    
    void read(){
    	n = R();
    	for(long long i = 1;i <= n; i++) a[i] = R();
    }
    
    void insert(long long x){
    	long long u = 0;
    	for(long long i = 32;i >= 0; i--){
    		long long w = ((x >> i) & 1);
    		if(!t[u][w]) t[u][w] = ++cnt;
    		u = t[u][w];
    	}
    	return ;
    }
    
    long long qry(long long x){
    	long long u = 0;
    	long long ans = 0;
    	for(long long i = 32;i >= 0; i--){
    		long long w = ((x >> i) & 1);
    		if(t[u][(w^1)]){
    			ans += (1<<i);
    			u = t[u][(w^1)];
    		}
    		else{
    			u = t[u][w];
    		}
    	}
    	return ans;
    }
    
    void clear(){
    	for(long long i = 0;i <= cnt; i++){
    		t[i][1] = t[i][0] = 0;
    	}
    	cnt = 0;
    }
    
    void compute(){
    	long long s = 0, l = 0, r = 0; 
    	for(long long i = 0;i <= n; i++){
    		s = (s ^ a[i]);
    		insert(s);
    		l = max(l,qry(s)) ;
    		mx[i] = l;
    	}
    	clear();
    	s = 0;
    	long long ans = 0;
    	for(long long i = n + 1;i >= 1; i--){
    		s = (s ^ a[i]);
    		insert(s);
    		r = max(r,qry(s));
    		ans = max(ans,r+mx[i-1]);
    	}
    	cout << ans;
    }
    int main(){
    //	freopen("最大和ex.in","r",stdin);
    //	freopen("最大和ex.out","w",stdout);
    	read();
    	compute();
    	return 0;
    }
    
    
    • 1

    信息

    ID
    186
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    45
    已通过
    13
    上传者