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

A - Eating Game#

关键词：签到，贪心

思路#

可能成为获胜者的玩家数量，也就是初始时菜最多的玩家，在给定数组中找出所有值最大的元素，记录数量即为答案。

Code#

1
// Problem: CF 2200 A
2
// Contest: Codeforces - Codeforces Round 1084 (Div. 3)
3
// URL: https://codeforces.com/contest/2200/problem/A
4
// Time: 2026-04-27 13:43:40
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
const int inf = 0x3f3f3f3f;
9

10
void solve()
11
{
12
    int n;
13
    cin >> n;
14

15
    vector<int> a(n + 1);
16

17
    int mx = -1;
18
    for (int i = 1; i <= n; i++)
19
    {
20
        cin >> a[i];
21
        mx = max(mx, a[i]);
22
    }
23

24
    int res = 0;
25
    for (int i = 1; i <= n; i++)
26
    {
27
        if (a[i] == mx)
28
        {
29
            res++;
30
        }
31
    }
32

33
    cout << res << '\n';
34
}
35

36
int main()
37
{
38
    int T;
39
    cin >> T;
40

41
    while (T--)
42
        solve();
43

44
    return 0;
45
}

B - Deletion Sort#

关键词：思维，贪心

思路#

假如给定数组直接是单调不降的，那么游戏直接结束，输出n即可。

否则一定存在某个 $i$ ，使得 $a_i>a_{i+1}$ ，我们可以删除这两个数之外的所有元素，然后删除 $a_i$ ，最后只会剩下一个元素，因此答案为1

Code#

1
// Problem: CF 2200 B
2
// Contest: Codeforces - Codeforces Round 1084 (Div. 3)
3
// URL: https://codeforces.com/contest/2200/problem/B
4
// Time: 2026-04-27 13:43:41
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
void solve()
9
{
10
    int n;
11
    cin >> n;
12

13
    vector<int> a(n), b(n);
14
    for (int i = 0; i < n; i++)
15
        cin >> a[i];
16

17
    b = a;
18
    sort(b.begin(), b.end());
19

20
    if (b == a)
21
        cout << a.size() << endl;
22
    else
23
        cout << 1 << endl;
24
}
25

26
int main()
27
{
28
    int T;
29
    cin >> T;
30

31
    while (T--)
32
        solve();
33
    return 0;
34
}

C - Specialty String#

关键词：思维

思路#

题目要求将相同的字符替换为*，实际上就是删除这些字符，假如字符串变为空就可以获胜。由于删除一对字符不会干扰另一对字符，因此操作顺序无所谓。

遍历数组 $\frac{n}{2}$ 次，每找到一对相等元素就删掉它，最后只需要输出字符串是否为空即可。

也可以用栈来模拟。

Code#

stack#

1
// Problem: CF 2200 C
2
// Contest: Codeforces - Codeforces Round 1084 (Div. 3)
3
// URL: https://codeforces.com/contest/2200/problem/C
4
// Time: 2026-04-27 13:43:42
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
void solve()
9
{
10
    int n;
11
    string s;
12
    cin >> n >> s;
13

14
    stack<char> stk;
15

16
    for (int i = 0; i < n; i++)
17
    {
18
        if (stk.empty())
19
        {
20
            stk.push(s[i]);
21
            continue;
22
        }
23

24
        if (s[i] == stk.top())
25
        {
26
            stk.pop();
27
        }
28
        else
29
            stk.push(s[i]);
30
    }
31

32
    if (stk.empty())
33
        cout << "YES" << endl;
34
    else
35
        cout << "NO" << endl;
36
}
37

38
int main()
39
{
40
    int T;
41
    cin >> T;
42

43
    while (T--)
44
        solve();
45

46
    return 0;
47
}

normal#

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

4
#define endl '\n'
5

6
typedef long long ll;
7
typedef unsigned long long ull;
8
typedef pair<int, int> pii;
9
typedef pair<double, double> pdd;
10
typedef pair<long long, long long> pll;
11

12
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
13
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
14
const int inf = 0x3f3f3f3f;
15
const int N = 0;
16

17
void solve()
18
{
19
    int n;
20
    string s;
21
    cin >> n >> s;
22

23
    for (int i = 0; i * 2 < n; i++)
24
        for (int j = 1; j < s.size(); j++)
25
            if (s[j] == s[j - 1])
26
                s.erase(j - 1, 2);
27

28
    cout << (s.empty() ? "YES" : "NO") << endl;
29
}
30

31
int main()
32
{
33
    int T;
34
    cin >> T;
35

36
    while (T--)
37
        solve();
38

39
    return 0;
40
}

D - Portal#

关键词：思维、排序

思路#

不要把整个数组看成一个数组，而是看成两个部分：在传送门里的和在传送门外的。

假设 $A$ 表示两个传送门间的子数组， $B$ 表示剩余的元素，进行传送操作，实际上就是对传送门里面的数组 $A$ 进行循环移位。

考虑经过传送操作后，整个数组的情况：实际上就是将 $A$ 内部的元素不断循环移位，将 $A$ 在整个数组中的位置不断改变，并且不改变 $B$ 中元素及其顺序。换句话说，传送门之间的元素不能跑出去。

要得到字典序最小的排列，我们从两个方面考虑， $A$ 数组的内部情况和它在数组中的位置：

内部：贪心地移动 $A$ 数组，直到它最左端的元素最小
外部：将内部排好序的 $A$ 接在第一个大于 $A$ 的最小值的元素左侧。假如不存在这样的元素，就插到 $B$ 的后面

NOTE
注意循环移位操作的写法：
if (!b.empty()) rotate(b.begin(), min_element(b.begin(), b.end()), b.end());
rotate()函数有三个参数：first，middle，last，均为迭代器。它会交换范围 [first, last) 中的元素，使得 [first, middle) 中的元素被放置在 [middle, last) 中的元素之后，同时保持两个范围中元素的顺序。
min_element()函数可以自定义比较规则，格式为min_element(first, last, comp)，传入两个迭代器。

Code#

1
// Problem: CF 2200 D
2
// Contest: Codeforces - Codeforces Round 1084 (Div. 3)
3
// URL: https://codeforces.com/contest/2200/problem/D
4
// Time: 2026-04-27 13:43:43
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
void solve()
9
{
10
    int n, x, y;
11
    cin >> n >> x >> y;
12

13
    vector<int> a, b;
14
    for (int i = 1; i <= n; i++)
15
    {
16
        int t;
17
        cin >> t;
18

19
        if (i > x && i <= y)
20
            b.push_back(t);
21
        else
22
            a.push_back(t);
23
    }
24

25
    if (!b.empty()) // 循环移位
26
        rotate(b.begin(), min_element(b.begin(), b.end()), b.end());
27

28
    int idx = (int) a.size(); // 应该默认插在最后
29
    for (int i = 0; i < (int) a.size(); i++)
30
    {
31
        if (a[i] > b[0])
32
        {
33
            idx = i;
34
            break;
35
        }
36
    }
37

38
    for (int i = 0; i < idx; i++)
39
        cout << a[i] << " ";
40

41
    for (auto i: b)
42
        cout << i << " ";
43

44
    for (int i = idx; i < (int) a.size(); i++)
45
        cout << a[i] << " ";
46

47
    cout << endl;
48
}
49

50
int main()
51
{
52
    int T;
53
    cin >> T;
54

55
    while (T--)
56
        solve();
57

58
    return 0;
59
}

E - Divisise Battle#

关键词：博弈论、数论

思路#

首先考虑在什么情况下可以对某个数进行操作：我们要把一个数拆成两个大于 $1$ 并小于这个数的两个数，当且仅当这个数不是 $1$ 和质数。

然后考虑我们要怎么操作这个数：

我们首先假设 $x$ 能被两个质数 $p,q$ 整除，其中 $p<q$ ，那么先手的那个人可以将 $x$ 替换为 $\frac{x}{p}$ 和 $p$ 。由于 $\frac{x}{p}$ 是 $q$ 的倍数，总会在 $p$ 之前出现一个大于 $p$ 的 $q$ 的倍数，因此该数组永远不会成为单调不降序列，所以只要给定数组存在这样的一个数，先手采取这种拆分策略是必胜的。

我们考虑，假如数组中不存在符合这样条件的 $x$ 怎么办？那么数组中所有元素要么是 $1$ ，要么都是某一个质数的幂，我们考虑找出这些数对应的那个唯一质因子并存储到另一个数组 $b$ 里（对数字 $1$ 特判）

TIP
这里转化的思路要多想一步，实际上假如这个数是质数的幂，这个数的唯一质因子在这道题目里就可以”代表“这个数，因为不管如何拆分，最后都只能拆成很多个质因子。

我们考察 $b$ 是否是单调不降的。如果 $b$ 已经是单调不降的，那么无论如何拆分，它仍然是升序的，所以此时后手必胜。

假如 $b$ 存在逆序对（不是单调不降的），显然整个数组不可能变成单调不降的，此时先手必胜。

NOTE
总结：对于这种将数拆分成两个数的乘积的问题，要从质数上下手，因为质数是不可以被拆分的。
首先考虑什么样的数不可以被拆分，再考虑最优的拆分策略。这道题中需要确认所有数的质因子数量情况，基于这个结果进行分类讨论。

Code#

1
// Problem: CF 2200 E
2
// Contest: Codeforces - Codeforces Round 1084 (Div. 3)
3
// URL: https://codeforces.com/contest/2200/problem/E
4
// Time: 2026-04-27 13:43:44
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
#define endl '\n'
9

10
typedef long long ll;
11
typedef unsigned long long ull;
12
typedef pair<int, int> pii;
13
typedef pair<double, double> pdd;
14
typedef pair<long long, long long> pll;
15

16
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
17
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
18
const int inf = 0x3f3f3f3f;
19
const int N = 0;
20

21
int get_prime(int x)
22
{
23
    set<int> s;
24
    for (int i = 2; i * i <= x; i++)
25
    {
26
        while (x % i == 0)
27
        {
28
            s.insert(i);
29
            x /= i;
30
        }
31
    }
32

33
    if (x > 1)
34
        s.insert(x);
35

36
    if (s.size() > 1) // 含有不同的质因子
37
        return -1;
38

39
    if (s.size() == 0) // 传入的是1
40
        return 1;
41

42
    return *s.begin(); // 只有一种质因子
43
}
44

45
void solve()
46
{
47
    int n;
48
    cin >> n;
49

50
    vector<int> a(n), b(n);
51

52
    for (int i = 0; i < n; i++)
53
        cin >> a[i];
54

55
    for (int i = 0; i < n; i++)
56
        b[i] = get_prime(a[i]);
57

58
    // 开始前如果单调不降，后手必胜
59
    if (is_sorted(a.begin(), a.end()))
60
        cout << "Bob" << endl;
61

62
    // 只要原数组中有一个有不同质因子的数，先手必胜
63
    else if (*min_element(b.begin(), b.end()) == -1)
64
        cout << "Alice" << endl;
65

66
    // b如果是单调不降的，后手必胜
67
    else if (is_sorted(b.begin(), b.end()))
68
        cout << "Bob" << endl;
69

70
    // b如果不是单调不降的，先手必胜
71
    else
72
        cout << "Alice" << endl;
73
}
74

75
int main()
76
{
77
    int T;
78
    cin >> T;
79

80
    while (T--)
81
        solve();
82

83
    return 0;
84
}