题目链接
题意:
给出一个长度为n的非负整数序列A，每次操作要求把整个序列异或上x后求mex。 n,m,Ai<=300000
思路:
首先求异或最大值最小值我们知道可以用01trie,每次insert是log,查询也是log级别的。
那么这个问题让我们求未出现的最小的自然数,我们来想想怎么转化.
首先我们知道 x^a[i]^z = a[i] ^（x^z）.也就是说我们并不用每次真的去改变数组a的值,我们只需要把维护一个x的异或前缀和在异或a
数列得到的结果是相同的.
我们要求数列异或后的未出现的自然数的最小值,我们知道z^x=y，如果x和y确定那么z也就确定了,既然我们现在要求不在数列的y,那么
我们可以想到 y^x =z ，这个z一定也不再数列中,如果在数列中的话得到的y就不是mex.
那么我们就将所有不在数列中的值加入01trie,变成一个排序二叉树,问题就转化成了在树中找到最小的z使得z^x =y ,y最小.那么问题又转
化成了贪心问题,要异或最小,那么z的每一位都要尽可能的和x的每一位相等,如果在01trie不存在这样的结点在找另一个.一直这样找到叶子结点
就是最小的了。对了,记得对每一个数的结尾记录他的对应的数是哪一个.
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> using namespace std; typedef long long ll; const int mod=1e9+7; const int maxn=6e6+10; const int N=3e5+10; int trie[maxn][5]; int num[maxn]; int vis[2*N]; int pos=1; int now; char str[25]; void insert(char s[],int val) { int c=0; int len = strlen(s); for(int i=0;i < len;i++) { int bt=s[i]-'0'; if(trie[c][bt]==0) { num[pos] = 0; memset(trie[pos],0,sizeof trie[pos]); trie[c][bt]=pos++; } c=trie[c][bt]; } num[c] = val; return ; } int find(char s[]) { int c=0; int len = strlen(s); for(int i=0;i < len;i++) { int bt=s[i]-'0'; if(trie[c][bt]) c=trie[c][bt]; else c=trie[c][1-bt]; } return num[c]; } void change(int i) { str[21]='\0'; int tmp = i; for(int j = 20;j >= 0;j--) { if(tmp) { str[j] = tmp%2 +'0'; tmp /= 2; } else str[j] = '0'; } } int main(){ int n,m; cin>>n>>m; for(int i = 1;i <= n;i++) { int a; scanf("%d",&a); if(vis[a]==0) vis[a] = 1; } for(int i = 0;i <= 600000 ;i++) { if(vis[i] == 0) { change(i); insert(str,i); } } now = 0; while(m--) { int x; scanf("%d",&x); now ^= x; x = now; change(x); printf("%d\n",find(str)^now); } return 0; } Marcus-Bao 认证博客专家 推荐系统 ACM算法竞赛 机器学习 本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
