【题意】

给定序列q[1..n]，求任意两数异或的最大值

数据范围：1<=n<=10^5，q[i]为32位非负整数

【分析】Trie用来从高到低保存0和1，然后爆搜：尽可能凑1，不然凑0

【代码】

WOC为什么是多组数据？

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int K=32; const int L=3300000; typedef long long LL; int n,ret[K+10]; LL x,mi[K+10]; int nxt[L][2],tot; inline void do_ret(LL i) { for (int j=K;j+1;j--) i>=mi[j]?ret[j]=1,i-=mi[j]:ret[j]=0; } inline void ins(void) { int now=1; for (int i=K;i+1;i--) { if (!nxt[now][ret[i]]) nxt[now][ret[i]]=++tot; now=nxt[now][ret[i]]; } } inline LL max(LL i,LL j) { return i>j?i:j; } LL DFS(int nn,int nx,int dep) { LL res=0; if (nxt[nn][0]&&nxt[nx][1]) res=max(res,DFS(nxt[nn][0],nxt[nx][1],dep-1)+mi[dep]); if (nxt[nn][1]&&nxt[nx][0]) res=max(res,DFS(nxt[nn][1],nxt[nx][0],dep-1)+mi[dep]); if (res) return res; if (nxt[nn][0]&&nxt[nx][0]) res=max(res,DFS(nxt[nn][0],nxt[nx][0],dep-1)); if (nxt[nn][1]&&nxt[nx][1]) res=max(res,DFS(nxt[nn][1],nxt[nx][1],dep-1)); return res; } int main(void) { mi[0]=1; for (int i=1;i<=K;i++) mi[i]=mi[i-1]*2; for (;~scanf("%d",&n);) { memset(nxt,0,sizeof nxt); tot=1; for (int i=1;i<=n;i++) { scanf("%lld",&x); do_ret(x),ins(); } printf("%lld\n",DFS(1,1,K)); } return 0; }
    
   
  

?

【小结】

(1) 对于位运算的问题，可以通过对于位的分析，常见维护的数据结构有Trie和线段树

(2) 异或的性质：[1] i^j=k --> j^k=i 且 i^k=j [2] i^i=0,i^0=i --> 可以把前缀与后缀互相转化，常见应用在可持久数据结构的查询