Codeforces Round #673 (Div. 2)

题目传送门

A. Copy-paste

把最小的数加到其他数上。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)
 
int n, k, a[1010];
void solve(int T) {
    
    cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    sort(a + 1, a + n + 1);
    int ans = 0;
    rep(i, 2, n) ans += ceil((k - a[i]) / a[1]);
    cout << ans << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
 
    int T = 1;
    cin >> T;
    rep(i, 1, T) solve(i);
}

B. Two Arrays

小于$frac{x}{2}$的涂黑，大于$frac{x}{2}$的涂白，等于$frac{x}{2}$间隔着涂。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)
 
ll n, k, a[100010], flag;
void solve(int T) {
    
    cin >> n >> k;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) {
        if(a[i] * 2 < k) cout << "1 ";
        else if(a[i] * 2 > k) cout << "0 ";
        else {
            cout << flag << " ";
            flag ^= 1;
        }
    }
    cout << endl;
 
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
 
    int T = 1;
    cin >> T;
    rep(i, 1, T) solve(i);
}

C.k-Amazing Numbers

预处理每个数字的最大间隔，转化以下即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)
 
ll n, a[300010], itv[300010], cnt[300010];
ll ans[300010];
void solve(int T) {
    
    cin >> n;
    rep(i, 1, n) cin >> a[i], itv[i] = cnt[i] = 0, ans[i] = -1;
    rep(i, 1, n) itv[a[i]] = max(itv[a[i]], i - cnt[a[i]]), cnt[a[i]] = i;
    rep(i, 1, n) itv[i] = max(itv[i], n + 1 - cnt[i]);
    int tmp = 1;
    for(int i = 1; i <= n; i++) for(; tmp <= n + 1 - itv[i]; tmp++) ans[tmp] = i;
    for(int i = n; i; i--) cout << ans[i] << " ";
    cout << endl;
 
 
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // freopen("in.txt", "r", stdin);
    // freopen("ans.txt", "w", stdans);
 
    int T = 1;
    cin >> T;
    rep(i, 1, T) solve(i);
}

D - Make Them Equal

要把所有数都变成一样，贪心构造。

首先可以花费至多$(n-1)*2$将所有数加到a[1]上，然后再花费$n-1$再把a[1]平均分到每个数上。

这里我用的优先队列是防止把$a[i]$变为$i$的倍数的时候$a[1]$为负。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)

struct point {
    int id, v;
    bool operator<(const point & f) const {
        return ceil(1.0 * v / id) * id - v > ceil(1.0 * f.v / f.id) * f.id - f.v;
    }
};


vector<int> ans[300010];
int n, a[100010], tot;
priority_queue<point> q;
int sum;
void solve(int T) {
    cin >> n;
    cin >> a[1];
    sum = a[1];
    while(!q.empty()) q.pop();
    rep(i, 2, n) cin >> a[i], sum += a[i], q.push((point){i, a[i]});
    if(sum % n) {
        cout << "-1" << endl;
        return;
    }
    tot = 0;
    while(!q.empty()) {
        point x = q.top();
        q.pop();
        if(x.v % x.id) {
            a[1] -= ceil(1.0 * x.v / x.id) * x.id - x.v;
            if(a[1] < 0) {
                cout << "-1" << endl;
                return;
            }
            ans[++tot].clear();
            ans[tot].push_back(1);
            ans[tot].push_back(x.id);
            ans[tot].push_back(ceil(1.0 * x.v / x.id) * x.id - x.v);
            x.v = ceil(1.0 * x.v / x.id) * x.id;
        }
        a[1] += x.v;
        ans[++tot].clear();
        ans[tot].push_back(x.id);
        ans[tot].push_back(1);
        ans[tot].push_back(x.v / x.id);
    }
    rep(i, 2, n) {
        ans[++tot].clear();
        ans[tot].push_back(1);
        ans[tot].push_back(i);
        ans[tot].push_back(sum / n);
    }
    cout << tot << endl;
    rep(i, 1, tot) {
        rep(j, 0, 2) cout << ans[i][j] << " ";
        cout << endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // freopen("in.txt", "r", stdin);
    // freopen("ans.txt", "w", stdans);
 
    int T = 1;
    cin >> T;
    rep(i, 1, T) solve(i);
}