AcWing 1414. 牛异或
原题链接
中等
作者:
谷心
,
2021-03-27 12:30:04
,
所有人可见
,
阅读 237
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
//超时
// int n;
// int s[N];
// int main()
// {
// cin >> n;
// for(int i = 1; i <= n; i++)
// {
// scanf("%d",&s[i]);
// s[i] ^= s[i-1]; // 前缀异或和
// }
// // l,r s[r]^s[l-1]
// int res = -1;
// int len = n;
// int resl,resr;
// for(int l=1;l <= n;l++)
// {
// for(int r=l;r<=n;r++)
// {
// if(res <= (s[r]^s[l-1]))
// {
// if(res == (s[r]^s[l-1]))// res相同时 长度更短的更新
// {
// if(len > r-l +1) resl = l,resr = r, len = r-l+1;
// }
// else{ // res 更新 r,l 更新 len 更新
// len = r-l+1;
// resl = l;
// resr = r;
// res = s[r]^s[l-1];
// }
// }
// }
// }
// cout<<res<<" "<<resl<<" "<<resr<<" "<<endl;
// }
//优化 用Trie树
const int M = N*21;
int s[N];
int son[M][2],id[M],idx;
void insert(int x,int k)
{
int p = 0;
for( int i =20; i>= 0; i--) // 尽可能找为1的数
{
int u = x >> i & 1;
if(!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
id[p] = k;
}
int query(int x)
{
int p = 0;
for(int i = 20; i >= 0; i--)
{
int u = x >> i & 1;
if (son[p][!u]) p = son[p][!u]; //找最高位数不同的数
else p = son[p][u];
}
return id[p];
}
int n;
int main()
{
cin >> n;
for(int i = 1; i<= n; i++)
{
scanf("%d",&s[i]);
s[i] ^= s[i-1];
}
int res = -1,a,b;
insert(s[0],0);
for(int i = 1;i<= n; i++)
{
int k = query(s[i]);
int t = s[i] ^ s[k];
if (t > res) res = t, a = k+1, b = i;
insert(s[i],i);
}
printf("%d %d %d\n",res ,a ,b);
}