当前位置：首页 > article >正文

Codeforces Round 975 (Div. 2)（A，B，C，D线段树解法，E）

article 2024/10/1 0:39:58

比赛链接

https://codeforces.com/contest/2019

A题

思路

分别求出奇数位和偶数位的最大值，之后进行比较即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2 + 5;
int n;
int a[N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int maxx1 = 0, maxx2 = 0, ans1 = 0, ans2 = 0;
    for (int i = 1, j = 2; i <= n; i += 2, j += 2)
    {
        maxx1 = max(maxx1, a[i]);
        ans1++;
        if (j <= n)
        {
            ans2++;
            maxx2 = max(maxx2, a[j]);
        }
    }
    cout << max(maxx1 + ans1, maxx2 + ans2) << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}

B题

思路

我们考虑预处理出每一个区间对答案产生的贡献。考虑每个区间以第 $a_{i}$ 个为端点，到 $a_{i+1}$ 中间的数对答案产生的贡献。

对第 $i$ 个端点的贡献和为 $(n-i+1)\times (i-1) + (n-i)$ ，即以 $a_{i}$ 为端点产生的贡献。

对第 $a_{i}+1$ 到 $a_{i+1}$ 之间的数对答案产生的贡献为 $i\times (n-i)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, q, k;
int a[N];
void solve()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    map<int, int> mp;
    mp[n - 1] += (a[2] - a[1]);
    mp[n - 1]++;
    for (int i = 2; i < n; i++)
    {
        int op = n - i + 1;
        int cnt = i - 1;
        mp[cnt * op + (n - i)]++;
        mp[(op - 1) * (cnt + 1)] += (a[i + 1] - a[i] - 1);
    }
    while (q--)
    {
        cin >> k;
        cout << mp[k] << " ";
    }
    cout << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}

C题

思路

可以分两种情况进行讨论。

根据题意，我们最多可以将卡牌分为 $n$ 组。

我们规定 $s u m$ 表示原先卡牌个数的总和， $ma xx$ 表示卡牌个数最多的那个卡牌类型的数量。

当 $k = 0$ 的时候，只需要对原先的卡牌进行分组即可。我们假设可以将每 $i$ 个卡牌分为一组，如果 $\% i == 0$ 并且 $\ge maxx$ ，则可以将卡牌分为每 $i$ 个一组。我们直接对答案进行暴力枚举即可。

当 $k > 0$ 的时候，我们依旧假设可以将每 $i$ 个卡牌分为一组，对于我们最后一组的卡牌，会有 $\% i$ 个，如果我们想要将其补全，需要再添加 $\% i$ 个卡牌。如果 $k < o p$ ，则不可将卡牌分为每 $i$ 个一组。否则，我们令 $res = (s u m + o p) / i + (k - o p) / i$ ，如果 $\ge maxx$ ，则 $i$ 为可行的答案。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, k, sum;
int a[N];
void solve()
{
    cin >> n >> k;
    sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    int maxx = *max_element(a + 1, a + 1 + n);
    if (k == 0)
    {
        int ans = 1;
        for (int i = 1; i <= n; i++)
        {
            if (sum % i == 0 && sum / i >= maxx)
            {
                ans = i;
            }
        }
        cout << ans << endl;
    }
    else
    {
        int ans = 1;
        for (int i = 2; i <= n; i++)
        {
            int op = i - sum % i;
            if (op == i)
                op = 0;
            if (op > k)
                continue;
            int res = (sum + op) / i + (k - op) / i;
            if (res < maxx)
                continue;
            ans = i;
        }
        cout << ans << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}

D题

思路

这里提供一个线段树的做法。

我们假设以点 $i$ 为起点，向两端不断扩散。对于 $i$ 点左边的点 $j$ ，其必须在 $j$ 点左端的点前被征服。对于 $i$ 点右边的点 $k$ ，其必须在 $k$ 点右端的点前被征服。

因此，我们可以预处理出前缀最小值和后缀最小值。

对于每一个起点 $i$ ，必然有一套单独的 $v ec t or < in t > df n$ 表示每一个点最晚可以在什么时刻被征服，而这个 $df n$ 值便是前面说的 $i$ 点左边点的前缀最小值，和 $i$ 点右边点的后缀最小值。

我们对于每一个 $dfn_{i}$ ，将区间 $dfn_{i},n]$ 全部加上一个正整数 $1$ 。表示在 $dfn_{i},n]$ 这个时间节段的每一个节点已经被征服了多少个点。

处理完 $df n$ 之后，我们对 $1$ 到 $n$ 的区间，每一个点都减去对应的时间。即第 $i$ 个点减去 $i$ 。

如果最后出现大于 $0$ 的情况，则表示第 $i$ 个点无法作为起点。

因此我们可以用线段树动态维护区间最大值，区间查询操作为加减，枚举每一个 $i$ 作为起点时是否可行，直接统计答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
int a[N], nxt[N];
vector<int>p(N);
struct segmenttree
{
    struct node
    {
        int l, r, maxx, tag;
    };
    vector<node>tree;

    segmenttree(): tree(1) {}
    segmenttree(int n): tree(n * 4 + 1) {}

    void pushup(int u)
    {
        auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];
        root.maxx = max(left.maxx, right.maxx);
    }

    void pushdown(int u)
    {
        auto &root = tree[u], &left = tree[u << 1], &right = tree[u << 1 | 1];
        if (root.tag != 0)
        {
            left.tag += root.tag;
            right.tag += root.tag;
            left.maxx = left.maxx + root.tag;
            right.maxx = right.maxx + root.tag;
            root.tag = 0;
        }
    }

    void build(int u, int l, int r)
    {
        auto &root = tree[u];
        root = {l, r};
        if (l == r)
        {
            root.maxx = -p[r];
        }
        else
        {
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }

    void modify(int u, int l, int r, int val)
    {
        auto &root = tree[u];
        if (root.l >= l && root.r <= r)
        {
            root.maxx += val;
            root.tag += val;
            return;
        }
        pushdown(u);
        int mid = root.l + root.r >> 1;
        if (l <= mid) modify(u << 1, l, r, val);
        if (r > mid) modify(u << 1 | 1, l, r, val);
        pushup(u);
    }

    int query(int u, int l, int r)
    {
        auto &root = tree[u];
        if (root.l >= l && root.r <= r)
        {
            return root.maxx;
        }
        pushdown(u);
        int mid = root.l + root.r >> 1;
        int res = -inf;
        if (l <= mid) res = query(u << 1, l, r);
        if (r > mid) res = max(res, query(u << 1 | 1, l, r));
        return res;
    }
};
void init()
{
    iota(p.begin(), p.end(), 0);
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    segmenttree smt(n);
    smt.build(1, 1, n);

    nxt[n] = a[n];
    for (int i = n - 1; i >= 1; i--)
    {
        nxt[i] = min(nxt[i + 1], a[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        smt.modify(1, nxt[i], n, 1);
    }
    int ans = 0, last = inf;
    for (int i = 1; i <= n; i++)
    {
        smt.modify(1, nxt[i], n, -1);
        smt.modify(1, 1, n, 1);
        if (smt.query(1, 1, n) <= 0) ans++;
        smt.modify(1, 1, n, -1);
        last = min(last, a[i]);
        smt.modify(1, last, n, 1);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    cin >> test;
    init();
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}

E题

思路

统计每一个节点所能到达的最大深度。

枚举以第 $i$ 层为结果计算答案，则第 $i$ 层的答案为深度 $> i$ 的节点的个数 $+$ 最大深度 $< i$ 的节点的个数。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n;
int depth[N], maxdeep[N], cnt[N], pre[N];
vector<int> mp[N];
void dfs(int u, int fu, int deep)
{
    depth[u] = deep;
    maxdeep[u] = deep;
    cnt[deep]++;
    for (int j : mp[u])
    {
        if (j == fu) continue;
        dfs(j, u, deep + 1);
        maxdeep[u] = max(maxdeep[u], maxdeep[j]);
    }
}
void solve()
{
    cin >> n;
    for (int i = 0; i <= n; i++)
    {
        depth[i] = maxdeep[i] = cnt[i] = pre[i] = 0;
        mp[i].clear();
    }
    for (int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        mp[u].push_back(v);
        mp[v].push_back(u);
    }
    dfs(1, -1, 1);
    for (int i = 1; i <= n; i++)
    {
        pre[maxdeep[i]]++;
        cnt[i] += cnt[i - 1];
    }
    int ans = inf;
    for (int i = 1; i <= n; i++)
    {
        pre[i] += pre[i - 1];
        ans = min(ans, pre[i - 1] + n - cnt[i]);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}