题解 P6180 【[USACO15DEC]Breed Counting S】

· · 题解

原题传送门。在我的博客中食用更佳。

题意概括：

先输入两个数 N，Q，分别表示牛个数和询问个数。

接下来先输入每只牛的类型，随后再输入 Q 组询问，每组询问是两个数：a 和 b，表示询问这两个牛的编号之间每种牛各有多少只。

要求输出每组询问的结果。记得换行。

思路：前缀和。如何实现呢？

在题中有这样一句话：

每个询问希望求出某个区间内每个品种奶牛的数量。

划重点：区间内。那么我们就可以用三个一位数组 x[i],y[i],z[i]来存储每一种奶牛到第 i 头时的总数量。

这样一来，每次用后面读入牛的编号所对应的个数减去前面读入牛的编号-1所对应的个数即可算出区间和（前缀和）了，即：

x_sum=x[b]-x[a-1],y_sum=y[b]-y[a-1],z_sum=z[b]-z[a-1].

是时候上完整代码了！

#include<bits/stdc++.h>//万能头文件好
#define ll long long//个人习惯
using namespace std;
ll x[100005],y[100005],z[100005];//数组最好开大个5个左右，以防万一
int main(){
    ll n,q,i,a,b;//习惯先把变量放这，数组放上面
    scanf("%lld%lld",&n,&q);//读入N和Q，为了方便都写的n和q.
    for(i=1;i<=n;i++){
        scanf("%lld",&a);//读入a，此时的a用于暂存当前品种 
        x[i]=x[i-1];y[i]=y[i-1];z[i]=z[i-1];
        //把之前的每一种类型的奶牛先加上来，稍稍压行
        switch(a){//判断这只牛的类型
            case 1:
                x[i]++;
                break;
            case 2:
                y[i]++;
                break;
            case 3:
                z[i]++;
                break;
        }//把这只牛加上去
    }
    for(i=1;i<=q;i++){//开始读入询问
        scanf("%lld%lld",&a,&b);//读入题目描述中的a和b.
        printf("%lld %lld %lld\n",x[b]-x[a-1],y[b]-y[a-1],z[b]-z[a-1]);
        //这一步前面有单独分析。
    }
    return 0;//over
}

还是很简单的把。本蒟蒻还不会树状数组（好像有大佬这样做），如有需要请移步他处。

完结撒花~