AGC010-B-Boxes

AGC010-B-boxes

题意：给定一数列，每次可以选取一起点将全数列分别减去1-n，求是否可以形成全为0的数列。

题解：若有答案，则选取的起点位置和数目唯一且确定。

在差分数组上这个操作相当于把一个数加n-1,其他数减1.最后使得所有数为0.

若有方案，则需满足：

1. 差分数组和为0，由于是个环，已经满足。
2. 差分数组的差分全是n的倍数，每次操作可以看成在某一位加n，然后在所有位置上减1.

据此唯一的构造方案就是也可以确定了，对应到原数组上，由于原数组最后任意一位都是0，只需按照构造方案操作，判断任意一位是否为0即可.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+10;
const ll inf=1e16;
int n;
int all[maxn],cha[maxn];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>all[i];
    if(n==1){
        cout<<"YES";
        return 0;
    }
    ll sum0=0,now0=(n*(n+1)/2LL);
    for(int i=1;i<=n;i++) sum0+=all[i];
    if(sum0%now0){cout<<"NO";return 0;}
    else sum0/=now0;
    cha[1]=all[1]-all[n];
    for(int i=1;i<n;i++) cha[i+1]=all[i+1]-all[i];
    int min1=0;
    for(int i=1;i<=n;i++) min1=max(min1,cha[i]);
    for(int i=1;i<=n;i++) cha[i]-=min1;
    bool ye=1;
    for(int i=1;i<=n;i++){
        if(cha[i]%n){ye=0;break;} 
        cha[i]/=n;
    }
    if(!ye){cout<<"NO";return 0;}
    ll now3=all[1];
    for(int i=1;i<=n;i++){
        ll now1=i,now2=cha[i];
        if(now1==1) now3+=now2;
        else now3+=(2+n-now1)*now2; 
    }
    if(now3) cout<<"NO";
    else cout<<"YES";
    return 0;
}

AGC010-B-Boxes

原文：https://www.cnblogs.com/14long-Alex/p/14780534.html