Acwing 1414.牛异或

大家好，欢迎来到IT知识分享网。

输入样例

5 1 0 5 4 2 

输出样例

6 4 5 

刚开始看到这个题，我是毫无思绪，看了一下题解：

https://www.acwing.com/video/2339/ 

https://www.acwing.com/problem/content/video/145/ 

#include<iostream> #include<algorithm> using namespace std; const int N=31*1e5+10;//因为数据的范围是2的31次方所以二进制有31位 int trie[N][2];//用二维数组把每一个数二进制每一位存储下来 int idx;//用idx来给未分配的标记 void get(int x) { 
    int p=0; for(int i=30;i>=0;i--) { 
    int s=x >> i & 1;//x二进制第i位表示的数字 if(!trie[p][s]) trie[p][s]=++idx;//把他放到trie保存 //保存方式，trie[p][s]里面放着是子节点的下标，真正存放x二进制第i位表示的数字的是列下标 p=trie[p][s];//转移到子节点 } } int f(int y)//寻找与他异或和最大的数 { 
    int p=0,res=0; for(int i=30;i>=0;i--) { 
    int s=y>>i&1; if(trie[p][!s]) { 
   res=res*2+!s;p=trie[p][!s];} else { 
    res=res*2+s;p=trie[p][s];//秦九昭算法 res=res*进制+n(从高位到低位每一位对应的数) } } return res; } int main(void) { 
    int n,t,cot=0; cin>>n; for(int i=1;i<=n;i++) { 
    cin>>t; get(t); int zj=f(t); cot=max(cot,zj^t); } cout<<cot; } 

#include<iostream> #include<algorithm> using namespace std; const int N=21*(1e5+10); int trie[N][2],g[]; int id[N],idx; void insert(int x,int d)//这些操作和求最大异或和一致 { 
    int p=0; for(int i=20;i>=0;i--) { 
    int s=x>>i&1; if(!trie[p][s]) trie[p][s]=++idx; p=trie[p][s]; } id[p]=d; } int quiry(int y) { 
    int p=0; for(int i=20;i>=0;i--) { 
    int s=y>>i&1; if(trie[p][!s]) p=trie[p][!s]; else p=trie[p][s]; } return id[p]; } int main(void) { 
    int n,res=-1,l=1,r=1; cin>>n; for(int i=1;i<=n;i++) { 
    cin>>g[i]; g[i]^=g[i-1]; } insert(g[0],0); //需要注意的细节，要是不填进去的话，如果只有一项，则会找自己也就是本身那么异或为0则不是我 //们想求的答案 for(int i=1;i<=n;i++) { 
    int u=quiry(g[i]); int sum=g[u]^g[i]; if(res<sum) res=sum,l=u+1,r=i; insert(g[i],i); } cout<<res<<" "<<l<<" "<<r; }