[zjoi2003]密码机

一台密码机按照以下的方式产生密码：首先往机器中输入一系列数，然后取出其中一部分数，将它们异或以后得到一个新数作为密码。现在请你模拟这样一台密码机的运行情况，用户通过输入控制命令来产生密码。
密码机中存放了一个数列，初始时为空。密码机的控制命令共有3种：
ADD <Number>
把<Number>加入到数列的最后。
REMOVE <Number>
在数列中找出第一个等于<Number>的数，把它从数列中删除。
XOR BETWEEN <Number1> AND <Number2>
对于数列中所有大于等于<Number1>并且小于等于<Number2>的数依次进行异或，输出最后结果作为密码。如果只有一个数满足条件，输出这个数。如果没有任何数满足条件，输出0。
你可以假设用户不会REMOVE一个不存在于数列中的数，并且所有输入的数都不超过20000

这题有点智商题的感觉；

xor运算符满足一个性质，就是一个数连续xor一个数两次，这个数不变；

可以利用树状数组，每次add或remove直接xor就行，find的时候找到right的xor结果，left的xor结果，两个再xor，这样重复的就会直接消掉；

实现很简单，想通就行了；

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cstdlib>

 #include<ctime>

 #include<vector>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define LL long long

 const int n=;

 int c[n];

 int lowbit(int x){return x&-x;}

 void add(int x,int y){while(x<=n){c[x]^=y;x+=lowbit(x);}}

 int find(int x){int ans=;while(x>){ans^=c[x];x-=lowbit(x);}return ans;}

 int read(){

     int x=;bool flag=;char ch=getchar();

     while(ch<''||ch>''){ch=getchar();if(ch=='-')flag=;}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return flag?-x:x;

 }

 void init(){

     char s[];

     while(scanf("%s",s)!=EOF){

         if(s[]=='A'||s[]=='R'){

             int x=read();

             add(x,x);

         }

         if(s[]=='X'){

             int x=read(),y=read();

             if(x>y){

                 printf("0\n");

                 continue;

             }

             int p=find(x-),q=find(y);

             cout<<(p^q)<<endl;

         }

     }

 }

 int main(){

     init();

 }

巴特西

[zjoi2003]密码机

最新文章

热门文章