Codeforces Round 975 (Div. 2)

A. Max Plus Size

题意

求奇数位之和和偶数位之和的最大值

题解

略

代码

#include <bits/stdc++.h>

using ll = long long;

void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    int mx = 0, ans = 0, cnt = 0;
    for (int i = 0; i < n; i += 2) {
        mx = std::max(mx, a[i]);
        cnt++;
    }
    ans = std::max(ans, cnt + mx);
    mx = 0, cnt = 0;
    for (int i = 1; i < n; i += 2) {
        mx = std::max(mx, a[i]);
        cnt++;
    }
    ans = std::max(mx + cnt, ans);
    std::cout << ans << "\n";
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0);
    int tt;
    std::cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

B. All Pairs Segments

题意

在数轴上给出个不同的特殊点，两两之间有一条线段，问这些点中有多少个点恰好被条线段覆盖。

题解

每两个特殊点中间的点被覆盖次数即左右两边特殊点的个数之积，特殊点所被覆盖次数为左右两边特殊点的个数（不包括自己）之积再加上。

代码

#include <bits/stdc++.h>

using ll = long long;

void solve()
{
    int n, q;
    std::cin >> n >> q;
    std::vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    std::unordered_map<ll, ll> mp;

    auto calc = [&](ll x) -> ll { return (x - 1) * (n - x + 1); };

    for (int i = 2; i <= n; i++) {
        mp[calc(i)] += a[i] - a[i - 1] - 1;
    }
    for (int i = 1; i <= n; i++) {
        mp[calc(i) + 1ll * (n - i)]++;
    }
    while (q--) {
        ll k;
        std::cin >> k;
        std::cout << mp[k] << " \n"[q == 0];
    }
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0);
    int tt;
    std::cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

C. Cards Partition

题意

给出种卡牌，每种牌有张，现在有次购买任意一张牌的机会，求最大能够组成多大的deck。要求每个deck种牌的种类互不相同且所有deck的大小相等，并且所有的牌都要属于一个deck。

题解

deck的大小肯定不大于，考虑从大到小枚举答案。

deck的大小一定能够整除最终卡牌的数量即，同时需要满足。

还有一个需要满足的条件是 $的数量$ ，否则根据抽屉原理一定有一个deck中包含相同的卡牌。

时间复杂度：。

代码

#include <bits/stdc++.h>

using ll = long long;

void solve()
{
    ll n, k;
    std::cin >> n >> k;
    std::vector<ll> a(n + 1);
    ll sum = 0;
    for (int i = 1; i <= n; i++) std::cin >> a[i], sum += a[i];
    sort(a.begin() + 1, a.end(), [&](int x, int y) { return x > y; });
    ll mx = *std::max_element(a.begin() + 1, a.end());

    auto check = [&](int x) -> bool { return (sum + k) / x >= mx && (x - sum % x) % x <= k; };

    for (int i = n; i >= 1; i--) {
        if (check(i)) {
            std::cout << i << "\n";
            return;
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0);
    int tt;
    std::cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

D. Speedbreaker

全场mvp，通过数量不到 E 的一半。

题意

一排有个城市，从左到右编号为。

在 1 时刻，你正好征服了一座城市，称为起始城市。
在 2,3,…,n 时刻，你可以选择一个与迄今为止征服的城市相邻的城市并征服它。

如果在每个 i 中，你在不晚于的时间征服了城市 i ，那么你就赢了。获胜策略可能存在，也可能不存在，这也取决于起始城市。有多少个起始城市可以让你获胜？

题解

首先如果单独考虑某一个点，则能在时刻之前到达该点的区间为，因此合法的点所组成的区间一定位于。

不妨大胆猜想这个就是答案。

代入样例发现这个做法在第二个样例处（）错误，因此充分性不满足。

通过观察这一组“奇怪的”样例，发现有两个 5 它们的距离是 5，也就是位于一个长度至少为 6 的区间，无论从哪个点出发都不能在合法时间内遍历到这两个点。

实际上，对于时间内能够到达的点来将，包含它们的区间长度一定不大于，也就是

满足上述两个条件的点就是所有满足条件的起始点。

证明说不太清楚，参考种树。但是第二个条件如果满足的话，在满足第一个条件的点中任意找一个点作为起始点，优先向剩余时间少的点走一定不劣，从而策略一定存在。

时间复杂度：。

代码

#include <bits/stdc++.h>

using ll = long long;

void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    int l = 1, r = n;
    std::vector<std::vector<int>> mp(n + 1);
    for (int i = 1; i <= n; i++) {
        l = std::max(l, i - a[i] + 1);
        r = std::min(r, i + a[i] - 1);
        mp[a[i]].push_back(i);
    }
    int L = n, R = 1;
    for (int i = 1; i <= n; i++) {
        if (mp[i].empty()) continue;
        L = std::min(L, mp[i][0]);
        R = std::max(R, mp[i].back());
        if (R - L + 1 > i) {
            std::cout << 0 << '\n';
            return;
        }
    }
    std::cout << std::max(0, r - l + 1) << '\n';
}
int main()
{
    std::ios::sync_with_stdio(false), std::cin.tie(0);
    int tt;
    std::cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

E. Tree Pruning

题意

给定一棵大小为树，每次可以删除一个叶子节点以及它所连的边，问最少需要多少次这样的操作能够使树上剩下的所有叶子节点全在同一深度（根节点为1号节点）。

题解

以样例为例来说明

在这棵树上，最少可以删除 5 条边使得所有叶子节点的深度相同，分别是 11，9，3，10，4。最终的叶子节点深度均为4.

可以发现我们删除的点并不都是深度大于最后深度的节点，也有小于最后深度的节点，例如4，10.

如果我们枚举最终的深度，则在原图上所有深度大于该深度的点都需要被删除，可以通过统计子树大小的方式来得到答案。

至于深度小于最终深度的叶子节点，如果我们从这些叶子节点向上考虑，还需要维护到第一个子树深度大于当前枚举深度的祖先，很难在有限时间复杂度内实现。

但是这给我们一个启发，如果处理出每个节点的中儿子能够到达的最大深度，那么如果该节点的儿子都不能达到当前枚举的深度，那么可以将当前节点的子树全部删除，这样仍然只用维护子树大小和子树所能到的最大深度，一遍dfs 即可。注意用差分将这里的贡献加到大于当前枚举深度的答案中。

时间复杂度：。

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define PII pair<int, int>
#define pi acos(-1.0)

void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> G(n + 1);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    vector<int> sz(n + 1), dep(n + 1), up(n + 1), son_dep(n + 1);
    vector<int> ans(n + 1), b(n + 2);
    int mx_dep = 0;

    auto dfs = [&](auto dfs, int u, int fa) -> void {
        sz[u] = 1;
        son_dep[u] = dep[u];
        mx_dep = max(dep[u], mx_dep);
        for (int v : G[u]) {
            if (v == fa) continue;
            dep[v] = dep[u] + 1;
            dfs(dfs, v, u);
            sz[u] += sz[v];
            son_dep[u] = max(son_dep[v], son_dep[u]);
        }
        ans[dep[u]] += sz[u] - 1;
        b[son_dep[u] + 1]++;
    };

    dfs(dfs, 1, 0);

    for (int i = 1; i <= mx_dep; i++) {
        b[i] += b[i - 1];
    }

    for (int i = 0; i <= mx_dep; i++) ans[i] += b[i];

    cout << *min_element(ans.begin(), ans.begin() + mx_dep + 1) << endl;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。