AGC010 - B: Boxes

原题链接

题意简述

给出一个由n(n≤105)个数构成的环，每次可以选择一个位置并从这个数起顺时针依次对每个数-1，-2，-3，…，-n。问能否将所有数全变为0。

分析

考虑一次操作对环带来了什么影响。
(在an后加一个a1来表示数环)
6,3,5,7,9(,6) -> 5,1,2,3,4(,5)
5,1,2,3,4(,5) -> 0,0,0,0,0(,0)
差分后：
−3,2,2,2,−3 -> −4,1,1,1,1
−4,1,1,1,1 -> 0,0,0,0,0
可以看到，一次操作相当于对差分数列（或者说是差分环）的一个位置加上n-1，剩下的位置减去1。那么只要检查原环的差分数列能否全变为0，并且此时和也为0就行了。
对每一个位置的计算复杂度为O(1)，总时间复杂度为O(n)。

实现

每次操作会使和sum减少 s0=n(n+1)/2，那么总共进行了 k=sum/s0 次操作。如果k不为整数那么不可行。
差分数列的每个位置要能在数个 +(n−1) 和 −1 后变为0，否则不可行。
列式表示为 (ai+1−ai)+xi(n−1)−(k−xi)=0，如果任何一个xi不为整数那么不可行。
最后，如果∑xi≠k说明此时sum≠0，不可行。

代码

复制代码#include <cstdio> typedef long long lint; int const N=1e5+10; int n,a[N]; int dif[N]; int main() { freopen("b.in","r",stdin); scanf("%d",&n); if(n==1) {printf("YES"); return 0;} for(int i=1;i<=n;i++) scanf("%d",&a[i]); a[n+1]=a[1]; lint s=(lint)n*(n+1)>>1,sum=0; for(int i=1;i<=n;i++) sum+=a[i],dif[i]=a[i+1]-a[i]; if(sum%s!=0) {printf("NO"); return 0;} lint k=sum/s,sumX=0; for(int i=1;i<=n;i++) { lint x=(k-dif[i])/n; if(x<0 || x*n!=k-dif[i]) {printf("NO"); return 0;} sumX+=x; } if(sumX==k) printf("YES"); else printf("NO"); return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
typedef long long lint;
int const N=1e5+10;
int n,a[N];
int dif[N];
int main()
{
    freopen("b.in","r",stdin);
    scanf("%d",&n);
    if(n==1) {printf("YES"); return 0;}
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    a[n+1]=a[1];
    lint s=(lint)n*(n+1)>>1,sum=0;
    for(int i=1;i<=n;i++) sum+=a[i],dif[i]=a[i+1]-a[i];
    if(sum%s!=0) {printf("NO"); return 0;}
    lint k=sum/s,sumX=0;
    for(int i=1;i<=n;i++)
    {
        lint x=(k-dif[i])/n;
        if(x<0 || x*n!=k-dif[i]) {printf("NO"); return 0;}
        sumX+=x;
    }
    if(sumX==k) printf("YES");
    else printf("NO");
    return 0;
}

注意

开longlong！int*int也有可能爆int，要先转成longlong再乘！
连WA六发…