NOTE
比赛链接：Codeforces Round 1074 (Div. 4)

A - Perfect Root#

关键词：签到

Code#

1
// Problem: CF 2185 A
2
// Contest: Codeforces - Codeforces Round 1074 (Div. 4)
3
// URL: https://codeforces.com/contest/2185/problem/A
4
// Time: 2026-05-14 22:08:57
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    for (int i = 1; i <= n; i++)
32
        cout << i << " ";
33
    cout << endl;
34
}
35

36
int main()
37
{
38
    fastio();
39

40
    int T = 1;
41
    cin >> T;
42

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

46
    return 0;
47
}

B - Prefix Max#

关键词：签到

思路#

把最大值换到数组的最开始一定是最优的，答案为 $max \times n$ 。

Code#

1
// Problem: CF 2185 B
2
// Contest: Codeforces - Codeforces Round 1074 (Div. 4)
3
// URL: https://codeforces.com/contest/2185/problem/B
4
// Time: 2026-05-14 22:08:42
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    vector<int> a(n);
32

33
    int mx = -1;
34
    for (int i = 0; i < n; i++)
35
    {
36
        cin >> a[i];
37
        if (a[i] > mx)
38
            mx = a[i];
39
    }
40

41
    cout << (ll) mx * n << endl;
42
}
43

44
int main()
45
{
46
    fastio();
47

48
    int T = 1;
49
    cin >> T;
50

51
    while (T--)
52
        solve();
53

54
    return 0;
55
}

C - Shifted MEX#

关键词：MEX，思维

思路#

任意次的操作都不会改变数组中任意两个元素之间的相对差值。

如果在变换后的数组中存在 $0, 1, \dots, M-1$ 这样一段连续的公差为 1 的序列，那么在原数组中，必然也存在一段长度为 $M$ 的连续公差为 1 的序列，即 $y, y+1, y+2, \dots, y+M-1$ （其中 $y = -x$ ）。

因此我们只需要找到原数组去重后，最长的连续公差为 $1$ 的序列的长度即可。假设原数组中最长的一段连续整数序列的长度为 $L$ ，起止元素分别为 $y$ 到 $y+L-1$ 。我们只需令 $x = -y$ ，那么这段序列就会被平移成 $0, 1, \dots, L-1$ 。

Code#

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

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    int n;
29
    cin >> n;
30

31
    vector<int> a(n);
32
    for (int i = 0; i < n; i++)
33
        cin >> a[i];
34

35
    sort(all(a));
36

37
    a.erase(unique(all(a)), a.end());
38

39
    int res = 0, cur = 0;
40
    for (int i = 0; i < n; i++)
41
    {
42
        if (i == 0 || a[i] - a[i - 1] != 1)
43
            cur = 0;
44
        cur++;
45
        res = max(res, cur);
46
    }
47

48
    cout << res << endl;
49
}
50

51
int main()
52
{
53
    fastio();
54

55
    int T = 1;
56
    cin >> T;
57

58
    while (T--)
59
        solve();
60

61
    return 0;
62
}

D - OutOfMemoryError#

关键词：模拟

思路#

如果每次都进行重置操作，最坏情况下的时间复杂度是 $O(n \times m)$ ，考虑将重置操作从 $O(n)$ 优化到 $O(1)$ 。

维护一个全局时间戳 $t$ ，并对于每个数维护个体时间戳，记录第 $i$ 个元素最后一次被修改时，系统处于第一次崩溃的状态。

当我们要操作第 op 个元素时，先检查它的个体时间戳 lst_up[op] 是否落后于全局时间戳 t。

假如是落后的，说明它需要被重置，进行一次重置操作并更新个体时间戳为 $t$ ，表示它已经更新到最新了。
假如加完 num 后导致了系统崩溃，就让全局时间戳 t++。

当所有操作结束，输出的时候，我们检查 lst_up[i] =?= t，假如 lst_up[i] < t，说明它还欠一次重置，所以我们输出原值

Code#

1
// Problem: CF 2185 D
2
// Contest: Codeforces - Codeforces Round 1074 (Div. 4)
3
// URL: https://codeforces.com/contest/2185/problem/D
4
// Time: 2026-05-14 22:26:44
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 0;
25

26
void solve()
27
{
28
    ll n, m, h;
29
    cin >> n >> m >> h;
30

31
    vector<ll> a(n + 1);
32
    vector<ll> cur(n + 1);
33

34
    for (int i = 1; i <= n; i++)
35
    {
36
        cin >> a[i];
37
        cur[i] = a[i];
38
    }
39

40
    vector<int> lst_up(n + 1, 0);
41
    int t = 0;
42

43
    while (m--)
44
    {
45
        ll op, num;
46
        cin >> op >> num;
47

48
        if (lst_up[op] < t)
49
            cur[op] = a[op], lst_up[op] = t;
50

51
        cur[op] += num;
52

53
        if (cur[op] > h)
54
            t++;
55
    }
56

57
    for (int i = 1; i <= n; i++)
58
    {
59
        if (lst_up[i] == t)
60
            cout << cur[i] << " ";
61
        else
62
            cout << a[i] << " ";
63
    }
64
    cout << endl;
65
}
66

67
int main()
68
{
69
    fastio();
70

71
    int T = 1;
72
    cin >> T;
73

74
    while (T--)
75
        solve();
76

77
    return 0;
78
}

E - The Robotic Rush#

关键词：二分，思维，预处理

思路#

所有机器人都是一起移动的，这意味着机器人和地刺之间的相对初始距离始终不变。

我们考虑计算全局位移的历史最远记录。对于任意一个机器人，它只会被距离它两侧最近的地刺扎死：

如果左边最近的地刺距离它是 pre，那么只要全局向左的位移首次达到 pre，这个机器人就会死。
如果右边最近的地刺距离它是 suf，那么只要全局向右的位移首次达到 suf，它也会死。

我们预处理出首次到达特定位移的时间，也就是记录首次到达向左/向右的某个位移时是在第几条指令（从 $1$ 开始）

cur 记录的是：当前的累积偏移量。
L[x] 记录的是：全局第一次向左偏移达到 x 单位长度时，是在第几步（i + 1）。
R[x] 记录的是：全局第一次向右偏移达到 x 单位长度时，是在第几步。

对于第 i 个机器人（初始坐标 a[i]），使用二分查找 lower_bound 在排序好的地刺数组 b 中找到它的位置。

假如距离大于 $K$ ，说明在 $K$ 次操作内不可能碰到，设置成 $K+1$ 防止数组越界。

设 pre 是它到左侧最近地刺的距离，suf 是它到右侧最近地刺的距离。直接查表，机器人碰到左地刺的时间是 L[pre]，碰到右地刺的时间是 R[suf]，它的死亡时间就是二者的最小值。

我们再维护一个统计死亡信息的数组，记录在第 $i$ 步刚好死掉的机器人的数量。

初始存活人数为 n。随着步数 i 从 1 推进到 k，每次减去在这一步刚好死掉的机器人数量 cnt[i]，并输出即可。

Code#

1
// Problem: CF 2185 E
2
// Contest: Codeforces - Codeforces Round 1074 (Div. 4)
3
// URL: https://codeforces.com/contest/2185/problem/E
4
// Time: 2026-05-08 14:42:04
5
// 预处理出向左和向右移动每个特定距离的“首次到达时间”
6
// 然后直接计算出每个机器人的确切死亡时刻
7
#include <bits/stdc++.h>
8
using namespace std;
9

10
// clang-format off
11
#define endl '\n'
12
#define all(x) (x).begin(), (x).end()
13
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
14
// clang-format on
15

16
using ll = long long;
17
using ull = unsigned long long;
18
using pii = pair<int, int>;
19
using pdd = pair<double, double>;
20
using pll = pair<long long, long long>;
21

22
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
23
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
24
const int inf = 0x3f3f3f3f;
25
const int N = 0;
26

27
void solve()
28
{
29
    int n, m, k;
30
    cin >> n >> m >> k;
31

32
    vector<int> a(n), b(m);
33

34
    for (int i = 0; i < n; i++)
35
        cin >> a[i];
36
    for (int i = 0; i < m; i++)
37
        cin >> b[i];
38

39
    sort(all(b));
40

41
    string s;
42
    cin >> s;
43

44
    // 记录首次到达向左/向右某一位移时，是在第几条指令（从1开始）
45
    vector<int> L(k + 2, inf), R(k + 2, inf);
46
    int cur = 0; // 记录当前绝对位移
47

48
    for (int i = 0; i < k; i++)
49
    {
50
        if (s[i] == 'L')
51
            cur--;
52
        else
53
            cur++;
54

55
        if (cur < 0 && L[-cur] == inf)
56
            L[-cur] = i + 1;
57
        if (cur > 0 && R[cur] == inf)
58
            R[cur] = i + 1;
59
    }
60

61
    // cnt[i] 表示在第 i 步死亡的机器人数量
62
    vector<int> cnt(k + 2, 0);
63

64
    for (int i = 0; i < n; i++)
65
    {
66
        auto it = lower_bound(all(b), a[i]);
67

68
        // 找左侧和右侧最近的地刺距离，找不到或者距离超过k则设为 k + 1
69
        int pre = (it == b.begin()) ? k + 1 : (a[i] - *prev(it));
70
        int suf = (it == b.end()) ? k + 1 : (*it - a[i]);
71

72
        if (pre > k)
73
            pre = k + 1;
74
        if (suf > k)
75
            suf = k + 1;
76

77
        int death = min(L[pre], R[suf]);
78
        if (death != inf)
79
            cnt[death]++;
80
    }
81

82
    int res = n;
83
    for (int i = 1; i <= k; i++)
84
    {
85
        res -= cnt[i];
86
        cout << res << " ";
87
    }
88
    cout << endl;
89
}
90

91
int main()
92
{
93
    fastio();
94

95
    int T = 1;
96
    cin >> T;
97

98
    while (T--)
99
        solve();
100

101
    return 0;
102
}