Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)【A - E】

D 题想了半天怎么直接枚举 $x$ ，赛后发现是需要通过枚举两数之差的因子来间接确定 $x$ 。

E 题这种利用 map 进行区间删减合并的操作也很妙啊……

比赛链接：https://codeforces.com/contest/1782

A. Parallel Projection

题解

取四个方向的最小值。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int w, d, h;
        cin >> w >> d >> h;

        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << h + min({
            y1 + y2 + abs(x1 - x2),
            (d - y1) + (d - y2) + abs(x1 - x2),
            x1 + x2 + abs(y1 - y2),
            (w - x1) + (w - x2) + abs(y1 - y2)}
            ) << "\n";
    }

    return 0;
}

B. Going to the Cinema

题解

枚举去影院的人的个数。

如果去了 $i$ 个人，那么第 $i$ 小的人要求的人数应小于 $i$ ，第 $i + 1$ 小的人要求的人数应大于 $i$ 。

特判去了 $0$ 和 $n$ 人的情况。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());

        int ans = (a[0] > 0) + 1;
        for (int i = 1; i < n; i++) {
            if (a[i - 1] <= i - 1 and a[i] > i) {
                ans += 1;
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

C. Equal Frequencies

题解

枚举最后剩下的字符的种类数。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string s;
        cin >> s;

        vector<vector<int>> pos(26);
        vector<int> cnt(26);
        for (int i = 0; i < n; i++) {
            pos[s[i] - 'a'].push_back(i);
            cnt[s[i] - 'a'] += 1;
        }

        int ans = INT_MAX;
        string ans_str;
        for (int ch_num = 1; ch_num <= 26; ch_num++) {
            if (n % ch_num != 0) {
                continue;
            }
            int res = 0;
            string str = s;
            vector<pair<int, int>> v;
            for (int i = 0; i < 26; i++) {
                v.push_back({cnt[i], i});
            }
            sort(v.begin(), v.end(), greater());
            vector<int> add;
            while ((int)v.size() > ch_num) {
                add.insert(add.end(), v.back().first, v.back().second);
                v.pop_back();
            }
            vector<int> p(26);
            for (auto [x, y] : v) {
                if (x > n / ch_num) {
                    add.insert(add.end(), x - n / ch_num, y);
                } else {
                    for (int i = 0; i < n / ch_num - x; i++) {
                        str[pos[add.back()][p[add.back()]]] = char('a' + y);
                        p[add.back()] += 1;
                        add.pop_back();
                        res += 1;
                    }
                }
            }
            if (res < ans) {
                ans = res;
                ans_str = str;
            }
        }
        cout << ans << "\n" << ans_str << "\n";
    }

    return 0;
}

D. Many Perfect Squares

题解

两个数可以确定一个 $x$ ，设 $i \lt j$ ，则有：

$a_i + x = s_1^2$

$a_j + x = s_2^2$

$a_j - a_i = s_2^2 - s_1^2$

$a_j - a_i = (s_2 - s_1)(s_2 + s_1)$

枚举 $i, j$ 及对应的 $s_2 - s_1$ ，解出对应的 $x$ 。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    #define int long long

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        set<int> st;
        st.insert(0);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = 1; k * k <= abs(a[j] - a[i]); k++) {
                    if (abs(a[j] - a[i]) % k == 0) {
                        int s2 = (k + abs(a[j] - a[i]) / k) / 2;
                        int s1 = -(k - s2);
                        if (s1 * s1 - a[i] != s2 * s2 - a[j]) {
                            continue;
                        }
                        int x = s2 * s2 - max(a[i], a[j]);
                        if (x >= 0) {
                            st.insert(x);
                        }
                    }
                }
            }
        }

        int ans = 1;
        for (auto x : st) {
            int res = 0;
            auto b = a;
            for (int i = 0; i < n; i++) {
                b[i] += x;
                int sqr = sqrt(b[i]);
                if (sqr * sqr == b[i]) {
                    res += 1;
                }
            }
            ans = max(ans, res);
        }
        cout << ans << "\n";
    }

    return 0;
}

E. Rectangle Shrinking

题解

计算宽度为 1 的矩形的覆盖面积，先删减宽度为 2 的矩形。

对于一个宽度为 2 的矩形：

• 如果上下两行都被宽为 1 的矩形覆盖，则删除
• 如果上下两行有一行被宽为 1 的矩形覆盖，则缩减掉被覆盖的那一行
• 如果上下两行都未被宽为 1 的矩形覆盖，则对这些矩形进行删减合并

之后将删减完成，宽度为 2 的矩形看作两个宽度为 1 的矩形，再对宽度为 1 的矩形进行删减合并。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> u(n), l(n), d(n), r(n);
        for (int i = 0; i < n; i++) {
            cin >> u[i] >> l[i] >> d[i] >> r[i];
        }

        vector<int> p(n);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(), [&](int x, int y) {
            return l[x] < l[y];
        });

        map<int, int> f[2];
        for (auto i : p) {
            if (d[i] - u[i] == 1) {
                continue;
            }
            int x = u[i] - 1;
            if (not f[x].empty() and f[x].rbegin()->second >= l[i] - 1) {
                f[x].rbegin()->second = max(f[x].rbegin()->second, r[i]);
            } else {
                f[x][l[i]] = r[i];
            }
        }

        map<int, int> g[2];
        for (auto i : p) {
            if (d[i] - u[i] == 0) {
                continue;
            }
            vector<bool> cv(2);
            for (int x = 0; x < 2; x++) {
                auto it = f[x].upper_bound(l[i]);
                if (it != f[x].begin() and prev(it)->second >= r[i]) {
                    cv[x] = true;
                }
            }
            if (cv[0] and cv[1]) {
                u[i] = l[i] = d[i] = r[i] = 0;
                continue;
            }
            if (not cv[0] and not cv[1]) {
                if (not g[0].empty() and g[0].rbegin()->second >= r[i]) {
                    u[i] = l[i] = d[i] = r[i] = 0;
                } else if (not g[0].empty() and g[0].rbegin()->second >= l[i] - 1) {
                    l[i] = g[0].rbegin()->second + 1;
                    g[0].rbegin()->second = r[i];
                } else {
                    g[0][l[i]] = r[i];
                }
                continue;
            }
            if (cv[0]) {
                u[i] = 2;
            } else {
                d[i] = 1;
            }
        }
        g[1] = g[0];

        for (auto i : p) {
            if (u[i] == 0 or d[i] - u[i] == 1) {
                continue;
            }
            int x = u[i] - 1;
            auto it = g[x].upper_bound(l[i]);
            if (it != g[x].end()) {
                r[i] = min(r[i], it->first - 1);
            }
            if (it != g[x].begin() and prev(it)->second >= r[i]) {
                u[i] = l[i] = d[i] = r[i] = 0;
            } else if (it != g[x].begin() and prev(it)->second >= l[i] - 1) {
                l[i] = prev(it)->second + 1;
                prev(it)->second = r[i];
            } else {
                g[x][l[i]] = r[i];
            }
        }

        int ans = 0;
        for (int x = 0; x < 2; x++) {
            for (auto [l, r] : g[x]) {
                ans += r - l + 1;
            }
        }

        cout << ans << "\n";
        for (int i = 0; i < n; i++) {
            cout << u[i] << ' ' << l[i] << ' ' << d[i] << ' ' << r[i] << "\n";
        }
    }

    return 0;
}