C. Set or Decrease

可以得到两个规律

修改操作一定是把较大的数变成最小的数更优
减一对谁操作都不影响结果

根据以上两个规律有可以总结出最优操作策略

对最小值先做若干次减法
把最大的若干个数变成最小值

已知策略后，我们发现因为值域很大，所以不能枚举最小值减的次数，同时最小值减的次数与最终结果也不满足单调性。

所以可以枚举修改多少个数字，然后二分出减法最少要做多少次。

#include <bits/stdc++.h>

using namespace std;

#define int __int128

const int inf = 1e15;

using ll = long long;

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

void solve() {
    int n, k, sum = 0;
    n = read() , k = read();
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        a[i] =  read(), sum += a[i];
    if (sum <= k) {
        cout << "0\n";
        return;
    }
    sort(a.begin() + 1, a.end(), greater<int>());
    int res = sum - k;
    for (int i = 1, pre = 0; i < n; i++) {
        if (res <= i) break;
        pre += a[i];
        int l = 0, r = inf, ans = 0;
        for (int mid; l <= r;) {
            mid = (l + r) >> 1;
            if (sum + i * a[n] - pre - (i + 1) * mid <= k) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        res = min(res, i + ans);
    }
    cout << (ll)res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    for (int t = read(); t; t--)
        solve();
    return 0;
}

D. Shuffle

首先可以想到一个比较正确的做法。

先选择连续的\(k\)个\(1\)，然后找到只包含这些\(1\)的最大子区间。子区间长度为\(len\)，则排列方式有\(C_{len}^{k}\)，其中产生变换的排列方式有\(C_{len}^{k}-1\)种，所以答案为\(\sum (C_{len}^{k}-1)\)。

但其实我们观察样例就发现会有重复的情况。思考重复的部分是怎样产生的。对于相邻的两个区间，重合部分有前一个区间的后\(k-1\)个和后一个区间的前\(k-1\)个，所以当前一个区间的第一个不动后\(k-1\)个一定发生改变，后一个区间前\(k-1\)个一定发生改变最后一个不动，这样就会产生重复的情况。所以我们减去这部分重复的情况。特别的，第一个区间不受这种情况的影响。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18, N = 5005;
const int mod = 998244353;

using ll = long long;

vector C(N, vector<int>(N, 0));

void init() {
    for (int i = 0; i < N; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    init();
    int n, k;
    string s;
    cin >> n >> k >> s;
    if (k == 0) {
        cout << "1\n";
        return 0;
    }
    vector<int> v;
    v.push_back(-1);
    for (int i = 0; i < n; i++)
        if (s[i] == '1') v.push_back(i);
    v.push_back(n);
    int res = 0;
    for (int i = 1, l, r; i + k < v.size(); i++) {
        l = v[i - 1] + 1, r = v[i + k] - 1;
        res += (C[r-l+1][k] - 1);
        if( i != 1 ) res -= ( C[ v[i+k-1]  - l ][k-1] - 1 );
        res %= mod;
    }
    cout << ( res + 1 + mod ) % mod;
    return 0;
}

E. Math Test

这道题学到了一个新技巧——对于绝对值可以直接枚举。

\[S=\sum_{i=1}^{n} |x_i-r_i| = \sum_{i=1}^{n} c_i(x_i-r_i),c_i\in\{0,1\}\\ =\sum_{i=1}^{n} c_i\times x_i - \sum_{i=1}^{n}c_i\times r_i \]

因为\(n\le10\)，所以我们可以直接枚举\(c_i\)

\[\sum_{i=1}^{n} c_i\times r_i =\sum_{i=1}^{n} c_i \times( \sum_{j=1}^{m} a_{i,j}\times p_j )\\ =\sum_{j=1}^{m} (\sum_{i=1}^{n} c_i \times a_{i,j})\times p_j \]

令\(cnt_j=\sum_{i=1}^{n} c_i \times a_{i,j}\)，则有

\[S = \sum_{i=1}^{n} c_i\times x_i - \sum_{j=1}^{m} cnt_j\times p_j \]

当枚举出\(c_i\)后\(\sum_{i=1}^{n} c_i\times x_i , \sum_{j=1}^{m} cnt_j\)都已经确定了。为了最大化\(S\)则需要尽可能减少\(p_j\)产生的贡献，所以把 \(p_j\)按照\(cnt_j\)排序。

所以枚举出\(c_i\)后贪心的计算出\(S\)，找到最优解即可。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> x(n);
    for (auto &i: x) cin >> i;
    vector<string> a(n);
    for (auto &i: a) cin >> i;

    int ans = -1;
    vector<int> best;
    for (int mask = 0, T = (1 << n); mask < T; ++mask) {
        vector<int> val(m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (a[i][j] == '1')
                    val[j] += ((mask >> i) & 1 ? 1 : -1);
        int res = 0;
        for (int i = 0; i < n; i++)
            res += ((mask >> i) & 1) ? -x[i] : x[i];
        vector<int> p(m);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&val](int x, int y) { return val[x] < val[y]; });
        for (int i = 0; i < m; i++)
            res += val[p[i]] * (i + 1);
        if (res > ans) ans = res, best = p;
    }

    vector<int> ansPerm(m);
    for (int i = 0; i < m; i++)
        ansPerm[best[i]] = i + 1;
    for (auto i: ansPerm)
        cout << i << " ";
    cout << "\n";
    return;
}


int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}