Codeforces Round 926 (Div. 2)

比赛链接

A

[Codeforces 1929A] Sasha and the Beautiful Array.cpp >folded

#include <bits/stdc++.h>
// #define int long long
#define pb push_back
using std::cin, std::cout, std::string;
int read(int x = 0, int f = 0, char ch = getchar())
{
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}
const int N = 1e6 + 5;
const int INF = 1 << 30;
// const long long INF = 1LL << 60;
int a[N];
void solve()
{
    int n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    std::sort(a + 1, a + 1 + n);
    cout << a[n] - a[1] << '\n';
}

signed main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
#endif
    for (int T = read(); T--; solve());
    return 0;
}

B

>folded

C

>folded

D

题意：给定一棵树，选择一些点成为坏点，但限制是树上任意一条简单路径最多包含 2 个坏点，问你有多少种选法

首先对于一条树上路径 (u, v) 可以拆成 (u, lca) + (lca, v)，把视角转换到 lca 上。一个根向下到叶子的链只能是 0, 1, 2 三种，并且相加不大于 2

>folded

E

>folded