A. Berland Poker

先尽可能的吧小丑给一个人，在把剩下的小丑尽可能的平分，最后计算差值即可。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, k, t;
    cin >> n >> m >> k, t = n / k;
    int a = min(m, t);
    m -= a, k--;
    int b = (m + k - 1) / k;
    cout << a - b << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

B. New Theatre Square

因为只有\(1\times1,1\times2\)两种白色瓷砖，所以每一行单独 dp 求一下就好了。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, a, b, res = 0;
    cin >> n >> m >> a >> b;

    string g;
    for (int i = 1; i <= n; i++) {
        cin >> g;
        vector<int> f(m + 1);
        for (int j = 1; j <= m; j++) {
            if (g[j - 1] == '*') f[j] = f[j - 1];
            else {
                f[j] = f[j - 1] + a;
                if (j - 2 >= 0 && g[j - 2] == '.')
                    f[j] = min(f[j], f[j - 2] + b);
            }
        }
        res += f[m];
    }
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

C. Mixing Water

其实混合只有两种情况

\(x\)杯热水，\(x\)杯凉水，温度一定\(\frac{h + c }{ 2}\)
\(x+1\)杯热水，\(x\)杯凉水，水温是\(T_x=\frac{(x+1)h+xc}{2x+1}\)，并且\(T_x\in(\frac{h+c}{2},h],T_x>T_{x+1}\)

知道这些之后其实很好做了，如果\(t\le \frac{h+c}{2}\)答案一定是 2，否则可以二分答案。

其实对于第二种情况如果解\(T_x=t\)可以解出\(x=\frac{t-h}{h+c-2t}\)，但是涉及到取证的问题，比较简单的做法是计算\(x-,x,x+1\)取最优解即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long
typedef long double ld;

void solve() {
    int c, h, T;
    cin >> h >> c >> T;
    if (c + h >= T * 2) {
        cout << "2\n";
        return;
    }
    int x = (T - h) / (h + c - 2 * T );
    ld v = LDBL_MAX;
    int res = -1;
    for (int i = max(0ll, x - 1); i <= x + 1; i++) {
        ld vi = abs(ld((i + 1) * h + i * c) / ld(2 * i + 1) - ld(T));
        if( vi < v ) v = vi , res = 2*i+1;
    }
    cout << res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

D. Yet Another Yet Another Task

首先如果没有删除操作的话，实际上就是非常简单最大子串和。

Bob实际上为了最优解，删除的一定子区间的内的最大值。

发现\(a\)的值域其实很小，我们考虑枚举最大值\(k\)，然后不选大于最大值的值，即把\(a_i>k\)的值置为\(-\infty\)，这样的话，求出最大子串和之后减去\(k\)就是当前情况下的最优解。

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, res = 0;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    for( int k = 0 ; k <= 30 ; k ++ ){
        auto b = a;
        for( auto & i : b )
            if( i > k ) i = INT_MIN;
        int ans = 0 , cnt = 0;
        for( const auto & i : b ){
            cnt += i;
            if( cnt < 0 ) cnt = 0;
            ans = max( ans , cnt );
        }
        res = max( res , ans - k );
    }
    cout << res << "\n";
    return 0;
}

E. Modular Stability

在本地找规律就会发现，当\(a_1\)确定时，\(a_i\)一定是\(a_1\)的倍数。所以答案就是

\[\sum C_{\frac{n}{a_1}-1}^{k-1} \]

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

vector<int> fact, invFact;

int power(int x, int y) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1, x = x * x % mod;
    }
    return ans;
}

int inv(int x) {
    return power(x, mod - 2);
}

void init(int n) {
    fact = vector<int>(n + 1), invFact = vector<int>(n + 1);
    fact[0] = 1, invFact[0] = inv(1);
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % mod, invFact[i] = inv(fact[i]);
}

int C(int x, int y) {
    assert(x >= y);
    return fact[x] * invFact[x - y] % mod * invFact[y] % mod;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, k, res = 0;
    cin >> n >> k;
    if (n < k) {
        cout << "0\n";
        return 0;
    }
    init(n);
    for (int i = 1; i * k <= n; i++)
        res = (res + C(n / i - 1, k - 1)) % mod;
    cout << res;
    return 0;
}

证明可以去看看原题链接给的题解