NOTE
比赛链接：Educational Codeforces Round 190 (Rated for Div.2)

A - Optimal Purchase#

关键词：模拟

思路#

考虑三种情况：

为所有的学生买个人秘钥
为 n / 3 组学生买团体秘钥，并为 n % 3 个学生购买个人秘钥
为 n / 3 组学生买团体秘钥，并为 n % 3 个学生购买团体秘钥

取最小值即可。

Code#

1
// Problem: CF 2230 A
2
// Contest: Codeforces - Educational Codeforces Round 190 (Rated for Div. 2)
3
// URL: https://codeforces.com/contest/2230/problem/A
4
// Time: 2026-05-18 23:03:28
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, a, b;
29
    cin >> n >> a >> b;
30

31
    ll res1 = a * n;
32
    ll res2 = b * (n / 3) + min(a * (n % 3), b);
33

34
    cout << min(res1, res2) << endl;
35
}
36

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

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

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

47
    return 0;
48
}

B - Digit String#

关键词：枚举，前缀和

思路#

注意到所有的 $4$ 都不能选，因为总可以选择 $4$ 本身作为构成 $4$ 的倍数的元素。

考虑哪些组合可以是 $4$ 的倍数，只有如下几个： $12, 32, 24, 44$ ，而含有 $4$ 的又不可以被选，因此只需要考虑 $12, 32$ 。

不能出现 $12, 32$ 的子序列，意味着所有的 $1$ 和 $3$ 都必须排在 $2$ 的后面。

因此最终保留的合法字符一定是 $\underbrace{22\dots22}_{\text{若干个 } 2} \quad \underbrace{13113\dots}_{\text{若干个 } 1 \text{ 和 } 3}$ 的形式。

换句话说，整个合法的字符串一定可以被一条“分割线”切成两半：左半边只能包含 $2$ ，右半边：只能包含 $1$ 和 $3$ 。

使用前缀和维护 $1, 2, 3$ 的出现次数，枚举分割点，并计算最多能保留下来的字符数。

Code#

1
// Problem: CF 2230 B
2
// Contest: Codeforces - Educational Codeforces Round 190 (Rated for Div. 2)
3
// URL: https://codeforces.com/contest/2230/problem/B
4
// Time: 2026-05-18 23:10:18
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
    string s;
29
    cin >> s;
30

31
    int n = s.size();
32

33
    vector<int> a(n), b(n), c(n);
34
    for (int i = 0; i < n; i++)
35
    {
36
        if (s[i] == '1')
37
            a[i]++;
38
        else if (s[i] == '2')
39
            b[i]++;
40
        else if (s[i] == '3')
41
            c[i]++;
42

43
        if (i == 0)
44
            continue;
45

46
        a[i] = a[i] + a[i - 1];
47
        b[i] = b[i] + b[i - 1];
48
        c[i] = c[i] + c[i - 1];
49
    }
50

51
    int res = 0;
52
    for (int i = 0; i <= n; i++)
53
    {
54
        int l2 = (i == 0) ? 0 : b[i - 1];
55
        int r1 = a[n - 1] - ((i == 0) ? 0 : a[i - 1]);
56
        int r3 = c[n - 1] - ((i == 0) ? 0 : c[i - 1]);
57

58
        res = max(res, l2 + r1 + r3);
59
    }
60
    cout << n - res << endl;
61
}
62

63
int main()
64
{
65
    fastio();
66

67
    int T = 1;
68
    cin >> T;
69

70
    while (T--)
71
        solve();
72

73
    return 0;
74
}

C - Arrange the Numbers in a Circle#

关键词：思维

思路#

每一组连续的三张卡片中至少有两个是相同的，意味着不能出现连续三张牌是完全不同的数字。

从这个角度出发，我们考虑将所有的牌分成两类：

基础牌：数量 $\ge 2$ 的数字。它们能自己组成连续的相同牌（如 $A, A$ ），因此是构建圆环的基础。
孤儿牌：数量为 $1$ 的数字。它们孤立存在，容易与两边的数字形成“三张不同”的非法组合。

并且我们发现，只要孤儿牌出现在圆环中，它的两侧一定是同一种基础牌，如 $\dots A, S, A \dots$ ，而不能是 $A, S, B$ 。

既然孤儿牌需要基础牌的“庇护”，那我们考察基础牌能提供多少庇护容量。这里分三种情况：

完全没有基础牌：答案直接为 $0$ 。
只有 1 种基础牌 (假设该数字有 $C$ 张)，每隔绝一个孤儿就需要左右两侧各有一个 $A$ ，所以 $k$ 个孤儿需要 $2k$ 个 $A$ 。容纳上限为： $\lfloor C / 2 \rfloor$ 。
有 $\ge 2$ 种基础牌 (比如 $A, B, C\dots$ )，为了保证基础牌之间不发生违规，我们让每种基础牌各自抱团，形如 $A \dots A, B \dots B, C \dots C$ 。在这个大的圆环里，基础牌 $A$ 除了要保护内部的孤儿，它的左边界和右边界还要去和别的字母交接。为了防止边界出现违规，基础牌 $A$ 必须留出“一头一尾”各 1 张牌去当屏障。所以，只有剩下的 $C - 2$ 张牌可以起到庇护作用。此时，基础牌 $A$ 能容纳的孤儿数量上限变成了： $\lfloor (C - 2) / 2 \rfloor$ 。

Code#

1
// Problem: CF 2230 C
2
// Contest: Codeforces - Educational Codeforces Round 190 (Rated for Div. 2)
3
// URL: https://codeforces.com/contest/2230/problem/C
4
// Time: 2026-05-18 23:28:41
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
    ll base = 0, single = 0, capacity = 0, sum = 0;
32

33
    for (int i = 0; i < n; i++)
34
    {
35
        ll x;
36
        cin >> x;
37

38
        if (x == 1)
39
            single++;
40

41
        // 收集所有数量>=2的牌作为基础牌并计算容量
42
        else
43
        {
44
            base++;
45
            sum += x;
46
            capacity += (x - 2) / 2;
47
        }
48
    }
49

50
    ll res = 0;
51

52
    if (base == 0) // 没有基础牌
53
        res = 0;
54
    else if (base == 1) // 只有一种基础牌
55
        res = sum + min(single, sum / 2);
56
    else // 有两种以上的基础牌
57
        res = sum + min(single, capacity);
58

59
    if (res < 3)
60
        cout << 0 << endl;
61
    else
62
        cout << res << endl;
63
}
64

65
int main()
66
{
67
    fastio();
68

69
    int T = 1;
70
    cin >> T;
71

72
    while (T--)
73
        solve();
74

75
    return 0;
76
}

D - Good Schedule#

关键词：DP

思路#

两个人追剧必须是按顺序来的，也就是开始的目标集都是第一集，如果电视放的是目标集就看，看完后目标集变成下一集，否则他们会无视。我们需要找一个区间 $[L, R]$ ，在这个区间里，要么一起看同一集，要么一起啥也不看。这就意味着，他们在整个区间里，目标集永远是同步的。

假设我们固定了区间的起点 $L$ ，初始时两人都需要看第 1 集。

接下来会发生什么？我们寻找第 1 集在 $a$ 和 $b$ 中首次出现的日子：设 Alice 首次遇到第 1 集的日子是 $posA$ ，设 Bob 首次遇到第 1 集的日子是 $posB$ ，这里有三种情况：

$posA \neq posB$ ，当产生分歧的时候，这个区间就用不了了，设 $posA < posB$ ，这个起点 $L$ 最远就能走到 $\min(posA, posB) - 1$ 。
$posA = posB = idx$ ，在 $idx$ 这一天，两人同时看到了第 1 集。看完后，两人的目标同时变成了第 2 集。那么从 $idx + 1$ 天开始，他们寻找第 2 集的过程就变成了下一个阶段的问题。
$posA = posB = \infty$ ，如果在剩下的日子里，第 1 集再也没出现过，那两个人就什么也不看，此时动作也是永远一致的，一直到第 $n$ 天结束都是合法的。

观察第二种情况，很明显满足无后效性。当我们同时在第 $idx$ 天看完第 $v$ 集后，我们接下来的命运，只取决于从 $idx + 1$ 天开始寻找第 $v+1$ 集的结果。

定义 $DP[i]$ 为：假设两人在第 $i$ 天成功同步看完了第 $v$ 集（前提 $a_i = b_i = v$ ），那么在未来，他们最早在哪一天会产生分歧（即动作不一致）

状态计算：在第 $i$ 天看完后，目标变成了 $a_i + 1$ 。我们去找 $a_i + 1$ 在 $i$ 之后的首次出现位置 $posA$ 和 $posB$ 。

如果 $posA \neq posB$ ，意味着两人寻找下一集遇到了时间差，那分歧必然在较早的那一天发生。所以 $DP[i] = \min(posA, posB)$ 。
如果 $posA = posB = next\_idx$ ，说明又同步了，分歧点推迟到了下一次，所以 $DP[i] = DP[next\_idx]$ 。
如果都没出现，说明永远没有分歧，合法的尽头是最后一天之后， $DP[i] = n + 1$ 。

Code#

NOTE
代码中，p1 和 p2 是二维数组（类似于邻接表）。p1[v] 里面按升序存储了第 $v$ 集在 Alice 城市播放的所有天数。
find 函数的作用是，在时刻表 s 里，找到大于等于第 $x$ 天的第一个播放日。如果没有找到，说明以后这部剧断更了，返回 inf。
使用倒序的 DP 进行预处理，寻找首次分歧日，并枚举每一个可能的起点 $L = i$ ，计算答案。

1
// Problem: CF 2230 D
2
// Contest: Codeforces - Educational Codeforces Round 190 (Rated for Div. 2)
3
// URL: https://codeforces.com/contest/2230/problem/D
4
// Time: 2026-05-20 23:19:09
5
#include <bits/stdc++.h>
6
using namespace std;
7

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

15
using ll = long long;
16
using ull = unsigned long long;
17
using pii = pair<int, int>;
18
using pdd = pair<double, double>;
19
using pll = pair<long long, long long>;
20
using i128 = __int128;
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;
30
    cin >> n;
31

32
    vector<int> a(n + 1), b(n + 1);
33
    vector<vector<int>> p1(n + 2), p2(n + 2);
34

35
    for (int i = 1; i <= n; i++)
36
    {
37
        cin >> a[i];
38
        p1[a[i]].push_back(i);
39
    }
40
    for (int i = 1; i <= n; i++)
41
    {
42
        cin >> b[i];
43
        p2[b[i]].push_back(i);
44
    }
45

46
    auto find = [&](const vector<int> &s, int x)
47
    {
48
        auto p = lower_bound(s.begin(), s.end(), x);
49
        if (p == s.end())
50
            return inf;
51
        return *p;
52
    };
53

54
    vector<int> dp(n + 1);
55
    for (int i = n; i > 0; i--)
56
    {
57
        if (a[i] != b[i])
58
            continue;
59

60
        int na = find(p1[a[i] + 1], i + 1);
61
        int nb = find(p2[a[i] + 1], i + 1);
62

63
        if (na == nb)
64
        {
65
            if (na == inf)
66
                dp[i] = n + 1;
67
            else
68
                dp[i] = dp[na];
69
        }
70
        else
71
            dp[i] = min(na, nb);
72
    }
73

74
    int res = 0;
75
    for (int i = 1; i <= n; i++)
76
    {
77
        int na = find(p1[1], i);
78
        int nb = find(p2[1], i);
79

80
        if (na == nb)
81
        {
82
            if (na == inf)
83
                res += n - i + 1;
84
            else
85
                res += dp[na] - i;
86
        }
87
        else
88
            res += min(na, nb) - i;
89
    }
90

91
    cout << res << endl;
92
}
93

94
signed main()
95
{
96
    fastio();
97

98
    int T = 1;
99
    cin >> T;
100

101
    while (T--)
102
        solve();
103

104
    return 0;
105
}