Gym-101775J-差分（2017-EC-final-J）

这个题过了一年才补QwQ

这个题可以用差分的思想来做，首先来了解一下差分：

差分就是将一串数分别于前一个数做差，例如：

一个序列1 2 5 4 7 3，差分后得到1 1 3 -1 3 -4 -3

这里注意得到的差分序列第一个数和原来的第一个数一样（相当于第一个数减0）

差分序列最后比原序列多一个数（相当于0减最后一个数）

性质：

1、差分序列求前缀和可得原序列

2、将原序列区间[L,R]中的元素全部+1，可以转化操作为差分序列L处+1，R+1处-1

3、按照性质2得到，每次修改原序列一个区间+1，那么每次差分序列修改处增加的和减少的相同

再来说这道题：

我们是想判断能不能全部分解成长度为3-5的区间，每个区间内元素大小一样

那么相当于在一个0序列进行区间操作，每次一个区间内全部+1，是不是能得到原序列

那么将输入的原序列差分后得到的差分序列相当于将0序列进行区间操作完成的结果

所以只需要将每一个区间修改处的值相加，最终判断是否为0即可

还有注意输入全为0时候输出Yes

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+5;
int t,n;
int a[N],b[N];

int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        b[0]=a[0];a[n]=0;//初始化第n+1个数为0
        for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];//进行差分
        int ok=1 ;//因为全为0的时候是Yes，所以初始化为1
        if(b[1]<0 || b[2]<0) ok=0 ;//对一个区间进行+1操作后，修改处必然是左端点处加一个值右端点加一处减一个相同的值，那么必定是差分值先为正值，不然一定构不成原序列
        else{
            long long int sum=0;
            for(int i=0;i<=n;i++){
                if(b[i]>0) sum+=b[i];//将所有修改处的左端点值加起来
                int j=i+3;//长度大于3的都可以拆分成若干个长度为3-5的序列
                if(j>n) break;
                if(b[j]<0) sum+=b[j];//如果是负数，那么一定是某个修改区间的右端点加一处，所以加起来
                if(sum<0) break;//如果端点值为负数一定不能得到原序列
            }
            if(sum!=0) ok=0 ;//最终只有0才表示只有区间修改，才能得到原序列
        }
        printf("Case #%d: %s\n",k,ok==1?"Yes":"No");
    }
    return 0;
}