• 题意
    • 给出一个数组,每次操作将整个数组亦或一个数x,问得到的数组的结果中的mex.mex表示为自然数中第一个没有出现过的非负整数
  • 题解
    • x^y1^y2…yn=x^(y1^y2…yn),所以不需要将整个数组改变,只需要累计异或x即可
    • 一个数组异或一个数,未出现的最小非负整数必定是数组中未出现的数异或这个数后得到的最小非负整数
  • 代码
    • //#include<bits/stdc++.h>
      #include<algorithm>
      #include <iostream>
      #include  <cstdlib>
      #include  <cstring>
      #include  <cassert>
      #include   <cstdio>
      #include   <vector>
      #include   <string>
      #include    <cmath>
      #include    <queue>
      #include    <stack>
      #include      <set>
      #include      <map>
      using namespace std;
      #define P(a,b,c) make_pair(a,make_pair(b,c))
      #define rep(i,a,n) for (int i=a;i<=n;i++)
      #define per(i,a,n) for (int i=n;i>=a;i--)
      #define CLR(vis) memset(vis,0,sizeof(vis))
      #define MST(vis,pos) memset(vis,pos,sizeof(vis))
      #define pb push_back
      #define mp make_pair
      #define all(x) (x).begin(),(x).end()
      #define fi first
      #define se second
      #define SZ(x) ((int)(x).size())
      typedef pair<int,pair<int,int> >pii;
      typedef long long ll;
      typedef unsigned long long ull;
      const ll mod = 1000000007;
      const int INF = 0x3f3f3f3f;
      ll gcd(ll a, ll b) {
      	return b ? gcd(b, a%b) : a;
      }
      template <class T>
      inline bool scan_d(T &ret) {
      	char c;
      	int sgn;
      	if(c=getchar(),c==EOF) return 0; //EOF
      	while(c!='?'&&(c<'0'||c>'9')) c=getchar();
      	sgn=(c=='?')?-1:1;
      	ret=(c=='?')?0:(c-'0');
      	while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
      	ret*=sgn;
      	return 1;
      }
      inline void outt(int x) {
      	if(x>9) outt(x/10);
      	putchar(x%10+'0');
      }
      template<class T>inline void gmax(T &A, T B){
      	(A<B)&&(A=B);//if(B>A)A=B;
      }
      template<class T>inline void gmin(T &A, T B){
      	(A>B)&&(A=B);//if(B<A)A=B;
      }
      const int maxn=3e5+10;
      int a[maxn];
      int Base[40];
      int vis[maxn*2];
      int trie[maxn*40][2],tot=0;
      
      void into_base(int x) {
      	//cout<<x<<endl;
      	int cnt=33;
      	CLR(Base);
      	while(x) {
      		Base[--cnt]=x%2;
      		x/=2;
      	}
      //	rep(i,1,32){
      //		cout<<Base[i];
      //	}
      //	cout<<endl;
      }
      
      void insert() {
      	int p=0;
      	rep(i,1,32) {
      		int ch=Base[i];
      		if(trie[p][ch]==0)trie[p][ch]=++tot;
      		p=trie[p][ch];
      	}
      }
      int search() {
      	int p=0;
      	int cnt=0;
      	rep(i,1,32) {
      		cnt*=2;
      		int ch=Base[i];
      		if(trie[p][ch]==0) {
      			ch^=1;
      			++cnt;
      			//cout<<i<<" "<<cnt<<endl;
      		}
      		p=trie[p][ch];
      	}
      	return cnt;
      }
      int main() {
      	int n;
      	while(~scanf("%d", &n)) {
      		tot=0;
      		CLR(trie);
      		CLR(vis);
      		int m;
      		scanf("%d", &m);
      		rep(i,1,n){
      			scanf("%d", &a[i]);
      			vis[a[i]]=1;
      		}
      		rep(i,0,600001){
      			if(!vis[i]){
      				into_base(i);
      				insert();
      			}
      		}
      		int sum=0;
      		int x;
      		while(m--){
      			scanf("%d", &x);
      			sum^=x;
      			into_base(sum);
      			printf("%d\n",search());
      		}
      	}
      
      	return 0;
      }

发表评论

邮箱地址不会被公开。 必填项已用*标注