调了好久，对着好多代码对了老半天，最终结果是数组开小了。以前学Trie的时候学的是用结构体和指针的，对这种数组模拟的还真拿捏不好。 参考：http://blog.csdn.net/mengxiang000000/article/details/77718605 涨知识了，有学到了Trie的新用法。 题意就是给你n个数，询问m次，每次询问给你一个x，让你求这n个数异或x之后，查询这n个数字的mex，mex就是自然数中第一个没有出现过的数。当初看到这题，脑袋闪过的就是暴力过不去，除了暴力，别的还想不到。 思路：假设现在有0-(k-1)这k个不同的数字，从中抽出来n个数字作为输入的数字。这n个数字分别对x进行异或运算，得到了一个新的序列，这个序列的mex就是那(k-n)个数字中异或x的最小值。因为这k个数字，从中抽出来n个异或x，异或后的新序列中没出现过的数字肯定是那(k-n)个数字对x异或的值。
#include <bits/stdc++.h> using namespace std; const int N = 19; bool mark[1<<N]; struct Trie { int next[(1<<N)*20][2]; int sz; void init() { memset(next,-1,sizeof(next)); sz = 0; } void insert(int num) { int cur = 0; for(int i = N-1; i >= 0; --i) { int t = (num>>i)&1; if(next[cur][t] == -1) next[cur][t] = ++sz; cur = next[cur][t]; } } int query(int num) { int ret = 0; int cur = 0; for(int i = N-1; i >= 0; --i) { int t = (num>>i)&1; if(next[cur][t] != -1) { cur = next[cur][t]; ret |= t<<i; } else { t = !t; cur = next[cur][t]; ret |= t<<i; } } return ret; } }; Trie t; int main() { t.init(); int n,m,num; scanf("%d %d",&n,&m); for(int i = 0; i < n; ++i) { scanf("%d",&num); mark[num] = true; } for(int i = 0; i < (1<<N); ++i) { if(!mark[i]) t.insert(i); } int q = 0; while(m--) { scanf("%d",&num); q ^= num; printf("%d\n",t.query(q)^q); } return 0; }