CS Course
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 430 Accepted Submission(s): 222
Problem Description
Little A has come to college and majored in Computer and Science.
Today he has learned bit-operations in Algorithm Lessons, and he got a problem as homework.
Here is the problem:
You are giving n non-negative integers , and some queries.
A query only contains a positive integer p, which means you
are asked to answer the result of bit-operations (and, or, xor) of all the integers except .
Today he has learned bit-operations in Algorithm Lessons, and he got a problem as homework.
Here is the problem:
You are giving n non-negative integers , and some queries.
A query only contains a positive integer p, which means you
are asked to answer the result of bit-operations (and, or, xor) of all the integers except .
Input
There are no more than 15 test cases.
Each test case begins with two positive integers n and p
in a line, indicate the number of positive integers and the number of queries.
Then n non-negative integers follows in a line, for each i in range[1,n].
After that there are q positive integers in q lines, for each i in range[1,q].
Each test case begins with two positive integers n and p
in a line, indicate the number of positive integers and the number of queries.
Then n non-negative integers follows in a line, for each i in range[1,n].
After that there are q positive integers in q lines, for each i in range[1,q].
Output
For each query p, output three non-negative integers indicates the result of bit-operations(and, or, xor) of all non-negative integers except in a line.
Sample Input
3 3
1 1 1
1
2
3
Sample Output
1 1 0
1 1 0
1 1 0
Source
Recommend
liuyiding
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6186
题意：从连续的and/or/xor中去掉某一个。。
法一：保存所有元素的某一位bit的和，查找ap有没有因为自己的某一位而改变全部的or/and，如果有，就改回来
法二：三个位运算都有交换率律结合律，所以可以保存前缀连续and/or和后缀连续and/or，注except第一个或者最后一个元素的时候要特判一下。
另外，因为异或具有性质：a^b^b = a ，所以可以将直接将1~n的异或再异或要去掉的ap即可
法二代码
#include<cstdio>
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = 100000 + 100;
int n,q;
int a[maxn];
int andl[maxn], andr[maxn], orl[maxn], orr[maxn], xorl[maxn], xorr[maxn];
int main(){
while(~scanf("%d %d", &n, &q)){
//memset(a,-1,sizeof(a));
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
andl[1] = orl[1] = xorl[1] = a[1];
andr[n] = orr[n] = a[n];
for(int i = 2; i <= n; i++){
andl[i] =andl[i-1]&a[i];
orl[i] = orl[i-1]|a[i];
xorl[i] = xorl[i-1]^a[i] ;
}
for(int i = n-1; i >= 1; i--){
andr[i] = andr[i+1]&a[i];
orr[i] = orr[i+1]|a[i];
}
for(int i = 0; i < q; i++){
int pp;
scanf("%d", &pp);
if(pp==1)printf("%d %d %d
", andr[2], orr[2], xorl[n]^a[pp]);
else if(pp==n)printf("%d %d %d
", andl[pp-1], orl[pp-1], xorl[n]^a[pp]);
else printf("%d %d %d
", andl[pp-1]&andr[pp+1], orl[pp-1]|orr[pp+1], xorl[n]^a[pp]);
}
}
return 0;
}