点击打开链接
题意给出n个数和m次询问 n,m<=1e5 每次询问给出数S 问n个数中与S异或的最大值时多少? 直接暴力O(nm),显然超时,由于异或和要最大 S从高位到低位的1尽量保持为1,0尽量变为1 把n个数写成2进制插入Trie中,S从高位开始尽量找不同即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+20; int ch[32*N][2],sz; ll val[32*N];//结点i结尾的数 void init() { memset(ch[0],0,sizeof(ch[0])); sz=1; } void insert(ll a) { int u=0; for(int i=32;i>=0;i--) { int c=(a>>i)&1; //二进制第i位是否为1 if(!ch[u][c]) { memset(ch[sz],0,sizeof(ch[sz])); val[sz]=0; ch[u][c]=sz++; } u=ch[u][c]; } val[u]=a; } ll query(ll x) { int u=0; for(int i=32;i>=0;i--) { int c=(x>>i)&1; //从高位起每位尽量找不同的异或 if(ch[u][c^1]) u=ch[u][c^1]; else u=ch[u][c];// } return val[u]; } int main() { int t; cin>>t; for(int cas=1;cas<=t;cas++) { init(); ll n,m,x; cin>>n>>m; for(int i=1;i<=n;i++) { scanf("%I64d",&x); insert(x); } printf("Case #%d:\n",cas); for(int i=1;i<=m;i++) { scanf("%I64d",&x); ll y=query(x); printf("%I64d\n",y); } } return 0; }
