# A

# 题目大意

黑板上有 $0 \to n - 1$ 的整数，在一轮游戏中，小 $A$ 需要

• 选取一个 $a$ 并擦除
• 然后小 $B$ 选取一个 $b$，满足 $a+b \equiv 3 \pmod 4$ 并擦除

这个游戏从小 $A$ 开始，如果有一方不能操作了，则另一个人赢了，给你 $n$，请问谁能赢？

# 数据范围

• $1 \le n \le 100$

# 题解

我们观察有，满足条件的 a b 是 1 2 , 3 4 , 5 6 ... 连续的，而小 $B$ 想要赢，只有 0 .... (1+2), (3+4), (5+6) 这样结尾的才行，因为这样末尾的 $k+k+1$ 才能和第一个 $0$ 凑成一对，而中间的全是 $i + i + 1$，小 $A$ 拿一个，小 $B$ 就拿另一个，这样小 $B$ 就一定赢，其他情况都是输

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void solve () {
    cin >> n;

    cout << (mp[n - 1] ? "Bob\n" : "Alice\n");
}

signed main () {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    for (int i = 1; i <= 200; i += 2)
        mp[i + i + 1] = 1;

    int _ = 1;
    cin >> _;

    while(_--)
       solve();

    return 0;
}

# B

# 题目大意

有 $n$ 名选手参加了比赛，第 $i$ 名选手的实力是 $a_i$，现在要开始淘汰，淘汰规则是

• 每次随机选择两名选手
• 淘汰实力较低的选手，若实力相同，则随机淘汰一个

给定整数 $j$ 和 $k$，判断第 $j$ 个选手是否有可能成为最后剩下的 $k$ 名选手之一

# 数据范围

• $1 \le n \le 2 \times 10^5$

# 题解

只要 $j \neq \max_{i=1}^{n} a_i$ 时，$k \neq 1$ 即可，狗到最后！

1
2
3
4
5
6
7
8

void solve () {
    cin >> n >> j >> k;
    int maxx = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], maxx = max(maxx, a[i]);
    
    cout << (a[j] != maxx && k == 1 ? "No" : "Yes") << '\n';
}

# C

# 题目大意

给你一个由不同整数组成的数组 $a$，在一次操作中，你可以

• 选择 $a$ 的非空前缀，并用它的最小值替换
• 选择 $a$ 的非空后缀，并用它的最大值替换

对于每一个元素 $a_i$，是否能通过若干次的上面的操作，使得数组变成 $[a_i]$ 只有它一个？

# 数据范围

• $1 \le n \le 2 \times 10^5$

# 题解

维护一个 $preMin$ 数组和 $sufMax$ 数组，分别表示前 $i$ 个的最小值，和从 $i \to n$ 的最大值
对于 $a_i$ 来说，只要 aa[i] <= preMin[i - 1] || a[i] >= sufMax[i + 1] 即可完成题目要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void solve() {
    cin >> n;
    vector<int> a(n + 1), preMin(n + 1, 1e18), sufMax(n + 2, 0);
    for (int i = 1; i <= n; i++)
        cin >> a[i], preMin[i] = min(preMin[i - 1], a[i]);

    for (int i = n; i >= 1; i--)
        sufMax[i] = max(sufMax[i + 1], a[i]);

    for (int i = 1; i <= n; i++) {
        int l = preMin[i - 1], r = sufMax[i + 1];

        cout << (a[i] <= l || a[i] >= r ? 1 : 0);
    }

    cout << '\n';
}

# D

# 题目大意

给小 $A$ 和小 $B$ 一个长度为 $n$ 的二进制字符串 $s$ 和整数 $k~(1 \le k < n)$
如果小 $A$ 能将 $s$ 中的字符全部转换为 $0$，那么他就赢了，反之小 $B$ 赢

他们两个轮流操作，小 $A$ 先

• 如果是小 $A$ 的轮次，那么在 $s$ 中选择长度为 $k$ 的任意子序列（可以不连续），然后把这个子序列中的字符全部变成 $0$
• 如果是小 $B$ 的轮次，那么在 $s$ 中选择长度为 $k$ 的任意子串（必须连续），然后把这个子串中的全部字符全部变成 $1$

只要在操作过程中，全部变成了 $0$，那么小 $A$ 就赢了，请问当给定 $s$ 和 $k$ 的时候，谁会赢？

# 数据范围

• $1 \le t \le 10^4$
• $2 \le n \le 2 \times 10^5$

# 题解

首先我们可以统计 $1$ 的个数为 $cnt$

• 如果 $cnt \le k$，那么小 $A$ 一步就可以把字符串变为满足题目要求的字符串，故 $A$ 能赢
• 如果 $cnt > k$，我们发现，只要把原字符串的范围，能拆成 $[k], [n-2k], [k]$，只要中间的 $n-2k \ge 0$，那么小 $B$ 一定赢
  • 为什么捏？因为当我们的 $cnt > k$ 时，小 $A$ 第一次操作，一定可以变为 $cnt - k$ 个 $1$，那么这 $cnt - k$ 个 $1$ 肯定是分布在三个块之间的，小 $B$ 此时的最优策略，肯定是找左右两边 $1$ 较少的长度为 $k$ 的段，把他们全部变为 $1$，那么此时场上肯定会出现，一段 $k$ 全是 $1$，剩下两段里至少有 $1$ 的情况，此时小 $A$ 就不可能赢了
    

    1 2 3 4 5 6 7 8 9 10 11 12 13 14

    void solve () { int cnt = 0; cin >> n >> k; vector<char> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i], cnt += (a[i] == '1'); if (k >= cnt) { cout << "Alice\n"; return; } cout << (n >= 2 * k ? "Bob" : "Alice") << '\n'; }

# E

# 题目大意

定义数组的 $MEX$ 为数组中不存在的最小非负整数
现在给你一个长度为 $n$ 的非负整数数组 $a$，请你对于所有的 $k$，计算从 $a$ 中删除 $k~(k=0,1,...,n)$ 个值后 $MEX(a)$ 的所有可能的值

# 数据范围

# 题解

写这个题目，有一个启示
其实 vector 开数组，和 memset 初始化同样大小的数组的时候，是 memset 更快的，那为什么郑州寄了呢，实际上，寄的原因是，我一共开的是 $10^3 \times 10^3$ 的数组，每次 memset 都会对 $10^6$ 的数组都操作一下，而我有 $t$ 组，如果 $t$ 顶到了最大范围（也就是每次数据的 $n,m$ 其实很小），那肯定还是 $vector$ 动态开更快，所以我们要注意 $t$ 组数据时，如果都需要 $N$ 个，那么实际上还是 memset 快的

这题是差分，倘若答案是 $x$，那么最小操作次数是把 $x$ 全删了，最多操作次数是把 $\ge x$ 的全删了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int n;
vector<int> cnt(N), cf(N);

void solve () {
    cin >> n;

    for (int i = 0; i <= n; i++)
        cnt[i] = cf[i] = 0;
    
    for (int i = 1, x; i <= n; i++)
        cin >> x, cnt[x]++;

    for (int i = 0; i <= n; i++) {
        cf[cnt[i]]++, cf[n - i + 1]--;

        if (cnt[i] == 0)
            break;
    }

    cout << cf[0] << ' ';
    for (int i = 1; i <= n; i++)
        cf[i] += cf[i - 1], cout << cf[i] << ' ';

    cout << '\n';
}