Codeforces Round 753 (Div. 3)

A

因为把26打成25还WA了一发

void solve() {
    std::string s, a;
    std::cin >> s >> a;
    std::unordered_map<int, int> w;
    for (int i = 0; i < 26; i++) {
        w[s[i]] = i;
    }
    int ans = 0;
    for (int i = 1; i < a.size(); i++) {
        ans += std::abs(w[a[i]] - w[a[i - 1]]);
    }
    std::cout << ans << "\n";
}

B

一个简单分类讨论，思路想假了想了太久，而且从第二位开始讨论的

实际上从第一位开始讨论更方便，因为只用考虑最后三个数：

$设m = 4_floor(n)$

$x是奇数，依次+m+1,−1,-m-4$

$x是偶数，依次-m-1,+1,+m+4$

void solve() {
    ll x, n;
    std::cin >> x >> n;
    int m = (n - 1) % 4;
    if (x & 1) {
        x += 1 + (n - 1) / 4 * 4;
        ll top = (n - 1) / 4 * 4 + 1;
        switch (((n - 1) % 4 + 4) % 4) {
            case 3:
                x += top + 3;
            case 2:
                x -= top + 2;
            case 1:
                x -= top + 1;
        }
    } else {
        x += -1 - (n - 1) / 4 * 4;
        ll top = (n - 1) / 4 * 4 + 1;
        switch (((n - 1) % 4 + 4) % 4) {
            case 3:
                x -= top + 3;
            case 2:
                x += top + 2;
            case 1:
                x += top + 1;
        }
    }
    std::cout << x << "\n";
}

C

按题意，选最小的最优

对数组排序后容易发现答案只可能是两个相邻元素的差，或者是原始最小

void solve() {
    int n;
    std::cin >> n;
    std::vector<ll> a(n + 1);
    ll max = -1e14;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    std::sort(a.begin() + 1, a.end());
    for (int i = 1; i <= n; i++) {
        max = std::max(max, a[i] - a[i - 1]);
    }
    std::cout << max << "\n";
}

D

直觉是能增加的尽量占用大的位置，如果不能放就会多出一个数不能满足$permutation$

于是排序之后，要满足条件的最佳方案（也是必要条件）是最大数能够满足从$n$到$n-数组个数$的$permutation$

对能减少的数也一样

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }
    std::string s;
    std::cin >> s;
    std::priority_queue<int> r;
    std::priority_queue<int, std::vector<int>, std::greater<>> b;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') {
            r.push(a[i]);
        } else {
            b.push(a[i]);
        }
    }

    int i;
    for (i = n; i && !r.empty(); i--) {
        if (r.top() > i) {
            std::cout << "NO\n";
            return;
        } else {
            r.pop();
        }
    }

    for (int j = 1; j <= i && !b.empty(); j++) {
        if (b.top() < j) {
            std::cout << "NO\n";
            return;
        } else {
            b.pop();
        }
    }
    std::cout << "YES\n";
}

E

考虑整条路径，在矩形内的才是有意义的，而且一定可以找到一条不掉出边界的路径，满足能取到最大值，可以二分(额额，因为操作是有序的，所以直接维护最大边界就可以，不用二分）

枚举有序步骤的终点，假设从$(0, 0)$开始，记录最大和最小的$x, y$边界，最后再还原回去就行

void solve() {
    int n, m;
    std::string s;
    std::cin >> n >> m >> s;
    int lo = 0, hi = s.size() - 1;
    int ansX = 1, ansY = 1;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        int x = 0, y = 0;
        int maxX = 0, minX = 0, maxY = 0, minY = 0;
        for (int i = 0; i < mid; i++) {
            if (s[i] == 'L') {
                y--;
            } else if (s[i] == 'R') {
                y++;
            } else if (s[i] == 'U') {
                x--;
            } else {
                x++;
            }
            maxX = std::max(x, maxX);
            minX = std::min(x, minX);
            maxY = std::max(y, maxY);
            minY = std::min(y, minY);
        }
        if (maxX - minX < n && maxY - minY < m) {
            lo = mid;
            ansX = -minX + 1;
            ansY = -minY + 1;
        } else {
            hi = mid - 1;
        }
    }
    std::cout << ansX << " " << ansY << "\n";
}

F

思路是记录所有点开始的最长路径长度来更新答案长度和坐标

对于没有经过重复点的路径，直接记忆化搜索

对于经过重复点的路径，可以发现重复点到自身路径形成一个环，且路径上每一个点出发的最长路径就是这个环的长度

所有的路径都可以变成一条非环的路径长度加上一条环的长度，也可以记忆化

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

    std::vector<std::string> mov(n);
    for (auto &s : mov) {
        std::cin >> s;
    }

    std::vector cnt(n, std::vector<int>(m));
    std::vector vis(n, std::vector<bool>(m));

    int x, y, ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!vis[i][j]) {
                std::vector<PII> s;
                int ni = i, nj = j;
                while (ni >= 0 && ni < n && nj >= 0 && nj < m && !vis[ni][nj]) {
                    vis[ni][nj] = true;
                    s.emplace_back(ni, nj);
                    auto t = mov[ni][nj];
                    if (t == 'U') {
                        ni--;
                    } else if (t == 'D') {
                        ni++;
                    } else if (t == 'L') {
                        nj--;
                    } else {
                        nj++;
                    }
                }

                if (ni < 0 || ni >= n || nj < 0 || nj >= m) {
                    for (int k = 0; k < s.size(); k++) {
                        auto [X, Y] = s[k];
                        cnt[X][Y] = s.size() - k;
                    }
                } else if (cnt[ni][nj]) {
                    s.emplace_back(ni, nj);
                    for (int k = s.size() - 2; k >= 0; k--) {
                        auto [nX, nY] = s[k + 1];
                        auto [X, Y] = s[k];
                        cnt[X][Y] = cnt[nX][nY] + 1;
                    }
                } else {
                    auto p = std::find(s.begin(), s.end(), std::make_pair(ni, nj)) - s.begin();
                    for (int k = s.size() - 1, len = s.size() - p; k >= 0; k--) {
                        auto [X, Y] = s[k];
                        if (k >= p) {
                            cnt[X][Y] = len;
                        } else {
                            auto [nX, nY] = s[k + 1];
                            cnt[X][Y] = cnt[nX][nY] + 1;
                        }
                    }
                }
            }
            if (cnt[i][j] > ans) {
                ans = cnt[i][j];
                x = i;
                y = j;
            }
        }
    }
    std::cout << x + 1 << " " << y + 1 << " " << ans << "\n";
}

G

给你两个数组，对于两个数组每个位置减去的数的和一定为$m$，让两个操作之后的自然数组的差最小

如果$m$足够大，必存在一个位置使得两个数组的差为$0$或$1$，否则逼近

最终一个数组的状态决定另外一个的状态，只考虑一个数组,对于每次减操作，存在可能的上下限

先假设全取下限，然后尽量朝目标逼近即可

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

    ll asum = 0, bsum = 0, sum = 0;
    std::vector<int> a(n), b(n);
    std::vector<ll> max(n), min(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i] >> b[i];
        asum += a[i];
        bsum += b[i];
        max[i] = std::min(a[i], m);
        min[i] = std::max(m - b[i], 0);
        sum += a[i] - max[i];
    }

    ll all = (asum + bsum - 1ll * n * m), ave = all / 2;
    std::vector<ll> ans(n);
    for (int i = 0; i < n; i++) {
        ll d = std::min(std::max(ave - sum, 0ll), max[i] - min[i]);
        ans[i] = max[i] - d;
        sum += d;
    }
    std::cout << std::abs(2 * sum - all) << "\n";
    for (auto d : ans) {
        std::cout << d << " " << m - d << "\n";
    }
}

H

给任意个$a,b,m$，$m$是$a,b$减去的总和

使得$(a,b)$的种类尽量少

相同的$(a,b)$的性质有$a+b-m$相同,$a$相同（$b$相同由a相同决定，少一个自由度）

首先用 std::map维护$a+b-m$相同的对，然后和G一样维护$a_{max}$和$a_{min}$

$[a_{max},a_{min}]$有相交就可以变成同一种种类，经典区间合并问题

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n), b(n), m(n);
    std::map<int, std::vector<std::array<int, 5>>> M;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i] >> b[i] >> m[i];
        int l = std::max(0, a[i] - m[i]), r = a[i] - std::max(0, m[i] - b[i]);
        M[a[i] + b[i] - m[i]].push_back({l, r, i, a[i], m[i]});
    }

    std::vector<PII> d(n);
    int ans = 0;
    for (auto [sum, v] : M) {
        std::sort(v.begin(), v.end(), [](auto &l, auto &r) {
            return l[1] < r[1];
        });

        int ed = -1e9, lst = 0;
        for (int i = 0; i < v.size(); i++) {
            auto [l, r, id, a, m] = v[i];
            if (l > ed) {
                ed = r;
                ans++;
            }
            d[id].first = a - ed;
            d[id].second = m - d[id].first;
        }
    }

    std::cout << ans << "\n";
    for (int i = 0; i < n; i++) {
        std::cout << d[i].first << " " << d[i].second << "\n";
    }
}