Codeforces Round 790 (Div. 4)

发表于 2024-05-08 更新于 2024-07-19 分类于题解阅读次数：本文字数： 1.2k 阅读时长 ≈ 4 分钟

Life is a challenge, meet it.

A. Lucky?

思路：

直接把前三位和后三位的求个和，然后比较一下就好了

时间复杂度：\(O(1)\)

void solve() {
    std::string s;
    std::cin >> s;

    std::cout << ((s[0] + s[1] + s[2] == s[3] + s[4] + s[5]) ? "YES\n" : "NO\n");
}

B. Equal Candies

思路：

要让所有的数相等，只需要把所有数和最小值做个差，然后求和一下就是最少的花费

时间复杂度：\(O(n)\)

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

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

    i64 ans = 0;
    int min = *min_element(a.begin(), a.end());
    for (int x : a) {
        ans += x - min;
    }
    std::cout << ans << "\n";
}

C. Most Similar Words

思路：

直接每一位的字符做差，然后求和即可

时间复杂度：\(O(n^2 \times len(s_i))\)

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

    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
    }

    int ans = 2E9;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int x = 0;
            for (int a = 0, b = 0; a < m && b < m; a++, b++) {
                x += abs(s[i][a] - s[j][b]);
            }
            ans = std::min(x, ans);
        }
    }
    std::cout << ans << "\n";
}

D. X-Sum

思路：

按照图形的形状模拟即可

时间复杂度：\(O(n \times m \times (n + m))\)

constexpr int dx[] {0, -1, -1, 1, 1};
constexpr int dy[] {0, 1, -1, -1, 1};

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

    std::vector<std::vector<int>> g(n, std::vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            std::cin >> g[i][j];
        }
    }

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            i64 sum = 0;
            auto extend = [&](int x, int y) {
                int a = x, b = y;
                sum += g[a][b];
                while (a > 0 && b > 0) {
                    a--, b--;
                    sum += g[a][b];
                }
                a = x, b = y;
                while (a + 1 < n && b + 1 < m) {
                    a++, b++;
                    sum += g[a][b];
                }
                a = x, b = y;
                while (a > 0 && b + 1 < m) {
                    a--, b++;
                    sum += g[a][b];
                }
                a = x, b = y;
                while (a + 1 < n && b > 0) {
                    a++, b--;
                    sum += g[a][b];
                }
            };
            extend(i, j);
            ans = std::max(ans, sum);
        }
    }
    std::cout << ans << "\n";
}

E. Eating Queries

思路：

可以直接对所有的数降序排序后，然后求个前缀和，最后二分，因为要求的是最少数量，只需要找到当前是第个位置即可

时间复杂度：\(O(nlogn + q \times logn)\)

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

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

    std::sort(x.rbegin(), x.rend());

    std::vector<i64> s(n + 1);
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] + x[i];
    }

    while (q--) {
        int val;
        std::cin >> val;

        if (s[n] < val) {
            std::cout << "-1\n";
            continue ;
        }

        std::cout << std::lower_bound(s.begin(), s.end(), val) - s.begin() << "\n";
    }
}

F. Longest Strike

思路：

直接模拟，我们找到数量大于 \(k\) 的一个连续最大的连续子段即可

时间复杂度：\(O(n + m)\)

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

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

    std::map<int, int> mp;
    for (int i = 0; i < n; i++) {
        mp[a[i]]++;
    }

    std::vector<int> p;
    for (auto [x, y] : mp) {
        if (y >= k) {
            p.push_back(x);
        }
    }

    if (p.empty()) {
        std::cout << "-1\n";
        return ;
    }

    int ansl = p[0], ansr = p[0];
    int l = p[0], r = p[0], mx = 0;
    int m = p.size(), len = 1;
    for (int i = 0; i + 1 < m; i++) {
        if (p[i] + 1 == p[i + 1]) {
            len++;
            r = p[i + 1];
            if (len > mx) {
                mx = len;
                ansl = l;
                ansr = r;
            }
        } else {
            l = p[i + 1];
            r = p[i + 1];
            len = 1;
        }
    }
    std::cout << ansl << " " << ansr << "\n";
}

G. White-Black Balanced Subtrees

思路：

树的遍历模板题，我们只需要维护出一个子树上白色点(W)和黑色点(B) 的数量，然后再遍历一遍进行判断并且统计即可

时间复杂度：\(O(n)\)

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

    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int x;
        std::cin >> x;
        x--;

        adj[x].push_back(i);
        adj[i].push_back(x);
    }

    std::string s;
    std::cin >> s;

    std::vector<int> B(n), W(n);
    auto dfs1 = [&](auto self, int u, int fa) -> void {
        s[u] == 'B' ? B[u] = 1 : W[u] = 1;
        for (int x : adj[u]) {
            if (x == fa) continue ;
            self(self, x, u);
            B[u] += B[x];
            W[u] += W[x];
        }
    };
    dfs1(dfs1, 0, -1);

    int ans = 0;
    auto dfs2 = [&](auto self, int u, int fa) -> void {
        if (B[u] == W[u]) ans++;
        for (int x : adj[u]) {
            if (x == fa) continue ;
            self(self, x, u);
        }
    };
    dfs2(dfs2, 0, -1);
    
    std::cout << ans << "\n";
}

H. Maximum Crossings

思路：

本题只需要求出序列里面逆序对的数量，然后把同一个区间存在的多个点除外的其他点的方案数给统计一下就可以了
对于一个区间里不重复的点的方案数：它的方案数为 \(\frac{(num_{now} - 1) \times num_{now}}{2}\)
对于求一个序列中逆序对个数的方法，我们可以使用树状数组或者归并排序

时间复杂度：\(O(nlogn)\)

/*
树状数组板子
*/

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

    std::vector<std::pair<int, int>> a(n);
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a[i] = {x, i};
    }

    std::sort(a.begin(), a.end(), [&](auto i, auto j) {
        if (i.first == j.first) {
            return i.second < j.second;
        }
        return i.first < j.first;
    });

    Fenwick<int> fen(n);
    std::vector<int> rank(n);
    for (int i = 0; i < n; i++) {
        rank[a[i].second] = i;
    }

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        fen.add(rank[i], 1);
        ans += i - fen.sum(rank[i]);
    }

    i64 cur = 1;
    for (int i = 1; i < n; i++) {
        if (a[i].first != a[i - 1].first) {
            ans += (cur * (cur - 1)) / 2;
            cur = 1;
        } else {
            cur++;
        }
    }
    ans += cur * (cur - 1) / 2;
    std::cout << ans << "\n";
}