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

A. Homework

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    int n, m;
    string a, b, c;
    cin >> n >> a >> m >> b >> c;

    string ans1, ans2;
    for (int i = 0; i < c.size(); ++i)
    {
        if (c[i] == 'D')
            ans2.push_back(b[i]);
        else
            ans1.push_back(b[i]);
    }

    ranges::reverse(ans1);

    cout << ans1 << a << ans2 << endl;
}

B. The Secret Number

算法：

    推公式。

思路：

    已知：

\(n = x + y, \quad y = x \cdot 10^k\)

    因此:

\(n = x + x \cdot 10^k\)

    化简可得：

\(n = x \left( 1 + 10^k \right)\)

    于是：

\(n = x \left( 1 + 10^k \right)\)

    只需枚举所有可能的 \(k\)，即可得到对应的解。

关键代码：

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

    string s = to_string(n);
    int len = s.size();

    vector<ll> ans;
    for (int k = len; k; --k)
    {
        ll cur = 1 + powl(10, k);
        ll x = n / cur;

        if (x * cur == n)
            ans.push_back(x);
    }

    cout << ans.size() << endl;
    if (ans.size())
    {
        for (auto x : ans)
            cout << x << ' ';
        cout << endl;
    }
}

C1. The Cunning Seller (easy version)

算法：

    模拟，贪心。

思路：

    题目要求最小化交易次数，直接从大的开始选即可。

关键代码：

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

    ll cur = n;
    ll ans = 0;
    for (int i = 20; i >= 0; --i)
    {
        ll cnt = pow(3, i);

        if (cur < cnt)
            continue;

        ll t = cur / cnt;
        ans += t * (pow(3, i + 1) + i * pow(3, i - 1));
        cur -= t * cnt;
    }

    cout << ans << endl;
}

C2. The Cunning Seller (hard version)

算法：

    模拟，贪心。

思路：

    先根据 \(c1\) 的思路求出最小的操作次数和每种方案买了几次，再从大到小将这些次数拆分成小一个的，既 \(3^i \Rightarrow 3^{i – 1}\)，每次 \(3^i\) 拆分成 \(3^{i – 1}\) 会使购买次数 \(+ 2\)。

关键代码：

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

    vector<ll> p(25, 1);
    for (int i = 1; i <= 20; ++i)
        p[i] = p[i - 1] * 3;

    ll cur = n;
    vector<ll> a(25, 0);
    for (int i = 20; i >= 0; --i)
    {
        ll cnt = p[i];

        if (cur < cnt)
            continue;

        ll t = cur / cnt;
        cur -= t * cnt;
        a[i] = t;
    }

    ll s = 0;
    for (auto x : a)
        s += x;

    if (s > k)
    {
        cout << -1 << endl;
        return;
    }

    for (int i = 20; i; --i)
    {
        if (a[i])
        {
            ll t = k - s;
            ll cnt = min(t / 2, a[i]);

            s += cnt * 2;
            a[i - 1] += cnt * 3;
            a[i] -= cnt;
        }
    }

    ll ans = 0;
    for (int i = 20; i >= 0; --i)
    {
        if (a[i])
            ans += a[i] * (pow(3, i + 1) + i * pow(3, i - 1));
    }

    cout << ans << endl;
}

D. From 1 to Infinity

算法：

    二分，推公式。

思路：

    对于本题可以将问题拆解为以下问题：

1. 找出 \(k\) 完整包含的最大的数字 \(n\)。
2. 找出前 \(n\) 个数字的数位和。
3. 如果 \(k\) 还包含 \(n + 1\) 的一部分就补上。

    对于第一个问题可以二分求得，第二个问题直接推公式求得，第三个问题根据情况补充即可。

关键代码：

void solve()
{
    ll k;
    cin >> k;

    vector<ll> v(25, 0);
    ll cur = 9;
    for (int i = 1; i < 17; ++i)
    {
        v[i] = cur * i + v[i - 1];
        cur *= 10;
    }

    vector<ll> p(25, 0);
    p[0] = p[1] = 1;
    for (int i = 2; i < 17; ++i)
        p[i] = p[i - 1] * 10;

    auto check = [&](ll mid) -> bool
    {
        string s = to_string(mid);
        ll len = s.size();

        ll t = mid - p[len] + 1;
        ll cnt = v[len - 1] + t * len;

        return cnt <= k;
    };

    ll l = 1, r = 1e16;
    while (l < r)
    {
        ll mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    ll now = l;
    string s = to_string(now);
    ll len = s.size();
    ll t = now - p[len] + 1;
    ll cnt = v[len - 1] + t * len;

    ll ans = 0;
    for (ll i = 1; i <= now; i *= 10)
    {
        ll high = now / (i * 10);
        ll cur = (now / i) % 10;
        ll low = now % i;

        ans += high * 45 * i;
        ans += (cur * (cur - 1) / 2) * i;
        ans += cur * (low + 1);
    }

    if (cnt == k)
        cout << ans << endl;
    else
    {
        string t = to_string(now + 1);

        for (int i = 0; cnt < k; ++i, ++cnt)
            ans += t[i] - '0';

        cout << ans << endl;
    }
}

E. Arithmetics Competition

算法：

    前缀技巧，贪心，排序。

思路：

    如果没有 \(x, y\) 的限制，那么在 \(a, b\) 中取 \(k\) 个的最优答案必然是两个数组合并排序后得到数组的前 \(z\) 项，就是在 \(a\) 中选前 \(A_z\) 个，在 \(b\) 中选 \(B_z\) 个。

    引入 \(x, y\) 后可以发现每次询问：

• 如果 \(x >= A_z\) 且 \(y >= B_z\)，那么答案就是 \(a\) 的前 \(A_z\) 个元素，\(b\) 的前 \(B_z\) 个元素（对于每次快速查询 \(a, b\) 数组的前缀元素和，直接进行前缀处理即可）。
• 如果上述不满足那么就是 \(x >= A_z\) 或者 \(y >= B_z\) 不满足。
  • 如果 \(x >= A_z\) 不满足：就是 \(a\) 中要少选几个元素，在 \(b\) 中多选几个元素即可。
  • 如果 \(y >= B_z\) 不满足：同上。

关键代码：

void solve()
{
    int n, m, q;
    cin >> n >> m >> q;

    vector<ll> a(n), b(m);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;

    ranges::sort(a, greater<>());
    ranges::sort(b, greater<>());

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

    vector<ll> sb(m + 10, 0);
    for (int i = 1; i <= m; ++i)
        sb[i] = sb[i - 1] + b[i - 1];

    vector<ll> cnt(n + m + 1, 0);
    int i = 0, j = 0;
    for (int k = 1; k <= n + m; ++k)
    {
        cnt[k] += cnt[k - 1];
        if (i < n && j < m)
        {
            if (a[i] >= b[j])
                ++cnt[k], ++i;
            else
                ++j;
        }
        else
        {
            if (i < n)
                ++cnt[k], ++i;
            else
                ++j;
        }
    }

    while (q--)
    {
        ll x, y, z;
        cin >> x >> y >> z;

        ll k = cnt[z];
        ll kk = z - cnt[z];

        ll ans = 0;
        if (x >= k && y >= kk)
            ans = sa[k] + sb[kk];
        else
        {
            if (x >= k)
                ans = sa[z - y] + sb[y];
            else
                ans = sa[x] + sb[z - x];
        }

        cout << ans << endl;
    }
}

F. Rada and the Chamomile Valley

    还没补。