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

A. DBMB and the Array

算法：

贪心。

思路：

考虑到操作可以执行任意次，所以只要数组和与 \(s\) 的差是 \(x\) 的倍数就可以满足题目要求。

关键代码：

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

    ll sum = accumulate(all(a), 0ll);

    if (sum > s)
        cout << "NO" << endl;
    else if (sum == s || (s - sum) % x == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

B. Reverse a Permutation

算法：

贪心。

思路：

将不在正确位置的最大值换到可换到的最前面即可。

关键代码：

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

    int pos = 0;
    int maxx = n;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == maxx)
        {
            --maxx;
            ++pos;
            continue;
        }
        else
            break;
    }

    for (int i = pos; i < n; ++i)
    {
        if (a[i] != maxx)
            continue;

        for (int l = pos, r = i; l < r; ++l, --r)
            swap(a[l], a[r]);
        break;
    }

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

C. Replace and Sum

算法：

贪心，前缀和。

思路：

逆序递推，对于每个 \(i\) 使得其 \(a_i = max(a_i, b_i)，a_{i – 1} = max(a_i, a_{i – 1})\)

关键代码：

void miyan()
{
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n + 1);
    vector<ll> b(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];

    for (int i = n; i >= 1; --i)
    {
        if (b[i] > a[i])
            a[i] = b[i];

        if (i > 1 && a[i] > a[i - 1])
            a[i - 1] = a[i];
    }

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

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << ' ';
    }
    cout << endl;
}

D. Monster Game

算法：

二分，前缀和优化。

思路：

由于剑可以任意顺序使用，因此对剑进行排序。

定义 \(s\) 数组为 \(b\) 数组的前缀和数组。

考虑枚举 \(x = a_i\)，在 \(a\) 中二分找到大于等于 \(x\) 的个数 \(cnt\)（即可使用的剑的数量），在 \(s\) 数组中二分找到 \(<= cnt\) 的最后一项（即 \(cnt\) 可以击败几个怪物），其下标就为当前 \(x\) 的答案 \(cur\)。

最后答案取全局最大 \(cur\) 即可。

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];

    sort(a.begin() + 1, a.end(), greater<>());

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

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ll x = a[i];

        ll cur = ranges::upper_bound(a, x, greater<>()) - a.begin() - 1;
        ll cnt = ranges::upper_bound(s, cur) - s.begin() - 1;

        ans = max(ans, x * cnt);
    }

    cout << ans << endl;
}

E. Product Queries

算法：

\(dp\)。

思路：

经典 \(dp\) 题目。

定义 \(dp[i]\) 为构造出 \(i\) 所需最少元素个数。

初始化：

• \(dp[a[i]]_{i = 1}^{n} = 1\)

状态转移：

• 使用类埃式筛方法。
• 循环遍历 \(i = [1, n]\)，\(j = i * k\)，\(k\) 为正整数，易得 \(dp[j] = min(dp[j], dp[i] + dp[j / i])\)

关键代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> dp(n + 1, 1e9);
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;

        dp[x] = 1;
    }

    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i)
            dp[j] = min(dp[j], dp[i] + dp[j / i]);

    for (int i = 1; i <= n; ++i)
        cout << (dp[i] == 1e9 ? -1 : dp[i]) << ' ';
    cout << endl;
}

F. Pizza Delivery

算法：

\(dp\)。

思路：

观察到 \(YF\) 不能向上移动（数组轴），因此对于每一层（\(x\) 轴）的点肯定是统一处理完然后再处理下一层，不难想到每一层走过的距离只跟最左最右的点有关，因此只保存每一层最左最右的点，其余点对答案不产生影响。

通过上述不难想到每一层向下走的点（即当前层最后一个到达的点），一定是最左或者最右点。

考虑动态规划。

定义 \(dp[i][0/1]\) 为到达第 \(i\) 层最后一个点（最左点：\(0\)，最右点：\(1\) ）所需的最小步数。

状态转移：

• 遍历每一层的最左最右点 记为 \(minv, maxv\)，上一层最左最右点 记为 \(minl, maxl\)，上一层的层数记为 \(last\)，当前层的层数记为 \(x\)；
• 当前层左右移动距离为 \(maxv – minv\)；
• 可得：
  • \(dp1 = min(dp[idx – 1][1] + x – last + abs(minl – maxv), dp[idx – 1][0] + x – last + abs(maxl – maxv)) + cost;\)
  • \(dp0 = min(dp[idx – 1][1] + x – last + abs(minl – minv), dp[idx – 1][0] + x – last + abs(maxl – minv)) + cost;\)

关键代码：

void miyan()
{
    ll n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;

    map<ll, ll> maxx, minn;
    maxx[x1] = y1, maxx[x2] = y2;
    minn[x1] = y1, minn[x2] = y2;

    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;
    for (int i = 0; i < n; ++i)
    {
        ll x = a[i], y;
        cin >> y;
        if (!maxx.count(x))
            maxx[x] = y;
        else
            maxx[x] = max(maxx[x], y);

        if (!minn.count(x))
            minn[x] = y;
        else
            minn[x] = min(minn[x], y);
    }

    vector<array<ll, 2>> dp(n + 2);

    ll last = x1;
    int idx = 0;
    for (auto [x, maxv] : maxx)
    {
        if (x == last)
        {
            dp[idx++] = {0, 0};
            continue;
        }

        ll minv = minn[x];
        ll minl = minn[last], maxl = maxx[last];
        ll cost = maxv - minv;

        ll dp0 = 0, dp1 = 0;
        dp1 = min(dp[idx - 1][1] + x - last + abs(minl - maxv), dp[idx - 1][0] + x - last + abs(maxl - maxv)) + cost;
        dp0 = min(dp[idx - 1][1] + x - last + abs(minl - minv), dp[idx - 1][0] + x - last + abs(maxl - minv)) + cost;

        last = x;
        dp[idx++] = {dp0, dp1};
    }

    cout << dp[idx - 1][0] << endl;
}

G. Paths in a Tree

还没补。