Codeforces Round 835 (Div. 4)

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

The most terrible enemy is no strong belief.

A. Medium Number

思路：

将三个数排序后，中间的那个输出即可

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

void solve() {
    int a[3];
    std::cin >> a[0] >> a[1] >> a[2];

    std::sort(a, a + 3);
    std::cout << a[1] << "\n";
}

B. Atilla's Favorite Problem

思路：

答案为 \(\Sigma_{i=0}^{n-1}max(s_i - 'a' + 1, ans)\)

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

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

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

    int ans = 0;
    for (char c : s) {
        ans = std::max(ans, c - 'a' + 1);
    }
    std::cout << ans << "\n";
}

C. Advantage

思路：

答案的序列为：当前值与除去当前值的最大值的差值

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

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

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

    std::vector<int> b = a;
    std::sort(b.begin(), b.end());

    for (int i = 0; i < n; i++) {
        if (a[i] != b[n - 1]) {
            std::cout << a[i] - b[n - 1] << " ";
        } else {
            std::cout << a[i] - b[n - 2] << " ";
        }
    }
    std::cout << "\n";
}

D. Challenging Valleys

思路：

只能存在山谷，不能是山峰，所以我们只需要找到那个最低点，然后判断 \(0 \sim pos_{min}\) 是不是递减，\(pos_{min} \sim n\) 是不是递增即可

时间复杂度：\(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];
    }
    if (std::is_sorted(a.begin(), a.end())) {
        std::cout << "YES\n";
        return ;
    }

    int min = 2E9, p = -1;
    for (int i = 0; i < n; i++) {
        if (a[i] < min) {
            min = a[i];
            p = i;
        }
    }

    if (std::is_sorted(a.begin(), a.begin() + p, std::greater())
    && std::is_sorted(a.begin() + p, a.end(), std::less())) {
        std::cout << "YES\n";
    return ;
    }
    std::cout << "NO\n";
}

E. Binary Inversions

题目大意：对于所有的 \((1 \le i \lt j \le n)\)，如果第 \(i\) 个位置是 \(a_i\)，第 \(j\) 个位置是 \(a_j\)，并且 \(a_i \gt a_j\)，就表示一个反转数

思路：

要让反转数尽可能的多，那么我们就需要预处理一个前缀和，表示：
1. \(zero[i]\)：前 \(i\) 个位置有多少个 \(0\)。
2. \(one[i]\)：前 \(i\) 个位置有多少个 \(1\)。
然后对于我们反转第 \(i\) 个位置，有两种情况：
1. 如果第 \(i\) 位最初是 \(0\)，那么我们将这个位置转换后的贡献是 \(zero[n]-zero[i]-one[i]\)
2. 如果第 \(i\) 位最初是 \(1\)，那么我们将这个位置转换后的贡献是 \(one[i-1]-(zero[n]-zero[i])\)

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

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

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

    std::vector<int> zero(n + 1), one(n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) {
            zero[i] = zero[i - 1] + 1;
            one[i] = one[i - 1];
        } else {
            one[i] = one[i - 1] + 1;
            zero[i] = zero[i - 1];
        }
    }

    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            ans += zero[n] - zero[i];
        }
    }
    i64 x = 0, y = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) {
            x = std::max(x, 1LL * zero[n] - zero[i] - one[i]);
            x = std::max(x, 0LL);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            y = std::max(y, 1LL * one[i - 1] - (zero[n] - zero[i]));
            y = std::max(y, 0LL);
        }
    }
    std::cout << std::max(ans + x, ans + y) << "\n";
}

F. Quests

思路：

首先，判断 \(Infinity\) 和 \(Imposible\)，如果收益最大的那个任务 \(d\) 次还不能达到目标要求，那么一定不可能
如果把序列里的前 \(min(n, d)\) 求和大于目标要求 \(c\)，那么说明 \(k\) 可以任意大
然后对于有解的情况，我们二分这个 \(k\) 值，对于这个任务周期为 \(k+1\)，完整周期有 \(\lfloor \frac{d}{k + 1} \rfloor\) 次，最后剩余的一个周期，取前 \(d \% (k + 1) - 1\) 个，这样保证 \(k\) 的最大值。

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

void solve() {
    i64 c;
    int n, d;
    std::cin >> n >> c >> d;

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

    std::sort(a.begin(), a.begin() + n, 
        [&](int i, int j) {
        return i > j;
    });

    if (a[0] * d < c) {
        std::cout << "Impossible\n";
        return ;
    }
    i64 sum = 0;
    for (int i = 0; i < std::min(n, d); i++) {
        sum += a[i];
    }
    if (sum >= c) {
        std::cout << "Infinity\n";
        return ;
    }
    for (int i = 1; i < n; i++) {
        a[i] += a[i - 1];
    }
    for (int i = n; i <= d; i++) {
        a[i] = a[i - 1];
    }

    auto check = [&](int x) {
        return a[x] * (d / (x + 1)) + (d % (x + 1) ? a[d % (x + 1) - 1] : 0) >= c;
    };

    int l = 0, r = d;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    std::cout << l << "\n";
}

G. SlavicG's Favorite Problem

思路：

可以传送 \(1\) 次，所以，我们从起点开始 \(dfs\)，然后记录路径中的每个点的值，然后从终点向起点再 \(dfs\)，当找到一个相同的值，就说明这个位置是可以传送过来的，所以我们只需要进行一次双向 \(dfs\) 即可。

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

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

    std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    std::set<int> st;
    std::vector<int> vis(n + 1);
    auto dfs1 = [&](auto self, int u, int fa, int x) -> bool {
        if (x == 0 && fa != -1) {
            return true;
        }
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (v == fa || vis[v]) continue ;
            st.insert(w ^ x);
            if (self(self, v, u, w ^ x)) {
                return true;
            }
        }
        vis[u] = false;
        return false;
    };
    vis.assign(n + 1, 0);
    auto dfs2 = [&](auto self, int u, int fa, int x) -> bool {
        if (x != 0 && u == b) {
            return false;
        } else if (x == 0 && u == b) {
            return true;
        }
        if (st.count(x) && fa != -1) {
            return true;
        }
        vis[u] = true;
        for (auto [v, w] : adj[u]) {
            if (v == fa || vis[v]) continue ;
            if (self(self, v, u, w ^ x)) {
                return true;
            }
        }
        vis[u] = false;
        return false;
    };
    if (dfs1(dfs1, b, -1, 0)) {
        std::cout << "YES\n";
    } else {
        if (dfs2(dfs2, a, -1, 0)) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
}