2020 China Collegiate Programming Contest Changchun Onsite L. Coordinate Paper

题目描述

https://codeforces.com/gym/102832/problem/L

Solution

我们不妨先将所有操作都变成加 $1$

不妨假设序列为 $v,v+1,\cdots,v+n-1$

我们发现可以让这数列增大 $k+1$ 的任何倍数

第一次我们在 $v$ 上增加，第二次可以在 $v+1$ 上增加

注意到这样不会改变整个数列的和模 $k+1$ 的值，且这个值只与 $v$ 有关

我们考虑枚举 $v$，这时候如果整个数列的和与 $s$ 模 $k+1$ 的值相同，且 $s$ 小于这个 $v$ 所能构造出的最小序列

那么一定有解，不断加 $k+1$ 即可

$v$ 能构造出的最小序列是这样的：$v,v+1,\cdots,k,0,1,2,\cdots,k,0,\cdots$

#include <iostream>
#include <cstdio>
#include <vector>
#define ll long long
#define maxn 100010
using namespace std;

ll n, k,s;

ll a[maxn];

vector<int> cnt[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k >> s;
    if (n == 1) return cout << s << "\n", 0; 
    ll sum; bool ok = 0; 
    for (int i = 0; i <= k; ++i) {
        ll v = max(0ll, n - min(n, k - i + 1)) / (k + 1);
        ll r = (n - min(n, k - i + 1) - v * (k + 1)) % (k + 1);
        sum = (v * k * (k + 1) + r * (r - 1) + (min(i + n - 1, k) + i) * (min(i + n - 1, k) - i + 1)) / 2; 
        if (s >= sum && s % (k + 1) == sum % (k + 1)) { a[1] = i; ok = 1; break; } 
    }
    if (!ok) return cout << "-1\n", 0; 
    cnt[a[1]].push_back(1);
    for (int i = 2; i <= n; ++i)
        a[i] = (a[i - 1] + 1) % (k + 1), cnt[a[i]].push_back(i); 
    ll p = (s - sum) / (k + 1), v = p / n, r = p % n; sum = 0; 
    for (int i = 1; i <= n; ++i) a[i] += v * (k + 1); 
    for (int i = 0; i <= k && sum < r; ++i) 
        for (auto u : cnt[i]) {
            a[u] += k + 1;
            if (++sum == r) break; 
        }
    for (int i = 1; i <= n; ++i) cout << a[i] << " \n"[i == n]; 
    return 0; 
}