3163: 蓝桥杯2023年第十四届省赛真题-异或和之差（C++）

暴力求解（40%）：

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N] , s[N] , ans = 0 , sum = 0;
int n;
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i ++) cin>>a[i];
    for(int i = 1;i <= n;i ++) s[i] = s[i-1] ^ a[i],cout<<s[i]<<endl;;
    LL maxx , minn;
    maxx = minn = s[0] ^ s[1];
    for(int i = 1;i <= n;i ++)
    {
        for(int j = i;j <= n;j ++)
        {
            sum = s[i-1] ^ s[j];
            minn = min(minn , sum);
            maxx = max(maxx , sum);
            cout<<sum<<' ';
        }
        cout<<endl;
    }
    ans = maxx - minn;
    cout<<ans<<endl;
    return 0;
}

时间优化

利用trie树的特性寻找异或的最大最小值：

trie树知识点：https://www.acwing.com/blog/content/15077/

一位大佬的代码思路讲解：https://www.bilibili.com/video/BV1ty421z77K/?spm_id_from=333.788&vd_source=5f7e4c928f2ae7a33f99f74c695f9806

最终代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N = 1e6 + 10 ; 
int  n , a[N] ; 
int son[2][N] , idx ; 
int mx[N] , mi[N] ;
void add(int x)
{
    int p = 0 ; 
    for(int i = 20 ; i >= 0 ; i --)
    {
        int u = (x>>i) & 1; //判断x的第i位上是1/0
        if(!son[u][p]) son[u][p] = ++idx;   //若节点不存在，则按照当前位置上的数是多少来构造树
        p = son[u][p];  //指向构造好的节点准备构造下一位
    }
}
int query_mx(int x)
{//异或值最大则需要尽可能多【不相同】的位数
    int p = 0 , res = 0;
    for(int i = 20;i >= 0;i --)
    {
        int u = (x >> i) & 1;
        if(son[!u][p])  res |= (1 << i);
        else u = !u;
        p = son[!u][p];
    }
    return res;
}
int query_mi(int x)
{//异或值最小则需要尽可能多【相同】的位数
    int p = 0 , res = 0;
    for(int i = 20;i >= 0;i --)
    {
        int u = (x >> i) & 1;
        if(!son[u][p])  //若与当前位相同的节点不存在，则最小异或
        {
            u = !u;
            res |= (1 << i);
        }
        p = son[u][p];
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i ++)  cin>>a[i];
    mx[0] = 0 , mi[0] = 1e9;
    int sum = 0;
    add(sum);
    for(int i = 1;i <= n;i ++)
    {//寻找i左边的异或和最大值和最小值
        sum ^= a[i];    //前缀和
        mx[i] = max(mx[i-1] , query_mx(sum));    //动态规划，i左边的最大值=i-1左边的最大值（不包括i）和以i为右端点（包括i）的最大值
        mi[i] = min(mi[i-1] , query_mi(sum));
        add(sum);    //构造树
    }
    memset(son , 0 , sizeof son) ; 
    idx = 0 ; sum = 0 ;
    int ans = 0 , mx2 = 0 , mi2 = 2e9; 
    add(sum) ; 
    for(int i = n ; i ; i --)
    {//寻找i右边的异或和最大值和最小值（倒序）
        sum ^= a[i] ; 
        mx2 = max(mx2 , query_mx(sum)) ; //同上
        mi2 = min(mi2 , query_mi(sum)) ; 
        //取（ans ， 右最大-左最小 ， 左最大-右最小）的最大值
        ans = max({ans , mx[i - 1] - mi2 , mx2 - mi[i - 1]}) ; 
        add(sum) ; 
    }
    cout<<ans<<endl;
    return 0;
}