首页 > 代码库 > ZJOI—— 密码机（2003）
ZJOI—— 密码机（2003）
ZJOI2003密码机，没找到可以测试的网站，就只过了样例~~
题目描述
一台密码机按照以下的方式产生密码：首先往机器中输入一系列数，然后取出其中一部分数，将它们异或以后得到一个新数作为密码。现在请你模拟这样一台密码机的运行情况，用户通过输入控制命令来产生密码。密码机中存放了一个数列，初始时为空。密码机的控制命令共有3种：
ADD < Number >
把< Number >到数列的最后。
REMOVE < Number >
在数列中找出第一个等于< Number >的数，把它从数列中删除。
XOR BETWEEN < Number1 > AND < Number2 >
对于数列中所有大于等于< Number1 >并且小于等于< Number2 >的数依次进行异或，输出最后结果作为密码。如果只有一个数满足条件，输出这个数。如果没有任何数满足条件，输出0。
你可以假设用户不会REMOVE一个不存在于数列中的数，并且所有输入的数都不超过20000。
输入格式
包括了一系列的控制命令。每个控制命令占据单独一行。输入文件中没有多余的空行。文件不超过60000行。
输出格式
对于每个XOR命令，依次在输出一行包括你的密码机所产生的密码。输出文件中不应该包含任何的多余字符
样例数据
样例输入
ADD 5
ADD 6
XOR BETWEEN 1 AND 10
REMOVE 5
XOR BETWEEN 6 AND 8
样例输出
3
6
由于a^b^a==b,所以从题目中可以看出，添加和删除都是^下一num
然后用树状数组维护num的情况就可以了
1 #include <algorithm> 2 #include <iostream> 3 #include <string> 4 #include <cstdio> 5 6 #define lowbit(x) (x&(-x)) 7 8 using namespace std; 9 10 const int N=20000+15;11 string s,s1,s2;12 int num,num1,num2,t[N];13 14 void insert(int x)15 {16 for(;x<=N;x+=lowbit(x)) t[x]^=num;17 }18 19 int query(int x)20 {21 int ans=0;22 for(;x;x-=lowbit(x)) ans^=t[x];23 return ans;24 }25 26 int main()27 {28 while(cin>>s)29 {30 if(s=="ADD"||s=="REMOVE")31 scanf("%d",&num), insert(num);32 else33 {34 cin>>s1>>num1>>s2>>num2;35 if(num1>num2) printf("0\n");36 else printf("%d\n",query(num2)^query(num1-1));37 }38 }39 return 0;40 }
ZJOI—— 密码机（2003）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。