Codeforces Round 968 (Div. 2)

A

拆成两个，直接判断首尾是否相同。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
const int N = 1e6 + 100;
const int mod = 1e9 + 7;
const int inf = 1e9;
const int minf = -1e9;
int n;
void Totoro()
{
    cin >> n;
    string s;
    cin >> s;
    if (s[0] == s[s.length() - 1])
    {
        cout << "No" << '\n';
    }
    else
    {
        cout << "Yes" << '\n';
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}

B

由于这个相当于每次去掉一个数字，一个人会挑选最大的数字丢弃，一个人会挑选最小的数字丢弃，因此最后剩下的就是中位数了。如果是偶数就是比较大的那一个。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
const int N = 1e6 + 100;
const int mod = 1e9 + 7;
const int inf = 1e9;
const int minf = -1e9;
int n;
void Totoro()
{
    cin >> n;
    vector<int> a(n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    sort(a.begin()+1, a.end());
    if (n % 2 == 0)
    {
        cout << a[n/2+1 ] << '\n';
    }
    else
    {
        cout << a[n/2+1] << '\n';
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}

C

贪心：尽量不一样的放。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
const int N = 1e6 + 100;
const int mod = 1e9 + 7;
const int inf = 1e9;
const int minf = -1e9;
int n;
struct node
{
    char c;
    int cnt;
} c[N];
bool vis[30];
int cnt[30];
bool cmp(node a, node b)
{
    return a.cnt < b.cnt;
}
void Totoro()
{
    for (int i = 0; i <= 26; i++)
    {
        cnt[i] = 0;
    }
    cin >> n;
    string s;
    cin >> s;
    for (auto c : s)
    {
        cnt[c - 'a' + 1]++;
    }
    int k = 0;
    for (int i = 1; i <= 26; i++)
    {
        if (cnt[i] == 0)
        {
            continue;
        }
        c[++k].cnt = cnt[i];
        c[k].c = 'a' + i - 1;
    }
    sort(c + 1, c + 1 + k, cmp);
    string ans;
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            if (c[j].cnt)
            {
                ans += c[j].c;
                c[j].cnt--;
            }
        }
    }
    cout << ans << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}

D1

直接模拟找最大的mex，感觉难度小于C。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void Totoro()
{
    int n, m;
    cin >> n >> m;
    int x = 0;
    for (int i = 1; i <= n; i++)
    {
        int l;
        cin >> l;
        vector<int> cnt(l + 2);
        for (int j = 1; j <= l; j++)
        {
            int c;
            cin >> c;
            if (c <= l + 1)
            {
                cnt[c]++;
            }
        }
        int a = 0;
        while (cnt[a] > 0)
        {
            a++;
        }
        a++;
        while (cnt[a] > 0)
        {
            a++;
        }
        x = max(x, a);
    }
    i64 ans = 0;
    if (m >= x)
    {
        ans = 1ll * x * (x + 1) + 1ll * (m - x) * (m + x + 1) / 2;
    }
    else
    {
        ans = 1ll * x * (m + 1);
    }
    cout << ans << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        Totoro();
    }
}