链接：https://atcoder.jp/contests/abc432

A – Permute to Maximize

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    array<int, 3> a;
    for (int i = 0; i < 3; ++i)
        cin >> a[i];

    ranges::sort(a);

    for (int i = 2; i >= 0; --i)
        cout << a[i];
    cout << endl;
}

B – Permute to Minimize

算法：

    模拟。

思路：

    无。

关键代码：

void miyan()
{
    vector<int> a;
    int cnt = 0;
    char c;
    while (cin >> c)
    {
        if (c == '0')
            ++cnt;
        else
            a.push_back(c - '0');
    }

    ranges::sort(a);

    cout << a[0];
    while (cnt--)
        cout << 0;
    for (int i = 1; i < a.size(); ++i)
        cout << a[i];
    cout << endl;
}

C – Candy Tribulation

算法：

    数学，贪心。

思路：

    设 \(b_i\) 为每个人获得的大糖果的数量。

• 那么第 \(i\) 个人获得的总重量为 \((a_i – b_i) * x + b_i * y = W\)
• 整理得：\(a_i * x – b_i * x + b_i * y = a_i * x + b_i * (y – x) = W\)
• 令 \(val = y – x\)
• 原式 \(= a_i * x + b_i * val = W\)
• 每个 \(b_i = (W – a_i * x) / val\)
• 那么对于任意的 \(<i, j>\)
• 有 \(a_i * x + b_i * val = a_j * x + b_j * val\)
• 整理得：\(b_i – b_j = ((a_j – a_i) * x) / val\)
• 可知条件\(1\)：任意两个 \(a_i\) 的差值都是 \(val\) 的倍数。

    贪心策略：

• 对于 \(W\)，给获得最少糖果的人的糖果全为大糖果，既 \(W = a_i * y\)
• 其他人获得的大糖果数量 \(b_i = (W – a_i * x) / val\)
• 如果存在一个人全部选择小糖果后依然小于 \(W\)，无解。

关键代码：

void miyan()
{
    ll n, x, y;
    cin >> n >> x >> y;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    ranges::sort(a);

    ll val = y - x;
    for (int i = 1; i < n; ++i)
    {
        if (((a[i] - a[i - 1]) * x) % val != 0)
        {
            cout << -1 << endl;
            return;
        }
    }

    ll W = a[0] * y;
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        ll cur = (W - a[i] * x) / val;

        if (a[i] * x > W)
        {
            cout << -1 << endl;
            return;
        }

        ans += cur;
    }

    cout << ans << endl;
}

D – Suddenly, A Tempest

    还没补。

E – Clamp

算法：

    树状数组。

思路：

• \(if\) \(l >= r\)
  • \(t = l\)
• \(else\)
  • \(if\) \(a[i] <= l:\)
    • \(t = l\)
  • \(else\) \(if\) \(a[i] > l:\)
    • \(if\) \(a[i] > r:\)
      • \(t = r\)
    • \(else\) \(if\) \(a[i] <= r\)
      • \(t = a[i]\)

    情况 \(1\) 直接输出。

    对于情况 \(2\)：

• \(ans = cnt(1, l) * l + cnt(r + 1, N) * r + cnt(l + 1, r) * a[i]\)。
• 只需求得 \(cnt(1, l)\)、\(cnt(r + 1, N)\) 和 \([l + 1, r]\) 的元素和。
• 树状数组求解。

关键代码：

int n, q;
vector<int> a;
vector<ll> tr(N, 0);  
vector<ll> sum(N, 0);

void update1(int x, int val)
{
    for (; x <= M; x += x & -x)
        tr[x] += val;
}

ll query1(int x)
{
    ll ans = 0;
    for (; x; x -= x & -x)
        ans += tr[x];
    return ans;
}

void update2(int x, int val)
{
    for (; x <= M; x += x & -x)
        sum[x] += val;
}

ll query2(int x)
{
    ll ans = 0;
    for (; x; x -= x & -x)
        ans += sum[x];
    return ans;
}

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

    a.resize(n + 1);

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        ++a[i];
        update1(a[i], 1), update2(a[i], a[i]);
    }

    while (q--)
    {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1)
        {
            ++y;
            update1(a[x], -1), update2(a[x], -a[x]);
            a[x] = y;
            update1(a[x], 1), update2(a[x], a[x]);
        }
        else
        {
            ++x, ++y;

            if (x >= y)
                cout << 1ll * n * (x - 1) << endl;
            else
                cout << (query1(x) * (x - 1)) + ((query1(M) - query1(y)) * (y - 1)) + (query2(y) - query2(x)) - (query1(y) - query1(x)) << endl;
        }
    }
}

F – Candy Redistribution

    还没补。