本帖最后由 michael_llh 于 2016-12-24 21:11 编辑
Binary Queries Some problems appear hard though they are very easy. Today Aakash is stuck in a range query problem. He has been given an array with only numbers 0 and 1. There are two types of queries - 0 L R : Check whether the number formed from the array elements L to R is even or odd and print EVEN or ODD respectively. Number formation is the binary number from the bits status in the array L to R 1 X : Flip the Xth bit in the array Input
First line contains a number N and Q as input. Next line contains N space separated 0 or 1. Next Q lines contain description of each query Output
Output for only query type 0 L R whether the number in range L to R is "EVEN" or "ODD" (without quotes). Constraints
1≤ N ≤ 10^6
1≤ L ≤ R ≤ 10^6
1≤ Q ≤ 10^6
1≤ X ≤ N sample input: 5 2 1 0 1 1 0 1 2 0 1 4 sample output: ODD
Comes from:
题目解析： 这个题目其实是这个意思： 有两种类型的queries： 1. 0 L R：这个模式的是说以0开头，这个数字是从左边第L开始到右边第R结束的数字组成，同时是一个二进制数，比如说110，那么对应这个数就是6，我们要判断这个二进制数是奇数还是偶数 2.1 X：这种模式下的就是要翻转第X个元素的值，比如说0变成1,1变成0这样。 输入格式： 第一行会有两个数字，N和Q，那么对于N表示的是下一行有多少个0和1构成的二进制数，Q则是表示接下来有几行来说明这个query。简单说，这几行就是query判断的规则。 输出格式： 如果是满足query第一种就输出“EVEN”或者“ODD” 下面就是数据约束说明了，这里不再复制了。 其实分析好题目后就很简单了，参考代码如下：
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int N=0;
int Q=0;
int sum=0;
int L =0;
int R =0;
int check = 0;
int x=0;
cin >> N >> Q;
char* array = new char[N];
if(N<0 || Q < 0)
return -1;
else if(N > 1){
for(int i=0; i<N; i++){
cin >> array[i];
}
while (Q--) {
cin >> check;
if (check) {
cin >> x;
array[x - 1] = array[x - 1] ^ 1;
}
else {
cin >> L >> R;
cout << (('0' == array[R - 1]) ? "EVEN" : "ODD") << endl;
}
}
}
return 0;
}
| 
楼主
标题置顶
标题高亮
