本帖最后由 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;
- }
| 
楼主
