AcWing 1414. 牛异或 C++ 现学现做
原题链接
中等
作者:
小卒无名
,
2021-01-30 12:50:13
,
所有人可见
,
阅读 862
#include <iostream>
using namespace std;
const int N = 1<<22;//最大
struct node
{
int son[2];//因为只有0 1,这里是保存子节点的下标的
int id;//当前节点代表的数
node(){
son[0] = son[1] = 0;
id = 0;
}
}a[N];
int t = 0;//a数组下标
int Find(int x)//找到能与x的最大异或数
{
int p = 0;
for(int i=20;i >= 0;i--)
{
int y = ((x>>i)&1);
if(a[p].son[!y]) p = a[p].son[!y];//贪心,如果当前位置取与原数相反,那么异或会是最大
else p = a[p].son[y];//没有就只能取这个咯
}
return a[p].id;//返回数组下标(当前字典树01串数字转化为10进制后的题目输入的数)
}
void Insert(int x,int idx)//插入的数,插入的是第几个数字
{
int p = 0;
for(int i=20;i>=0;i--)
{
int y = ((x>>i)&1);
if(!a[p].son[y])//说明不存在
a[p].son[y] = ++t;
p = a[p].son[y];
}
a[p].id = idx;
}
int sum[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
sum[i] = sum[i-1]^x;//求前缀异或和
}
int ans = 0,le,ri;
le = ri = 1;
for(int i=1;i<=n;i++)
{
Insert(sum[i-1],i-1);
int id = Find(sum[i]);
if((sum[id]^sum[i]) > ans)
ans = (sum[id]^sum[i]),le = id+1,ri = i;
}
printf("%d %d %d\n",ans,le,ri);
return 0;
}