题意:
给一个集合,多次询问,每次给一个k,问你集合和k异或结果最大的哪个
题解:
经典的01字典树问题,学习一哈.
把一个数字看成32位的01串,然后查找异或的时候不断的沿着^为1的路向下走即可
#include <bits/stdc++.h>
#define endl '\n'
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=1e5+10,maxm=2e6+10;
int casn,n,m,k,num[maxn];
struct Trie{
int next[maxn*32][2],size;
ll val[maxn*32];
void init(){
size=0;
memset(next,0,sizeof next);
memset(val,0,sizeof val);
}
void insert(ll x){
int cur=0;
for(int i=32;i>=0;i--){
int k=(x>>i)&1;
if(!next[cur][k]) next[cur][k]=++size;
cur=next[cur][k];
}
val[cur]=x;
}
ll find(ll x){
int cur=0;
for(int i=32;i>=0;i--){
int k=(x>>i)&1;
if(next[cur][k^1])cur=next[cur][k^1];
else cur=next[cur][k];
}
return val[cur];
}
}trie;
string s[maxn]; int main() {
IO;
cin>>casn;
int __=0;
while(casn--){
cin>>n>>m;
trie.init();
cout<<"Case #"<<++__<<":"<<endl;
while(n--){
ll x;
cin>>x;
trie.insert(x);
}
while(m--){
ll x;
cin>>x;
cout<<trie.find(x)<<endl;
}
}
return 0;
}
acdream 1063 代码
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=1e5+10,maxm=2e6+10;
int casn,n,m,k,num[maxn];
struct Trie{
int next[maxn*32][2],size;
ll val[maxn*32];
void init(){
size=0;
memset(next,0,sizeof next);
memset(val,0,sizeof val);
}
void insert(ll x){
int cur=0;
for(int i=32;i>=0;i--){
int k=(x>>i)&1;
if(!next[cur][k]) next[cur][k]=++size;
cur=next[cur][k];
}
val[cur]=x;
}
ll find(ll x,bool flag){
int cur=0;
for(int i=32;i>=0;i--){
int k=(x>>i)&1;
if(flag){
if(next[cur][k^1]) cur=next[cur][k^1];
else cur=next[cur][k];
}else {
if(next[cur][k])cur=next[cur][k];
else cur=next[cur][k^1];
}
}
return val[cur];
}
}trie; int main() {
IO;
cin>>casn;
while(casn--){
cin>>n;
trie.init();
while(n--){
ll x;
string s;
cin>>s>>x;
if(s=="insert") trie.insert(x);
else if(s=="qmin") cout<<(x^trie.find(x,0))<<endl;
else cout<<(x^trie.find(x,1))<<endl;
}
}
return 0;
}