有关昨天cf div2 的d题,表示完全不会啊,一搜发现是个叫01字典树的东西,然后就去看了一下,然后发现完全看不懂,很艰难的做了个”模版题” T_T. 有几个理解的要点. 每个节点记录下一个节点的方式,这里不是指针型,是数组模拟(不知道为什么,好像数组模拟会难理解一点,所以大家都倾向于使用这种),这里不像二叉树 2x,2x+1,而是rt,rt++,等于是一个线性的. 而且我们的query,不一定是能找到完美匹配的,而是找到 最好的.
/* xzppp */ #include <iostream> #include <vector> #include <cstdio> #include <string.h> #include <algorithm> #include <queue> #include <map> #include <string> #include <cmath> #include <bitset> using namespace std; #define FFF freopen("in.txt","r",stdin);freopen("out.txt","w",stdout); #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define MP make_pair #define PB push_back typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int > pii; const int MAXN = 1e5+17; const int MAXM = 20; const int MAXV = 1001+17; const int INF = 0x7fffffff; const int MOD = 1e9+7; int dt[32*MAXN][2],tail[32*MAXN],rt,a[MAXN]; void insert(int num,int id) { int cur = 0; for (int i = 31; i > -1 ; --i) { if(!dt[cur][num>>i&1]) dt[cur][num>>i&1] = rt++; cur = dt[cur][num>>i&1]; } tail[cur] = id; } int query(int num) { int cur = 0; for (int i = 31; i > -1 ; --i) { int need = !(num>>i&1); if(dt[cur][need]) cur = dt[cur][need]; else cur = dt[cur][!need]; } return cur; } int main() { #ifndef ONLINE_JUDGE FFF #endif int t,x=1; cin>>t; while(t--) { printf("Case #%d:\n",x++); memset(dt, 0, sizeof(dt)); memset(tail, 0, sizeof(tail)); int n,m; cin>>n>>m; rt = 1; for (int i = 0; i < n; ++i) { scanf("%d",a+i); insert(a[i],i); } for (int i = 0; i < m; ++i) { int temp; scanf("%d",&temp); int need = query(temp); printf("%d\n",a[tail[need]]); } } return 0; }