s

Codeforces Round 897

A. A

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
#include <bits/stdc++.h>
#define int long long

/*
思路：让我们从最小数中减去 n, 从第二个最小数中减去 n−1，从第三个 …中减去 n−2，再从最大数中减去  1
显然没有更好的结果
*/

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::array<int, 2>> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i][0];
        a[i][1] = i + 1;
    }
    sort(a.begin(), a.end());
    std::vector<int> ans(n + 1);
    int cnt = n;
    for (auto [k, idx] : a) {
        ans[idx] = cnt--; 
    }
    for (int i = 1; i <= n; i++) {
        std::cout << ans[i] << ' ';
    }
    std::cout << '\n';
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B. B

思路： 考虑给定串前后的对应部分原来是否相同，若不同则需要且仅需要在这两个位置中改一个，若相同则可以都不改或者都改。特别地，若 n 为奇数则中间位置改不改都行。

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>
#define int long long

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    // 记录有多少对不同
    int cnt = 0;
    for (int i = 0, j = n - 1; i < j; i++, j--) {
        if (s[i] != s[j]) {
            cnt++;
        } 
    }
    std::string ans(n + 1, '0');
    // 异或运算 与 1 异或才会改变
    // 至少需要修改 cnt 个, 最多只能修改 n - cnt 个， 如果 n 是奇数， 中间的一位可修改可不修改，所以：i += 1 + (n % 2 == 0)
    for (int i = cnt; i <= n - cnt; i += 1 + (n % 2 == 0)) {
        ans[i] = '1';
    }
    std::cout << ans << '\n';
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. C

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
#include <bits/stdc++.h>
#define int long long

/*
思路： 理解题意发现并不难， 如果s[0] > 1, 则R最大为1
如果是序列 0 1 2 3， 则R最大是4。
不多说了，看代码吧
*/

void solve() {
    int n;
    std::cin >> n;
    int x;
    std::map<int, int> mp;
    for (int i = 0; i < n; i++) {
        std::cin >> x;
        mp[x]++;
    }
    int p = 0;
    for (int i = 0; i <= n; i++) {
        if (!mp.count(i)) {
            p = i;
            break;
        }
    }
    while (1) {
        std::cout << p << std::endl;
        int q;
        std::cin >> q;
        if (q == -1) {
            break;
        }
        p = q;
    }
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D. d

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
#include <bits/stdc++.h>
#define int long long

/*
思路： 找环， 建有向边 i -> a[i]， 表示第 i 个要变为 a[i],  
通过观察 如果存在一个环的大小不等于k， 这个是肯定不可以构造成功的， k = 1 的时候特判一下 
*/

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n + 1);
    int f = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x;
        a[i] = x;
        if (i != x) f = 1;
    }

    if (f && k == 1) {
        std::cout << "NO\n";
        return;
    }

    std::vector<int> vis(n + 1);
    std::vector<int> st(n + 1);

    for (int i = 1; i <= n; i++) {
        if (!st[i]) {
            int cnt = 0;
            for (int j = i; ; j = a[j]) {
                if (st[j] && st[j] != i) {
                    cnt = k;
                    break;
                }
                st[j] = i;
                vis[j]++;
                if (vis[j] == 3) {
                    break;
                }
                if (vis[j] == 2) {
                    cnt++;
                }
            }
            if (cnt != k) {
                std::cout << "NO\n";
                return;
            }
        }
    }

    std::cout << "YES\n";
}

signed main() {
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E. E1

待补

1

F. E2

1

G. F

1

AtCoder Beginner Contest 311 A - F

H、a

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

int main() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;
    // 了解set的用法：https://www.runoob.com/cplusplus/cpp-libs-set.html
    std::set<char> se;
    for (int i = 0; i < n; i++) {
        se.insert(s[i]);
        if (se.size() == 3) {
            std::cout << i + 1 << '\n';
            return 0;
        }
    }
    return 0;
}

I、b

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
#include <bits/stdc++.h>

/*
思路： 统计每一天有空的人数， 取有空人数 = n 的天 连续的最大值
*/

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> cnt(m);
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        for (int j = 0; j < m; j++) {
            if (s[j] == 'o') {
                cnt[j]++;
            }
        }
    }
    int ans = 0, t = 0;
    for (int i = 0; i < m; i++) {
        if (cnt[i] == n) {
            t++;
            ans = std::max(ans, t);
        } else {
            t = 0;
        }
    }
    std::cout << ans << '\n';
    return 0;
}

J、c

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
#include <bits/stdc++.h>

/*
思路： 因为有n条边， 所以每个连通块一定存在一个环。任意选择一个开始操作即可，见代码
*/

signed main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    std::vector<int> vis(n + 1), ans;
    // 这里i初始可以是 1 - n 的任意值
    for (int i = 1; ; i = a[i]) {
        vis[i]++;
        // 说明这个环都已经全部被加入到ans中了，退出循环
        if (vis[i] == 3) {
            break;
        }
        // 第二次遍历到， 说明这个一定是环中的一个节点
        if (vis[i] == 2) {
            ans.push_back(i);
        }
    }
    std::cout << ans.size() << '\n';
    for (auto x : ans) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
    return 0;
}

K、d

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
#include <bits/stdc++.h>
int n, m;
const int MAX = 210;
std::string a[MAX];
int vis[MAX][MAX];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void dfs(int x, int y) {
    vis[x][y] = 1;
    // 选择四个方向
    for (int i = 0; i < 4; i++) {
        int tx = x, ty = y;
        while (a[tx + dx[i]][ty + dy[i]] != '#') {
            vis[tx][ty] = 1;
            tx += dx[i], ty += dy[i];
        }
        // 此时走到 a[tx][ty]，重新选择方向
        // 如果这个格子被走过的话就 一定不用重新遍历了
        if (!vis[tx][ty]) {
            dfs(tx, ty);
        } 
    }
}

int main() {
    std::cin >> n >> m;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    } 

    dfs(1, 1);

    int ans = 0;
    // 记录答案
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[i][j]) {
                ans++;
            }
        }
    }
    std::cout << ans << '\n';

    return 0;
}

L、e

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
#include <bits/stdc++.h>

/*
题意： 转化题意就是求 全部无洞正方形子矩阵的数量
    把有洞的方格设为 0， 其他设为 1 统计全为 1 的正方形子矩阵问题就转化为 这道题：https://leetcode.cn/problems/count-square-submatrices-with-all-ones/description/?envType=daily-question&envId=2025-08-20
    这道题正好是今天 leetcode 的每日一题
    可以看这一篇题解：https://leetcode.cn/problems/count-square-submatrices-with-all-ones/solutions/3751608/tu-jie-dong-tai-gui-hua-jian-ji-xie-fa-p-1kiy/?envType=daily-question&envId=2025-08-20
    以下是示例代码
*/

const int N = 3010;
int a[N][N];
long long dp[N][N];

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;
    while (k--) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = 1;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 0) {
                dp[i][j] = std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                ans += dp[i][j];
            }
        }
    }
    std::cout << ans << '\n';

    return 0;
}

M、f

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
#include <bits/stdc++.h>
const int MOD = 998244353;

/*
思路： 定义 dp[i][j]表示前i列，其中第i列的情况是，j 行及以下都是黑色，以上都是白色 的方案数。
详细见题解：https://www.cnblogs.com/Lanly/p/17574427.html
*/

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::string> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == '#') {
                if (i < n - 1) {
                    a[i + 1][j] = '#';
                    if (j < m - 1) {
                        a[i + 1][j + 1] = '#';
                    }
                }
            }
        }
    }
    std::vector<int> dp(n + 1, 0);
    // 初始化 第 -1 列全为白色这一种方案
    dp[n] = 1;
    for (int i = 0; i < m; i++) {
        std::vector<int> dp2(n + 1, 0);
        int sufsum = 0;
        for (int j = n; j >= 0; j--) {
            sufsum = (sufsum + dp[j]) % MOD;
            if (j > 0 && a[j - 1][i] == '#') {
                continue;
            }
            if (j > 0) {
                dp2[j] = dp[j - 1] + sufsum;
            } else {
                dp2[j] = sufsum;
            }
            dp2[j] %= MOD;
        }
        dp = dp2;
    }
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        ans = (ans + dp[i]) % MOD;
    }
    std::cout << ans << '\n';
    return 0;
}

N、g

待做