CSES Introductory Problems

这些是寒假集训新做的题，之前做过的不会再专门写一遍题解了，如果需要代码可以看仓库。

Raab Game I#

首先，两个人的总分一定不会比牌数多，其次一个人合法的得分范围是 $\left[1, n - 1\right]$ ，只需要排序一下全部往后错一位就可以得到这两个边界，所以对于一个合法的结果一定满足

\begin{align} a + b \le n\\ a \neq 0\\ b \neq 0 \end{align}

不难发现平局不管出什么牌对其他的大小关系都没有影响，所以不妨先抽最后面的把平局的都打完，然后把剩下的排序，根据胜场数轮换其中一个人的出牌顺序就可以了。我的策略是打完平局之后，把 $a$ 的出牌顺序全部往后错 $b$ 位，让他输掉前 $b$ 场，赢后 $a$ 场。

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
int main() {
7
    ios::sync_with_stdio(0);
8
    cin.tie(0), cout.tie(0);
9
    int T;
10
    cin >> T;
11
    while (T--) {
12
        vector<int> va, vb;
13
        int n, a, b;
14
        cin >> n >> a >> b;
15
        if (a + b > n || (!a || !b) && (a | b)) {
16
            cout << "NO" << endl;
17
            continue;
18
        }
19
        while (a + b != n) {
20
            va.emplace_back(n), vb.emplace_back(n);
21
            n--;
22
        }
23
        if (n == 1) {
24
            cout << "NO" << endl;
25
            continue;
26
        }
27
        for (int i = 1; i <= n; ++i) {
28
            va.emplace_back((i + b - 1) % n + 1), vb.emplace_back(i);
29
        }
30
        cout << "YES" << endl;
31
        for (int i : va) cout << i << ' ';
32
        cout << endl;
33
        for (int i : vb) cout << i << ' ';
34
        cout << endl;
35
    }
36
    return 0;
37
}

Mex Grid Construction#

我刚开始看错题了，我本来以为鸽子里填的是一行和一列的 mex 值，又读了一遍之后发现只是前面的 mex 值，所以直接模拟即可。

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 110;
7
int a[N][N];
8
bool f[N * 2];
9

10
int main() {
11
    ios::sync_with_stdio(0);
12
    cin.tie(0), cout.tie(0);
13
    int n;
14
    cin >> n;
15
    for (int i = 1; i <= n; ++i) {
16
        for (int j = 1; j <= i; ++j) {
17
            memset(f, 0, sizeof(f));
18
            for (int k = 1; k < j; ++k) f[a[i][k]] = true;
19
            for (int k = 1; k < i; ++k) f[a[k][j]] = true;
20
            for (int k = 0; k < 200; ++k) {
21
                if (!f[k]) {
22
                    a[i][j] = a[j][i] = k;
23
                    break;
24
                }
25
            }
26
        }
27
    }
28
    for (int i = 1; i <= n; ++i) {
29
        for (int j = 1; j <= n; ++j) {
30
            cout << a[i][j] << ' ';
31
        }
32
        cout << endl;
33
    }
34
    return 0;
35
}

Knight Moves Grid#

经过查阅资料，这个 Knight 可以等价代换成中国象棋的马，边权为 1 的图上的最短路直接 bfs 即可。

1
#include <iostream>
2
#include <cstring>
3
#include <queue>
4

5
using namespace std;
6

7
const int N = 1010;
8
const int dx[] = {1, 1, -1, -1, 2, 2, -2, -2}, dy[] = {2, -2, 2, -2, 1, -1, 1, -1};
9
int v[N][N];
10

11
int main() {
12
    ios::sync_with_stdio(0);
13
    cin.tie(0), cout.tie(0);
14
    int n;
15
    cin >> n;
16
    memset(v, -1, sizeof(v));
17
    v[1][1] = 0;
18
    queue<pair<int, int>> q;
19
    q.emplace(1, 1);
20
    while (!q.empty()) {
21
        auto [x, y] = q.front();
22
        q.pop();
23
        for (int i = 0; i < 8; ++i) {
24
            int tx = x + dx[i], ty = y + dy[i];
25
            if (v[tx][ty] == -1 && 0 < tx && tx <= n && 0 < ty && ty <= n) {
26
                v[tx][ty] = v[x][y] + 1;
27
                q.emplace(tx, ty);
28
            }
29
        }
30
    }
31
    for (int i = 1; i <= n; ++i) {
32
        for (int j = 1; j <= n; ++j) cout << v[i][j] << ' ';
33
        cout << endl;
34
    }
35
    return 0;
36
}

Grid Coloring I#

一个位置合法，当且仅当和当前不一样，和左侧不一样，和上方不一样，但是每个位置有四个选择，所以一定能选出一个合法的，直接模拟即可。

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
const int N = 510;
7
int a[N][N];
8

9
int main() {
10
    ios::sync_with_stdio(0);
11
    cin.tie(0), cout.tie(0);
12
    int n, m;
13
    cin >> n >> m;
14
    memset(a, -1, sizeof(a));
15
    for (int i = 1; i <= n; ++i) {
16
        for (int j = 1; j <= m; ++j) {
17
            char c;
18
            cin >> c;
19
            a[i][j] = (c - 'A') % 4;
20
            for (int k = 0; k < 4; ++k) {
21
                if (a[i][j] != k && a[i - 1][j] != k && a[i][j - 1] != k) {
22
                    a[i][j] = k;
23
                    break;
24
                }
25
            }
26
        }
27
    }
28
    for (int i = 1; i <= n; ++i) {
29
        for (int j = 1; j <= m; ++j) {
30
            cout << char(a[i][j] + 'A');
31
        }
32
        cout << endl;
33
    }
34
    return 0;
35
}

String Reorder#

假设现在还剩 $n$ 个字符，出现次数最多的字符的出现次数为 $cnt$ 。如果一上来就 $cnt > \lceil\frac{n}{2}\rceil$ ，那一定不合法，反之合法。确保全局合法之后从前到后一个一个选

$n\ \text{is odd}\ \land\ \lceil\frac{n}{2}\rceil = cnt$ ，只能选出现次数最多的，保证合法性
否则，贪心选最小的，保证字典序

1
#include <iostream>
2

3
using namespace std;
4
const int N = 100010;
5
int cnt[26];
6

7
int main() {
8
    ios::sync_with_stdio(0);
9
    cin.tie(0), cout.tie(0);
10
    int n, mxp = 0;
11
    string s;
12
    cin >> s;
13
    n = s.length();
14
    for (char c : s) cnt[c - 'A']++;
15
    for (int j = 0; j < 26; ++j) {
16
        if (cnt[j] > cnt[mxp]) mxp = j;
17
    }
18
    if (cnt[mxp] > (n + 1 >> 1)) {
19
        cout << -1 << endl;
20
        return 0;
21
    }
22
    for (int i = 1, ls = -1; i <= n; ++i) {
23
        int pos = -1;
24
        if ((n - i + 1 & 1) && cnt[mxp] == (n - i + 2 >> 1)) pos = mxp;
25
        else for (int j = 0; j < 26; ++j) {
26
            if (cnt[j] && j != ls) {
27
                pos = j;
28
                break;
29
            }
30
        }
31
        cout << char(pos + 'A');
32
        cnt[pos]--;
33
        for (int j = 0; j < 26; ++j) {
34
            if (cnt[j] > cnt[mxp]) mxp = j;
35
        }
36
        ls = pos;
37
    }
38
    cout << endl;
39
    return 0;
40
}

Star's Blog

Raab Game I#

Mex Grid Construction#

Knight Moves Grid#

Grid Coloring I#

String Reorder#