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 ;

}

巴特西

Atcoder B - Boxes 玄学 + 数学

最新文章

热门文章