Atcoder B – Boxes 玄学 + 数学

http://agc010.contest.atcoder.jp/tasks/agc010_b

预处理出每两个相邻的数的差值，那么首先知道是一共取了sum / ((1 + n) * n / 2)次，因为每一次固定要取这么多，所以这个就是操作次数。

然后观察到，每一次操作，都是把dis[]数组的n – 1个减小1，有一个要加上n – 1、最终要变成0

那么问题就是转化成，给定一个数，有两种操作，

第一种是减去1，第二种是加上某一个数，问其在k步后，能否变成0

那么设第一种操作用了x次，第二种操作就是k – x次，那么带入去，能得出一条方程。

dis[i] – x + (k – x) * (n – 1) = 0  （错误了）

不知为何这样错了，很假。

然后题解是设第一种用了k – x次，第二种用了x次。

那么就是dis[i] – (k – x) + x * (n – 1) = 0（能过）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 2e5 + ;
int a[maxn];
vector<int>da;
void work() {
    int n;
    LL sum = ;
    cin >> n;
    for (int i = ; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    LL add = 1LL * n * (n + ) / ;
    if (sum % add != ) {
        cout << "NO" << endl;
        return;
    }
    for (int i = ; i <= n; ++i) {
        da.push_back(a[i] - a[i - ]);
    }
    da.push_back(a[] - a[n]);
    LL k = sum / add;
    for (int i = ; i < da.size(); ++i) {
        LL t = k - da[i];
//        LL t = da[i] + k * (n - 1);
        if (t % n !=  || t < ) {
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return ;
}