比赛链接：Codeforces Round 950 (Div.3)

A. Problem Generator

读入的时候统计各种难度的数量，数量少于 $m$ 的，统计少了多少。

时间复杂度： $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int main()
{
    int t = read();
    while (t--)
    {
        int vis[10];
        memset(vis, 0, sizeof(vis));
        int n = read(), m = read();
        string s;
        cin >> s;
        for (int i = 0; i < s.length(); i++)
            vis[s[i] - 'A']++;
        int num = 0;
        for (int i = 0; i <= 'G' - 'A'; i++)
        {
            if (vis[i] < m)
                num += m - vis[i]; // 统计个数
        }
        cout << num << endl;
    }
    return 0;
}

B. Choosing Cubes

分别记下大于第 $f$ 位和等于第 $f$ 位的数的数量，根据数量关系判断（具体看代码）。

时间复杂度： $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;

int t, n, f, k, a[105];

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int main()
{
    t = read();
    while (t--)
    {
        n = read(), f = read(), k = read();
        int num1 = 0, num2 = 0;
        for (int i = 1; i <= n; i++)
            a[i] = read();
        for (int i = 1; i <= n; i++)
        {
            if (a[i] > a[f])
                num1++;
            else if (a[i] == a[f])
                num2++;
        }
        if (num1 + num2 <= k)
            printf("YES\n");
        else if (num1 >= k)
            printf("NO\n");
        else
            printf("MAYBE\n");
    }
    return 0;
}

C. Sofia and the Lost Operations

分别判断 $d[m]$ 是否出现在 $b$ 数组里面以及 $b$ 数组与 $a$ 数组不同的值是否能在 $d$ 数组里面找到。

时间复杂度： $O(n \log n)$ 。

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2e5 + 10;
int t, n, m, a[N], b[N], d[N], vis[N];

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}

signed main()
{
    t = read();
    while (t--)
    {
        n = read();
        int flag = 0;
        for (int i = 1; i <= n; i++)
            a[i] = read();
        for (int i = 1; i <= n; i++)
            b[i] = read();
        m = read();
        for (int i = 1; i <= m; i++)
            d[i] = read();
        int p = 0;
        for (int i = 1; i <= n; i++)
        {
            if (a[i] != b[i])
                vis[++p] = b[i];
            if (b[i] == d[m])
                flag = 1;
        }
        sort(d + 1, d + m + 1), sort(vis + 1, vis + p + 1);
        int p1 = 1, p2 = 1;
        while (p1 <= p && p2 <= m)
        {
            if (vis[p1] == d[p2])
                p1++, p2++;
            else
                p2++;
        }
        if (flag && p1 == p + 1)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

D. GCD-sequence

从 $b$ 数组递减的位置，分别删去对应的 $a$ 数组的元素，再生成新的 GCD 序列，判断新序列是否不递减。

时间复杂度： $O(n)$ 。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int t, n;
vector<int> a(N);

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int gcd(int a, int b)
{
    return a == 0 ? b : gcd(b % a, a);
}

bool check(int x)
{
    if (x < 0 || x > n - 1)
        return false;
    vector<int> c = a;
    vector<int> d;
    c.erase(c.begin() + x);
    for (int i = 0; i < n - 2; i++)
    {
        d.push_back(gcd(c[i], c[i + 1]));
        if (i && d[i] < d[i - 1])
            return false;
    }
    return true;
}

void solve()
{
    n = read();
    vector<int> b;
    for (int i = 0; i < n; i++)
        a[i] = read();
    for (int i = 0; i < n - 1; i++)
        b.push_back(gcd(a[i], a[i + 1]));
    for (int i = 0; i < n - 2; i++)
    {
        if (b[i] > b[i + 1])
        {
            if (check(i - 1) || check(i) || check(i + 1) || check(i + 2))
                puts("YES");
            else
                puts("NO");
            return;
        }
    }
    puts("YES");
}

int main()
{
    t = read();
    while (t--)
        solve();
    return 0;
}