差分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を出力します
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;
}