在这个题目中
Description
Eugeny has array a=a1,a2,...,an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:
Query number i is given as a pair of integers li, ri(1≤li≤ri≤n).
The response to the query will be integer 1, if the elements of array a can be rearranged so as the sum ali+ali+1+...+ari=0, otherwise the response to the query will be integer 0.
Help Eugeny, answer all his queries.
Input
The first line contains integers n and m(1≤n,m≤2·105). The second line contains n integers a1,a2,...,an(ai=-1,1). Next m lines contain Eugene‘s queries. The i-th line contains integers li,ri(1≤li≤ri≤n).
Output
Print m integers — the responses to Eugene‘s queries in the order they occur in the input.
Sample Input
2 3
1 -1
1 1
1 2
2 2
0
1
0
5 5
-1 1 1 1 -1
1 1
2 3
3 5
2 5
1 5
0
1
0
1
0
首先第一步就是要理解题目的意思，然后没有什么其他的技巧了，不过要注意的就是要注意运用位运算，这样可以加快运行速度和运行内存，从这个题目中，我们可以知道利用位运算判断奇偶性的方法了。
贴一下代码吧！
/*171ms,0KB*/
#include<cstdio>
int main()
{
int n, m, a;
int c1 = 0, c2 = 0;
int l, r;
scanf("%d%d", &n, &m);
while (n--)
{
scanf("%d", &a);
if (a > 0)
++c1;
else
++c2;
}
while (m--)
{
scanf("%d%d", &l, &r);
a = r - l + 1;
if (a & 1) //位运算判断奇偶性；
puts("0");
else
{
a >>= 1;//右移表示除以2；
puts(c1 < a || c2 < a ? "0" : "1");
}
}
return 0;
}自己写的代码也贴在下面吧！
#include <stdio.h>
#include <string.h>
#define M 200
//#define min c1<c2?c1:c2
int a[M];
int main(void)
{
memset(a,0,sizeof(a));
int n,m,i,w;
int l,r,c1=0,c2=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==-1)
c1++;
else
c2++;
}
while(m--)
{
scanf("%d %d",&l,&r);
w=r-l+1;
if(w%2==0&&w/2<=c1&&w/2<=c2)
{
puts("1");
}
else
puts("0");
}
return 0;
}没有注意用位运算，不过通过应该是没有问题的。
本文出自 “我的算法笔记” 博客，谢绝转载！
Eugeny and Array,布布扣,bubuko.com
原文：http://liu168ad.blog.51cto.com/7511123/1381453