Educational Codeforces Round #174

B

题目大意：给定一个包含 $n$ 行 $m$ 列的表格。初始时，第 $i$ 行第 $j$ 列的单元格颜色为 $a_{i, j}$。我们称两个单元格是陌生人（strangers）如果它们不共享任何一条边（允许通过角落接触）。我们称一个单元格集合为陌生人集合（set of strangers），当且仅当集合中任意两个单元格都是陌生人。根据定义，包含不超过一个单元格的集合总是陌生人集合。在每一步操作中，你可以选择一个满足以下条件的陌生人集合：集合中所有单元格颜色相同，并将它们全部涂成另一种颜色（可以选择任意一种颜色作为结果颜色）。问：要将整个表格涂成同一种颜色，最少需要多少步操作？

数据范围：$1 \le t \le 10^4$，$1 \le n \le m \le 700$，$1 \le a_{i, j} \le nm$，$\sum nm \le 5 \cdot 10^5$。

思路：

 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
26
int dx[4] = {0, 1, -1, 0};
int dy[4] = {-1, 0, 0, 1};
void solve() {
    int n, m;
    cin >> n >> m;
    vvi ma(n, vi(m));
    rep(i, 0, n - 1) { rep(j, 0, m - 1) cin >> ma[i][j]; }
    vi vis(n * m + 1);
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            if (vis[ma[i][j]] == 0) vis[ma[i][j]] = 1;
            rep(v, 0, 3) {
                int ax = i + dx[v], ay = j + dy[v];
                if (ax >= 0 && ax <= n - 1 && ay >= 0 && ay <= m - 1) {
                    if (ma[ax][ay] == ma[i][j]) vis[ma[i][j]] = 2;
                }
            }
        }
    }
    int ans = 0;
    rep(i, 1, m * n) { ans += vis[i]; }
    int ans2 = INT_MAX;
    rep(i, 1, m * n) ans2 = min(ans2, ans - vis[i]);
    cout << ans2 << endl;
    return;
}

C

题目大意：我们称一个整数序列为美丽的（beautiful），当且仅当满足以下条件： - 序列长度至少为 $3$； - 对于除第一个元素外的每个元素，其左侧存在一个比它小的元素； - 对于除最后一个元素外的每个元素，其右侧存在一个比它大的元素；给定一个大小为 $n$ 的整数数组 $a$，其中每个元素均为 $1$ 到 $3$ 之间的整数。需要计算数组 $a$ 中美丽子序列的数量。

数据范围：$1 \le t \le 10^4$，$3 \le n \le 2 \cdot 10^5$，$1 \le a_i \le 3$，$\sum n \le 2 \cdot 10^5$。

思路：

 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
26
27
28
29
30
31
32
33
const ll MOD = 998244353;
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    ll tem = 0;
    ll tem2 = 0;
    ll tem3 = 0;
    int idx = -1;
    rep(i, 0, n - 1) {
        if (a[i] == 1) {
            idx = i;
            break;
        }
    }
    if (idx == -1) {
        cout << 0 << endl;
        return;
    }
    rep(i, idx, n - 1) {
        if (a[i] == 1) {
            tem++;
        } else if (a[i] == 2) {
            tem2 = (tem2 * 2 % MOD + tem) % MOD;
        } else {
            ans = (ans + tem2) % MOD;
        }
    }
    cout << ans << endl;
    return;
}

D

题目大意：给定一个由小写拉丁字母组成的字符串 $s$。你可以对字符串 $s$ 执行以下操作：选择一个连续的（可能为空的）子串，并对其进行洗牌（即重新排列子串中的字符顺序）。需要确定为了将给定字符串 $s$ 转换为回文，必须进行操作的最小子串长度。

数据范围：$1 \le t \le 10^4$，$2 \le |s| \le 2 \cdot 10^5$，$\sum |s| \le 2 \cdot 10^5$。

思路：

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
const ll MOD = 998244353;
void solve() {
    string s;
    cin >> s;
    int n = sz(s);
    int l1 = 0, r1 = n - 1;
    while (l1 <= r1 && s[l1] == s[r1]) {
        l1++, r1--;
    }
    if (l1 > r1) {
        cout << 0 << endl;
        return;
    }
    string tem = s.substr(l1, r1 - l1 + 1);
    int m = sz(tem);
    int l = 2, r = m, ans = 2, mid;
    auto check = [&](int mid) -> bool {
        if (mid > m / 2) {
            vi tem2(26);
            vi tem3(26);
            rep(i, 0, mid - 1) tem2[tem[i] - 'a']++;
            rep(i, mid, m - 1) tem3[tem[i] - 'a']++;
            bool flag = true;
            rep(i, 0, 25) {
                if (tem2[i] >= tem3[i])
                    continue;
                else
                    flag = false;
            }
            if (flag) return true;
            flag = true;
            rep(i, 0, 25) tem2[i] = 0, tem3[i] = 0;
            rep(i, m - mid, m - 1) tem2[tem[i] - 'a']++;
            rep(i, 0, m - mid - 1) tem3[tem[i] - 'a']++;
            rep(i, 0, 25) {
                if (tem2[i] >= tem3[i] && (tem2[i] - tem3[i]) % 2 == 0)
                    continue;
                else
                    flag = false;
            }
            return flag;
        } else {
            rep(i, mid, m / 2 - 1) {
                if (tem[i] != tem[m - 1 - i]) return false;
            }
            vi tem2(26);
            vi tem3(26);
            rep(i, 0, mid - 1) tem2[tem[i] - 'a']++;
            rep(i, m - mid, m - 1) tem3[tem[i] - 'a']++;
            bool flag = true;
            rep(i, 0, 25) {
                if (tem2[i] == tem3[i])
                    continue;
                else
                    flag = false;
            }
            if (flag) return true;
            flag = true;
            rep(i, 0, 25) tem2[i] = 0, tem3[i] = 0;
            rep(i, 0, mid - 1) tem3[tem[i] - 'a']++;
            rep(i, m - mid, m - 1) tem2[tem[i] - 'a']++;
            rep(i, 0, 25) {
                if (tem2[i] == tem3[i])
                    continue;
                else
                    flag = false;
            }
            return flag;
        }
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans << endl;
    return;
}

E

题目大意：给定一个由字符 A 和 B 组成的字符串 $s$。需要将它分割成长度为 $1$ 或 $2$ 的块，使得： - “A” 类型的块数量不超过 $a$； - “B” 类型的块数量不超过 $b$； - “AB” 类型的块数量不超过 $ab$； - “BA” 类型的块数量不超过 $ba$；其中 “AA” 和 “BB” 类型的块是被禁止的。原始字符串 $s$ 的每个字符必须恰好属于一个块。

数据范围：$1 \le t \le 10^4$，$1 \le |s| \le 5 \cdot 10^5$，$0 \le a, b, ab, ba \le 5 \cdot 10^5$，$\sum |s| \le 5 \cdot 10^5$。

思路：

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void solve() {
    string s;
    cin >> s;
    int n = sz(s);
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    int cnt0 = 0, cnt1 = 0;
    rep(i, 0, n - 1) {
        if (s[i] == 'A')
            cnt0++;
        else
            cnt1++;
    }
    if (a + b + 2 * c + 2 * d < n) {
        cout << "NO" << endl;
        return;
    }
    vi tem;
    vi tem2;
    ll tem3 = 0;
    int l = 0;
    while (l <= n - 1) {
        int r = l;
        while (r < n - 1 && s[r + 1] != s[r]) r++;
        if ((r - l + 1) % 2 == 1) {
            tem3 += (r - l + 1) / 2;
        } else {
            if (s[l] == 'A')
                tem.push_back((r - l + 1) / 2);
            else
                tem2.push_back((r - l + 1) / 2);
        }
        l = r + 1;
    }
    ranges::sort(tem);
    ranges::sort(tem2);
    ll re = 0;
    rep(i, 0, sz(tem) - 1) {
        if (c >= tem[i]) {
            c -= tem[i];
            re += tem[i];
        } else
            tem3 += tem[i] - 1;
    }
    rep(i, 0, sz(tem2) - 1) {
        if (d >= tem2[i]) {
            d -= tem2[i];
            re += tem2[i];
        } else
            tem3 += tem2[i] - 1;
    }
    re += min(tem3, c + d);
    if (a + re >= cnt0 && b + re >= cnt1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return;
}