qduoj 帅气的HYC的珍珠(前缀和+思维)

第1行一个整数T，表示有T组测试数据。(T<=15)
第2行一个整数N， 表示有N棵草。(1<=N<=1000)
第3行有N个整数0或者1，中间用空格隔开， 1代表第i课草有露珠，0代表第i棵草没有露珠。
第4行是一个整数Q， 代表查询的次数。(1<=Q<=100000)
下面第（4+Q）行每行两个整数L， R。 代表查询的区间［L， R］；（1<=L<=R<=N）

对于每组查询输出一行。

1
4
1 1 0 1
3
1 2
2 3
1 4

1
0
1

思路：这个题目查询是和更新分开的，因此可以事先建立一个前缀和数组，sum[i] 表示除当前位置外之前的珍珠的个数，对于每个询问，找到左右就行了。

#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <cmath>
#include <stack>
#include <climits>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;int sum[2000];
int a[2000];
int m,n;
int getSum(int i)  // 获得右端点的 sum
{if(a[i] == 0){return sum[i];}if(i-1>=1 && a[i-1] == 1)return sum[i]+1;return sum[i];
}int getSum_(int i)   // 获得左端点的sum 值
{if(a[i] == 0)  // 如果该点为0，那么sum【i】是准确的return sum[i];if(i+1<=n && a[i+1] == 1)        // 如果a[i] == a[i+1] == 1;当前珍珠归于右，return sum[i];if(i-1>=1 && a[i-1] == 1)  // 如果 a[i+1] == 0 a[i] == a[i-1] == 1 当前珍珠归左return sum[i]+1;return sum[i]; // 否则当前没珍珠。
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i = 1; i <= n; i++)scanf("%d",&a[i]);int flag = 0;for(int i = 1; i <= n; i++){if(a[i] == 0){if(flag >= 2)sum[i] = sum[i-1] + 1;elsesum[i] = sum[i-1];flag = 0;}else if(flag == 0){flag = 1;sum[i] = sum[i-1];}else{flag++;sum[i] = sum[i-1];}}int q;scanf("%d",&q);for(int i = 0; i < q; i++){int l,r;scanf("%d%d",&l,&r);if(r-l == 0)  // 因为后面的判断多用到 a[i+1] a[i-1] 对于长度为1的先排除。{printf("0\n");continue;}int tmp = getSum(r) - getSum_(l);printf("%d\n",tmp);}}return 0;
}