差分2017-2018 ACM-ICPC Asia East Continent League Final(ECL-Final 2017)(J題)

1474 ワード

http://codeforces.com/gym/101775/problem/J 差分とは、一連の数をそれぞれ前の数に差分することです.たとえば、次のようにします.
1つのシーケンス1 2 5 4 7 3、差分後に1 1 1 3-1 3-4-3を得る
ここで、得られた差分シーケンスの最初の数は、元の最初の数と同じであることに注意する(最初の数マイナス0に相当する)
差分シーケンスは、元のシーケンスよりも最後に1つ多い数(0から最後の数を減らすことに相当)
性質:
1、差分シーケンス接頭辞と元のシーケンスを求める
2、元のシーケンス区間[L,R]の要素を全て+1し、差分シーケンスLで+1,R+1で-1に変換できる
3、性質2によって得られ、元のシーケンスを修正するたびに1つの区間+1が変更されると、差分シーケンスの修正ごとに増加したものと減少したものは同じである.
この問題についてお話しします.
長さ3-5の区間に全部分解できるかどうかを判断したいのですが、区間ごとに要素の大きさが同じです.
1つの0シーケンスで区間操作を行うことに相当し、1つの区間ごとにすべて+1となり、元のシーケンスが得られるかどうか
では、入力された元のシーケンスを差分して得られる差分シーケンスは、0シーケンスを区間操作した結果に相当する
したがって,各区間修正箇所の値を加算し,最終的に0であるか否かを判断するだけでよい.
また注意入力が全て0の場合Yesを出力します
#include 

using namespace std;

const int maxn=2e5+10;
int a[maxn],b[maxn];
int main()
{
    int t;
    int tt=1;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i0) sum+=b[i];
                int j=i+3;
                if(j>n)
                    break;
                if(b[j]<0) sum+=b[j];
                if(sum<0)
                    break;
            }

            if(sum==0)
                printf("Case #%d: Yes
",tt++); else printf("Case #%d: No
",tt++); } } return 0; }