前几题也没什么好讲的，只写了E、F的分析。

1335A Candies and Two Sisters

A.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        n = (n - 1) / 2;
        cout << n << endl;
    }
    return 0;
}

1335B Construct the String

B.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, a, b;
        cin >> n >> a >> b;
        for (int i = 0; i < n; ++i) {
            cout << char(i % b + 'a');
        }
        cout << endl;
    }
    return 0;
}

1335C Two Teams Composing

C.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        map<int, int> mp;
        for (int i = 0, t; i < n; ++i) {
            cin >> t;
            ++mp[t];
        }
        vector<pii> cnt;
        for (auto &i : mp) {
            cnt.emplace_back(i.second, i.first);
        }
        sort(cnt.begin(), cnt.end());
        int ans = 0;
        if (cnt.back().first - 1 >= cnt.size())
            ans = cnt.size();
        for (int i = cnt.size() - 1; i > 0 && !ans; --i) {
            if (cnt.back().first >= i ) {
                ans = i;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

1335D Anti-Sudoku

题目的要求提示也比较明显，$9$行$9$列和$9$大方块对应一下。

D.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
        string s[9];
        for (auto &i : s) cin >> i;
        s[0][0] = s[1][1];
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                s[i * 3 + j][j * 3 + i] = s[i * 3][j * 3];
            }
        }
        for (auto &i : s) cout << i << endl;
    }
    return 0;
}

1335E Three Blocks Palindrome (easy & hard version)

首先可以想到枚举两个颜色，咋一看好像复杂度是$200\times 200 \times 2e…^5$，但是实际上可以想到对于一个颜色作为两端来说，它确定左端长度，也就有唯一对应的右端，那么就是找中间段的某个颜色最多的个数，由于$\sum pos_i \leq 2e^5$，那么最多只有这么多$\div 2$个位置对，每个位置对再前缀和后暴力枚举众数，复杂度最多$O(2e^7)$。
$E1$可以通过暴力解决，具体的话我么想。

E.cpp
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
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int a[N], cnt[N][200];

int main() {
    int q;
    cin >> q;
    while (q--) {
        int n, ans = 0;
        cin >> n;
        vector<vector<int>> pos(201);
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            for (int j = 1; j <= 200; ++j) {
                cnt[i][j] = cnt[i - 1][j];
            }
            ++cnt[i][a[i]];
            pos[a[i]].emplace_back(i);
            ans = max(ans, cnt[i][a[i]]);
        }
        for (int i = 1; i <= 200; ++i) {
            if (pos[i].empty()) continue;
            int l = 0, r = pos[i].size() - 1;
            for (;l < pos[i].size() && l < r; ++l) {
                while (cnt[pos[i][l]][i] > cnt[n][i] - cnt[pos[i][r - 1]][i]) --r;
                if (l >= r) break;
                for (int j = 1; j <= 200; ++j) {
                    ans = max(ans, 2 * cnt[pos[i][l]][i] + cnt[pos[i][r] - 1][j] - cnt[pos[i][l]][j]);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

1335F Robots on a Grid

这个题解法还是挺明显的，因为某些路径一定会成环（否则机器人就不能无限走下去了），那么如果将矩阵转化为图后，每个连通块就是一个基环内向树，最多放机器人个数就是环长的和。最多在黑色格子的可以这样考虑：
如果环外的链上有若干黑色点，那么如果把这些链按方向合并到环上，最后环上有几个黑色点，就是最多的答案。
（自己写成码农了，后来跟jls学了波姿势，灰常清楚）

F.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    int q;
    cin >> q;
    while (q--) {
    int n, m;
        cin >> n >> m;
        vector<string> g(n), col(n);
        vector<int> to(n * m), dgr(n * m);
        vector<vector<int>> e(n * m);
        for (int i = 0; i < n; ++i) cin >> col[i];
        for (int i = 0; i < n; ++i) cin >> g[i];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int xx = i, yy = j;
                if (g[i][j] == 'U') --xx;
                else if (g[i][j] == 'D') ++xx;
                else if (g[i][j] == 'L') --yy;
                else ++yy;
                to[i * m + j] = xx * m + yy;
                ++dgr[to[i * m + j]];
            }
        }
        function<void(int)> cut_chain = [&](int x) {
            --dgr[x];
            e[to[x]].emplace_back(x);
            if (--dgr[to[x]] == 0)
                cut_chain(to[x]);
        };
        for (int i = 0; i < n * m; ++i) {
            if (!dgr[i])
                cut_chain(i);
        }
        int ans1 = 0, ans2 = 0;
        for (int i = 0; i < n * m; ++i) {
            if (dgr[i] == 1) {
                int cnt = 1;
                for (int j = to[i]; j != i; j = to[j]) {
                    e[to[j]].emplace_back(j);
                    ++cnt;
                }
                ans1 += cnt;
                vector<bool> cc(cnt);
                function<void(int, int)> dfs = [&](int u, int dpt) {
                    dgr[u] = -1;
                    if (col[u / m][u % m] == '0') cc[dpt % cnt] = true;
                    for (int v : e[u])
                        dfs(v, dpt + 1);
                };
                dfs(i, 0);
                ans2 += count(cc.begin(), cc.end(), true);
            }
        }

        cout << ans1 << ' ' << ans2 << endl;
    }
    return 0;
}