Atcoder Beginner Contest 377 题解

发表于 更新于 分类于 阅读次数： 本文字数： 8.1k
棋盘专场。

TOYOTA SYSTEMS Programming Contest 2024（AtCoder Beginner Contest 377) 题解

A

题意

给定一个含有三个字符的字符串，判断是否有“A”，“B”，“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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    if (s == "ABC") {
        cout << "Yes" << "\n";
    } else {
        cout << "No" << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定一个\(8\times 8\)的棋盘，在里面放入棋子，如果一个位置满足条件，需要这个位置的行和列都没有棋子，求满足条件的位置数。

题解

我们遍历每一个棋子的位置，一个位置是棋子，说明它所在的一行和一列都不可能是符合条件的位置。我们用两个集合分别排除掉不符合的行和列，最后的答案就是两个集合里剩余的元素数量相乘。

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>
using namespace std;
#define int long long

void solve() {
    vector<string> s(8);
    for (int i = 0; i < 8; i++) {
        cin >> s[i];
    }
    set<int> row, col;
    for (int i = 0; i < 8; i++) {
        row.insert(i);
        col.insert(i);
    }
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            if (s[i][j] == '#') {
                row.erase(i);
                col.erase(j);
            }
        }
    }
    cout << row.size() * col.size() << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

给定一个\(n\times n\)的棋盘，放入\(m\)个棋子，每个棋子可以吃掉它周围按照中国象棋“马”的走法的位置上的棋子（即\((i+2,j+1),(i+2,j-1),(i-2,j+1),(i-2,j-1),(i+1,j-2),...\)，求棋盘里还能放多少个棋子，要求这些棋子不能与已有的棋子重合和被吃掉。

\(1\le n\le 10^9，1\le m\le 2\times 10^5\)

题解

\(n\)的范围非常大，自然遍历的方法是不行的，而\(m\)相对较小，可以创建一个集合，用在存放不能放置的棋子数量，我们遍历这\(m\)​个棋子，排除掉它们周围的几个棋子，最后用总未知数减去集合的大小即可。

时间复杂度：\(O(M\log M)\)

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

void solve() {
    vector dx = {0, 1, 1, 2, 2, -1, -1, -2, -2};
    vector dy = {0, 2, -2, 1, -1, 2, -2, 1, -1};
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(m);
    set<pair<int, int>> st;
    for (int i = 0; i < m; i++) {
        cin >> a[i].first >> a[i].second;
        st.insert({a[i].first, a[i].second});
    }
    for (int i = 0; i < m; i++) {
        int x = a[i].first, y = a[i].second;
        for (int j = 0; j < 9; j++) {
            int fx = x + dx[j];
            int fy = y + dy[j];
            if (1 <= fx && fx <= n && 1 <= fy && fy <= n) {
                st.insert({fx, fy});
            }
        }
    }
    cout << n * n - st.size() << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定\(n\)个区间\([l,r]\)和右端点\(m\)，满足\(1\le l\le m\)，求\([l,r]\)的数量，要求\(l\le r\)且\([l,r]\)不能包含任何一个给定的区间。

题解

不能包含任何一个给定的区间，也就是说我们求的\([l,r]\)必须是最小区间的子区间。假设存在\([l,r_1],[l,r_2]\)，那么出现在\([r_1,r_2]\)的任何一个区间都不能作为答案。因此我们不妨考虑固定左端点，那么我们选取的右端点必须是比当前左端点对应的最小的\(r\)还要小，即对于左端点为\(l\)，答案为\(min(r_l) - l\)，而如果我们选取的位置，题目没有左端点给出，我们钦定它为左端点的话，它的右端点应该对应的是此时左端点右边的第一个题目中给定的左端点对应的右端点。也就是说，对于\(i\)位置，我们找到第一个\(l>i\)对应的\(r\)，区间\([i,i],[i,i+1],...,[i,r-1]\)​都是符合题意的，因为没有完全包含给定的区间。

为了不完全包含，在钦定左端点的情况下，如果从小到大选取左端点，它们对应的右端点应该是非递减的，否则必然会包含给定的区间。我们需要从大到小遍历左端点，设\(f_i\)代表以\(i\)为左端点对应的右端点，那么\(f_i = min(f_i, f_{i+1})\)​

时间复杂度：\(O(n+m)\)

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>
using namespace std;

#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> f(m, m);
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        f[l] = min(f[l], r);
    }
    for (int i = m - 2; i >= 0; i--) {
        f[i] = min(f[i], f[i + 1]);
    }
    int ans = 0;
    for (int i = 0; i < m; i++) {
        ans += f[i] - i;
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

    return 0;
}

E

题意

给定一个大小为\(n\)的排列\(p_i\)和\(k\)，进行\(k\)次操作，每次操作进行\(p_i = p_{p_i}\)的变换，输出\(k\)次操作后的数组。

\(1\le k \le 10^{18}\)

题解

首先要明确的一点，本题不能使用倍增法。

回顾一道相似的题：ABC 367 E-Permute K Times

那一题是给定两个长度为\(n\)的序列\(X\)和\(A\)，进行\(k\)如下操作：将所有\(1\le i \le n\)，\(A_i = A_{X_i}\)，输出最后的结果。也就是说，对于位置\(i\)，它下一次应该变为位置\(X_i\)上的数，我们从\(i\)向位置\(X_i\)连边，这样连成的图会形成多个环，且每个位置到达的下一个位置是确定的。注意，这里的图，位置是不变的，变化的只有每个位置的图，因此，每个位置走\(2^k\)步到达的位置我们可以确定下来。

然后是本题，虽然\(p_i\)连向\(i\)会产生一个环，很不幸的是，由于\(p_i\)在变化，因此连成的图里每个位置到达的下一个位置也在变化，因此每个位置走\(2^k\)步到达的位置是不能倍增得到的。

一个结论是：对于构成同一个环的几个位置，经过\(k\)次操作，每个数向右循环移动\(2^k\)次。

证明：我们可以这样理解：

未操作时，数组为：\(a_1,a_2,......,a_n\)

第一次操作后，数组为：\(（a）_{a_1},（a）_{a_2},......,（a）_{a_n}\)

第二次操作后，数组为：\(（a_{a）_{a_{a_1}}},（a_{a）_{a_{a_1}}},......,（a_{a）_{a_{a_1}}}\)

理解一下：这道题的意思是，我们要找位置\(i\)的第一次操作后的数，就是在\(a\)数组里，找到\(a_i\)对应的下标；要找第二次操作后的数，就是在第一次操作后的数组，即\((a_a)\)数组里，找到\(a_{a_i}\)对应的下标。也就是说，第\(k\)次操作后都生成了一个新的数组，我们记为\(a_{a_{..._{a_a}}}\)，共\(2^k\)个\(a\)​。

（第二次操作后\(A_i\leftarrow A_{A_{A_i}}\)的理解也是对的，这里实际上每一次操作后\(A\)数组都改变了，实际上意义跟上面的是一样的）

对于第\(n+1\)次操作后得到的状态，实际上就是把第\(n\)次后得到的数组看作一个新数组按照规则移动一次，但是我们需要的是从初始\(a\)数组移动的次数，也就是重复从\(a_1\)到\(a_{a_{..._{a_a}}}\)的过程，设第\(n\)次需要移动\(f_n\)次，那么有\(f_{n+1} = 2f_n\)，而\(f_0 = 1\)，于是有递推公式移动\(2^k\)次。我们需要这样理解\(f_0 = 1\)：我们所采用的移动方法是：把环中的编号按遍历的顺序放入临时数组（结合代码）移动0次，\(2^0 = 1\)，我们重新赋值时应该把真正的数字赋值给每一个位置，而我们放入数组时实际上放入的是编号，不是真正的数字，真正的数字其实是数组中下一个数，所以我们默认先移动了一次。此后的移动就是严格按照递推公式移动了。注意：如果不这么做，递推公式应该为\(f_i = 2f_{i-1} +1\)，移动次数\(2^k - 1\)。结合上快速幂取模即可。

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

int qpow(int a, int b, int mod) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }
    vector<bool> vis(n);
    for (int i = 0; i < n; i++) {
        if (vis[i]) {
            continue;
        }
        int j = i;
        vector<int> tmp;
        while (!vis[j]) {
            tmp.push_back(j);
            vis[j] = 1;
            j = a[j];
        }
        int d = qpow(2, k, tmp.size());
        for (int j = 0; j < tmp.size(); j++) {
            a[tmp[j]] = tmp[(j + d) % tmp.size()];
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] + 1 << " \n"[i == n - 1];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F

题意

给定一个\(n\times n\)的棋盘，放入\(m\)个棋子，每个棋子可以吃掉它所在的行、列、两条对角线上的棋子。求棋盘里还能放多少个棋子，要求这些棋子不能与已有的棋子重合和被吃掉。

\(1\le n\le 10^9，1\le m\le 10^3\)

题解

\(m\)的范围比较小而\(n\)的范围还是非常大，我们还是只能通过容斥的方法求解。我们不妨用总棋子数\(n*n\)，对于每个方向都减去不符合条件的棋子，但是这样做的话有很多棋子会被减去多次，需要我们再加回来。其中\((i,j)\)点所在主对角线上的元素数量应该为\(n - |i-j|\)（最中间那一条对角线元素个数为\(n\)），副对角线为\(n - |n - (i + j) + 1|\)（同理）

接下来是漫长的分类讨论过程，要做到不重不漏。考虑到中心的棋子甚至可能同时被行、列、主对角线、副对角线减去，因此我们可以依次考虑行与另外三者重复，列与主副对角线重复，主对角线与副对角线重复的情况，这样可以考虑到所有情况。

首先考虑行与列、主对角线、副对角线：我们对于每一行使用一个集合去重，把列、两对角线中重复出现的点都加入集合。对于主对角线的处理为：\(d = i - j\)可以作为判断不同主对角线的依据，已知行找列，不妨设\(i>j\)，那么列\(j = i - d\)，副对角线同理。

后续思路几乎相同，使用集合去重。值得注意的是对于双对角线的情况时，对于\(d = i-j\)和\(e=x+y\)​，可以用方程解为整数的方法先判定会不会相交。

时间复杂度：\(O(M^2\log M)\)（常数较大）

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
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    set<int> R, C, D, E;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        R.insert(a);
        C.insert(b);
        D.insert(a - b);
        E.insert(a + b);
    }
    int ans = n * n;
    ans -= n * R.size();
    ans -= n * C.size();
    for (auto d : D) {
        ans -= n - abs(d);
    }
    for (auto e : E) {
        ans -= n - abs(n + 1 - e);
    }
    for (auto r : R) {
        set<array<int, 2>> s;
        for (auto c : C) {
            s.insert({r, c});
        }
        for (auto d : D) {
            int c = r - d;
            if (1 <= c && c <= n) {
                s.insert({r, c});
            }
        }
        for (auto e : E) {
            int c = e - r;
            if (1 <= c && c <= n) {
                s.insert({r, c});
            }
        }
        ans += s.size();
    }
    for (auto c : C) {
        set<array<int, 2>> s;
        for (auto d : D) {
            int r = c + d;
            if (1 <= r && r <= n) {
                s.insert({r, c});
            }
        }
        for (auto e : E) {
            int r = e - c;
            if (1 <= r && r <= n) {
                s.insert({r, c});
            }
        }
        ans += s.size();
    }
    for (auto d : D) {
        set<array<int, 2>> s;
        for (auto e : E) {
            if ((d + e) % 2) {
                continue;
            }
            int r = (1LL * d + e) / 2;
            int c = (1LL * e - d) / 2;
            if (1 <= r && r <= n && 1 <= c && c <= n) {
                s.insert({r, c});
            }
        }
        ans += s.size();
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}