CS Course
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3807 Accepted Submission(s): 1412
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 a1,a2,⋯,an, 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 ap.
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.
2≤n,q≤105
Then n non-negative integers a1,a2,⋯,an follows in a line, 0≤ai≤109 for each i in range[1,n].
After that there are q positive integers p1,p2,⋯,pqin q lines, 1≤pi≤n 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 ap in a line.
Sample Input
3 3
1 1 1
1
2
3
Sample Output
1 1 0
1 1 0
1 1 0
时间限制：4000/2000 MS（Java /其他）内存限制：32768/32768 K（Java /其他）
提交总数：3807接受提交：1412
问题描述
Little A上了大学，主修计算机和科学。
如今，他已经在算法课程中学习了位操作，并且在作业方面遇到了问题。
这是问题所在：
您要提供n个非负整数a1，a2，⋯，an和一些查询。
查询仅包含一个正整数p，这意味着您
要求回答除ap以外的所有整数的位运算（和，或xor）的结果。
输入值
测试案例不超过15个。
每个测试用例均以两个正整数n和p开头
在一行中，指示正整数的数量和查询的数量。
2≤n，q≤105
然后，n个非负整数a1，a2，⋯，an排成一行，对于范围[1，n]中的每个i，0≤ai≤109。
之后，在q行中有q个正整数p1，p2，⋯，pqin，范围[1，q]中的每个i1≤pi≤n。
输出量
对于每个查询p，输出三个非负整数表示一行中除ap之外的所有非负整数的位运算（和或xor）的结果。
样本输入
3 3
1 1 1
1
2
3
样本输出
1 1 0
1 1 0
1 1 0
题目链接
WFU寒假训练<十一>
这道是杭电OJ中的题目 依次输出从除ap外的所有非负整数的位运算（和或xor）的结果(我做的时候暴力TLE了好几次)
本题思路：定义6个数组，预处理前缀和和后缀和，输出的时候注意等于1和等于n的情况，其他情况根据前缀和和后缀和输出答案即可
ac代码：
#include <bits/stdc++.h>
using namespace std;
const int _max=1e5+50;
int num[_max];
int an[_max],huo[_max],xo[_max];//前缀和
int rean[_max],rehuo[_max],rexo[_max];//后缀和
int n,q;
int main()
{
ios::sync_with_stdio(false);
void solve();
while(cin>>n>>q)//不多组输入会WA
{
for(int i=1;i<=n;i++)
cin>>num[i];
solve();//预处理函数
for(int i=1;i<=q;i++)
{
int s;
cin>>s;
if(s==1)//特殊情况
cout<<rean[s+1]<<" "<<rehuo[s+1]<<" "<<rexo[s+1]<<endl;
else if(s==n)//特殊情况
cout<<an[s-1]<<" "<<huo[s-1]<<" "<<xo[s-1]<<endl;
else
cout<<(an[s-1]&rean[s+1])<<" "<<(huo[s-1]|rehuo[s+1])<<" "<<(xo[s-1]^rexo[s+1])<<endl;
}
}
return 0;
}
void solve()
{
an[1]=huo[1]=xo[1]=num[1];
for(int i=2;i<=n;i++)
{
an[i]=an[i-1]&num[i];
huo[i]=huo[i-1]|num[i];
xo[i]=xo[i-1]^num[i];
}
rean[n]=rehuo[n]=rexo[n]=num[n];
for(int i=n-1;i>=1;i--)
{
rean[i]=rean[i+1]&num[i];
rehuo[i]=rehuo[i+1]|num[i];
rexo[i]=rexo[i+1]^num[i];
}
}