链接：https://codeforces.com/contest/2145

A. Candies for Nephews

算法：

    数学。

思路：

    无。

关键代码：

void miyan()
{
    ll n;
    cin >> n;

    cout << ((3 - (n % 3)) % 3) << endl;
}

B. Deck of Cards

算法：

    模拟，贪心。

思路：

    无。

关键代码：

void miyan()
{
    int n, k;
    string s;
    cin >> n >> k >> s;

    string ans(n, ' ');
    ll l = 0, r = n - 1;
    ll cnt = 0;
    for (int i = 0; i < k; ++i)
    {
        if (s[i] == '0')
            ans[l++] = '-';
        else if (s[i] == '1')
            ans[r--] = '-';
        else
            ++cnt;
    }

    ll len = r - l + 1;

    if (!cnt)
    {
        for (int i = l; i <= r; ++i)
            ans[i] = '+';
    }
    else if (len == cnt)
    {
        for (int i = l; i <= r; ++i)
            ans[i] = '-';
    }
    else if (len > cnt)
    {
        for (int i = l; i <= r; ++i)
            ans[i] = '?';
        for (int i = l + cnt; i <= r - cnt; ++i)
            ans[i] = '+';
    }

    cout << ans << endl;
}

C. Monocarp’s String

算法：

    前缀和，哈希。

思路：

    题意：删除一段连续的段，使得剩余的 \(a\) 字符和 \(b\) 字符个数相等。

    定义 \(cnta\) 为 \(a\) 的个数，\(cntb\) 为 \(b\) 的个数，\(k = cnta – cntb\)，将 \(a\) 转换成 \(-1\)，\(b\) 转换成 \(1\)，对数组做前缀和，前缀和数组为 \(s\)。

    如果想让 \(a\) 的个数等于 \(b\) 的个数，就需要删除一段 \(a\) 的个数比 \(b\) 的个数多 \(k\) 个的区间，既 \(s[r] – s[l – 1] = k\)。

    对于当前 \(i\)，考虑使用哈希表存储所有前缀值的下标，既 \(s[1, 2]，s[1, 3]，……，s[1, i – 1]\)，如果哈希表中存在 \(s[i] – k\)，就更新全局答案，对数组全部遍历一遍更新答案即可。

关键代码：

void miyan()
{
    int n;
    string t;
    cin >> n >> t;

    ll cnta = ranges::count(t, 'a');
    ll cntb = n - cnta;

    if (cnta == cntb)
    {
        cout << 0 << endl;
        return;
    }

    if (!cnta || !cntb)
    {
        cout << -1 << endl;
        return;
    }

    vector<int> a(n, 0);
    for (int i = 0; i < n; ++i)
        a[i] = t[i] == 'a' ? 1 : -1;

    vector<ll> s(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + a[i - 1];

    ll ans = INT_MAX;
    ll need = cnta - cntb;
    map<int, int> m;
    for (int i = 1; i <= n; ++i)
    {
        m[s[i - 1]] = i - 1;

        ll val = s[i] - need;
        if (m.count(val))
            ans = min(ans, 1ll * i - m[val]);
    }

    if (ans == INT_MAX || ans == n)
        ans = -1;
    cout << ans << endl;
}

D. Inversion Value of a Permutation

算法：

    数学，动态规划，构造。

思路：

    题意：构造一个排列使得不是升序的区间（子数组）的个数为 \(k\) 个。

    先考虑对于一个排列其不是升序的区间个数最大为 — 整个排列是降序，既 \(n, n – 1, n – 2 ………… 2, 1\)。

    一个数组其不重复区间个数为 \(C_{n}^{2} = n(n – 1) / 2\)。

    那么一个完全升序的区间 \([l, r]\) 其长度为 \(x\)，那么就会有 \(C_{n}^{2} = x(x – 1) / 2\) 个升序的子数组。

    要使得恰好存在 \(k\) 个不是升序的区间需要存在一些逆序对，既将区间分解成一些连续的升序区间。

    \(eq\)：\([1, 6, 3, 4, 5, 2]\) 分解为 \([1, 6] [3, 4, 5] [2]\)。

    设某段升序区间长度为 \(x_i\)，要使得存在 \(k\) 个不是升序的区间那么就需要使得 \(C_{n}^{2} – ∑C_{x_i}^{2} = k\)。

    推导：

1. \(C_{n}^{2} – ∑C_{x}^{2} = k\)
2. \(n(n – 1) / 2 – ∑(x(x – 1) / 2) = k\)
3. \(n(n – 1) / 2 – (∑x(x – 1)) / 2 = k\)
4. \(n(n – 1) – ∑x(x – 1) = 2k\)
5. \(n ^ 2 – n – ∑x ^ 2 + ∑x = 2k\)

    其中 \(∑x = n\)，那么原式可表述为：\(2k = n ^ 2 – ∑x ^ 2\)。

    此时问题已经转换为：将长度为 \(n\) 的排列分解成若干段区间，使这些区间的长度的平方和为 \(S = n ^ 2 – 2k\)。

    由于 \(0 <= n <= 30\)，\(0 <= k <= n(n – 1) / 2\)，直接预处理一个 \(dp\) 表，预处理出来全部 \(n\) 和 \(k\) 是否可行。

    对于可行的 \(n\) 和 \(k\)，对 \(n\) 进行拆解，设 \(now\) 为当前剩余的段长，每次考虑拆解出 \(1\) ~ \(now\) 的可行长度并将其放入到数组 \(v\) 中。

    对于 \(v\) 其里面已经存储了每个上升段的长度。

    构造策略：

• 定义 \(cur = n\)，既逆序填数。
• 对于 \(v[i]\)，将这段填为 \([cur – x + 1, cur]\) 的数。

关键代码：

vector<vector<int>> dp(31, vector<int>(901, 0));
void init()
{
    dp[0][0] = 1;
    for (int i = 1; i <= 30; ++i)
    {
        for (int j = 0; j <= i * i; ++j)
        {
            bool ok = 0;
            for (int k = 1; k <= i; ++k)
            {
                ll cur = j - k * k;
                if (cur < 0)
                    break;

                if (dp[i - k][cur])
                {
                    ok = 1;
                    break;
                }
            }

            dp[i][j] = ok;
        }
    }
}

void miyan()
{
    ll n, k;
    cin >> n >> k;

    ll s = n * n - 2 * k;

    if (s < 0 || s > n * n)
    {
        cout << 0 << endl;
        return;
    }

    if (!dp[n][s])
    {
        cout << 0 << endl;
        return;
    }

    ll now = n;
    ll tot = s;
    vector<int> v;
    bool flag = 0;
    while (now)
    {
        bool ok = 0;
        for (int i = 1; i <= now; ++i)
        {
            ll cur = tot - i * i;

            if (cur < 0)
                break;

            if (dp[now - i][cur])
            {
                v.push_back(i);
                ok = 1;
                now -= i;
                tot = cur;
            }
        }

        if (ok)
            continue;

        flag = 1;
        break;
    }

    if (flag)
    {
        cout << 0 << endl;
        return;
    }

    ll cur = n;
    vector<int> ans;
    for (auto x : v)
    {
        for (int i = cur - x + 1; i <= cur; ++i)
            ans.push_back(i);

        cur -= x;
    }

    for (auto x : ans)
        cout << x << ' ';
    cout << endl;
}

E. Predicting Popularity

    还没补。