新生夏令营第七次训练赛题解

A - 神秘的比赛#

题目大意#

给定一个只包含大写英文字母的字符串 s。

如果一个字符串包含连续的子串 "FFT" 或者 "NTT"，那么它就被认为是“困难的”。

你的任务是：重新排列字符串 s 中的字符，得到一个不困难的新字符串。输出任意一种符合要求的排列方式即可。

思路#

注意到在 ascll 码中 'F' < 'N' < 'T'，因此只要让所有的字符 T 早于 F 和 N 出现就不会出现 FFT 和 NTT。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
void solve() {
6
    string s;
7
    cin >> s;
8
    sort(s.begin(), s.end(), greater<char>()); // 从大到小排序
9
    //C++17 后可写成 sort(s.begin(), s.end(), greater())
10
    // sort 好啊，sort 得学啊
11
    cout << s << "\n";
12
}
13

14
int main() {
15
    ios::sync_with_stdio(false);
16
    cin.tie(nullptr);
17
    int t;
18
    cin >> t;
19
    while (t--) {
20
        solve();
21
    }
22
    return 0;
23
}

B - 神秘的网格#

题目大意#

给你三个整数 $n,m,k$ 。题目保证 $k \ge 2$ 并且 $n \times m$ 一定能被 $k$ 整除。

你需要构造一个 $n$ 行 $m$ 列的整数网格，并满足以下所有条件：

网格中每个整数的值都在 $1$ 到 $k$ 之间（包含 $1$ 和 $k$ ）。
从 $1$ 到 $k$ 的每个整数，在网格中出现的次数都完全相等。
任意两个相邻（共享一条边）的格子，它们里面的数不能相同。

题目保证解总是存在的，你只需要输出任意一种符合条件的构造方案即可。

思路#

这个代码的核心思想是分情况讨论，根据 m 和 k 的关系，选择了两种不同的构造策略来填满这个 $n \times m$ 的格子。

情况一：`m` 不能被 `k` 整除 (`else` 分支)#

这是比较简单的一种情况。思路是：不管行列，就当成一条直线，从头到尾用 1, 2, ..., k 这个序列循环填充。

为啥这样可行？
- 左右相邻：格子 (i, j) 和 (i, j + 1) 是挨着的，它们在填充序列里也是一前一后，所以值肯定是 t + 1 和 (t + 1) % k + 1，自然就不同啦。
- 上下相邻：格子 (i, j) 和 (i + 1, j) 在填充序列里隔了整整一行，也就是 m 个数。因为我们这个分支的条件是 m % k != 0，所以它们的值 t + 1 和 (t + m) % k + 1 肯定也不同。
- 数量相等：因为总格子数 n * m 是 k 的倍数，所以 1 到 k 这 k 个数刚好可以循环 (n * m) / k 次，每个数不多不少，正好一样多！

情况二：`m` 能被 `k` 整除 (`if` 分支)#

如果还用上面的无脑填充法，就会出问题！因为 m % k == 0，上下相邻的两个格子 (i, j) 和 (i + 1, j) 的值就会变成一样的，这就违反规则了。

所以在这里用了一个更聪明的方法：每一行都用循环序列填充，但是下一行的起始数字要比上一行错开一位！

具体怎么做的？
- 代码里 (t + i) % k + 1 就是这个思想的体现。
- t 负责在行内从 1 到 k 循环。
- i 负责在行间制造偏移。第 0 行是从 1, 2, ... 开始，第 1 行就从 2, 3, ... 开始，第 i 行就从 (i % k) + 1 开始。
为啥这样可行？
- 左右相邻：在同一行内，依然是连续的数字，肯定不同。
- 上下相邻：因为每一行的起始数字都错开了，所以 (i, j) 和 (i + 1, j) 的值也肯定不同啦。
- 数量相等：因为 m 是 k 的倍数，所以每一行都包含了整数倍个完整的 1 到 k 的循环。因此，在每一行里，1 到 k 的数量都是相等的，那整个表格里肯定也相等！

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
void solve() {
6
    int n, m, k;
7
    cin >> n >> m >> k;
8
    bool flag = m % k;
9
    int t = 0;
10
    for (int i = 0; i < n; i++) {
11
        for (int j = 0; j < m; j++) {
12
            if (flag) {
13
                cout << t + 1 << " \n"[j == m - 1];
14
            } else {
15
                cout << (t + i) % k + 1 << " \n"[j == m - 1];
16
                // i 作为偏移量，从而实现每一行都相对上一行偏移了一个位置
17
            }
18
            t = (t + 1) % k;
19
        }
20
    }
21
}
22

23
int main() {
24
    ios::sync_with_stdio(false);
25
    cin.tie(nullptr);
26
    int t;
27
    cin >> t;
28
    while (t--) {
29
        solve();
30
    }
31
    return 0;
32
}

C - 神秘的直播#

题目大意#

给定一个 $n$ 行 $m$ 列的矩阵 $a$ 。这个矩阵 $a$ 里的元素恰好是 $1$ 到 $n \cdot m$ 的一个排列（即每个数都只出现一次）。

你需要构造一个同样是 $n$ 行 $m$ 列的新矩阵 b，并满足以下两个条件：

矩阵 $b$ 也必须是 $1$ 到 $n \cdot m$ 的一个排列。
对于任意一个位置 $(i, j)$ ，新旧矩阵上对应位置的数都不能相同，即 $a_{i, j} \ne b_{i, j}$ 。

如果能构造出这样的矩阵 $b$ ，就输出任意一种方案；如果不能，就报告无解。

思路#

对从 1 到 n * m 的所有数字进行一次“循环移位”。

具体来说，就是把每个数字 x 都变成 x+1，但是有一个例外：最大的那个数 n * m，让它变成 1。这就形成了一个闭环：

1 $\rightarrow$ 2
2 $\rightarrow$ 3
$\dots$
n * m - 1 $\rightarrow$ n * m
n * m $\rightarrow$ 1

为什么这个简单的策略是正确的：

它满足了 a[i, j] != b[i, j] 的条件：因为每一个数字都被变成了另一个不同的数字（x 要么变成了 x + 1，要么最大的数变成了 1），所以对于任意位置 (i, j)，新矩阵 b 里的数 b[i, j] 肯定不会等于旧矩阵 a 里的数 a[i, j]。
它保证了矩阵 b 仍然是一个 1 到 n * m 的排列：这个“循环移位”操作非常公平，它只是把所有数字整体挪动了一下位置，没有凭空创造新的数字，也没有让任何一个数字消失。所以，原来矩阵 a 里有 1 到 n * m 各一个，那么经过这个变换后，新矩阵 b 里也必然是 1 到 n * m 各一个。
它还正确处理了唯一的无解情况：代码里有一个判断 if (n * m == 1)。这是因为当矩阵只有一个格子 1x1 时，里面的数字（必然是1）没有别的数字可以换，只能换成它自己，这就违反了 a[i, j] != b[i, j] 的规则。所以 1 x 1 的情况是无解的

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
void solve() {
6
    int n, m;
7
    cin >> n >> m;
8

9
    if (n * m == 1) {
10
        int x;
11
        cin >> x; //输入唯一的一个数
12
        cout << -1 << "\n";
13
        return;
14
    }
15

16
    for (int i = 0; i < n; i++) {
17
        for (int j = 0; j < m; j++) {
18
            int x;
19
            cin >> x;
20
            x--; // 转换成 0-base (从零开始的索引)，方便后续取模
21
            cout << (x + 1) % (n * m) + 1 << " \n"[j == m - 1];
22
            // 每个数都加一，最大的数会因为取模变成 0
23
            // 取完模后记得加回来之前减掉的 1
24
        }
25
    }
26
}
27

28
int main() {
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
    int t;
32
    cin >> t;
33
    while (t--) {
34
        solve();
35
    }
36
    return 0;
37
}

D - 神秘的回文#

题目大意#

给定一个整数 $n$ 。

你需要构造一个长度为 $n$ 的整数序列 $a=[a_1,a_2,\dots ,a_n]$ ，它必须满足以下所有条件：

序列中的每一个元素 $a_i$ 都必须满足 $1 \le a_i \le n$ 。
我们定义两个函数：
- $f(a)$ ：序列 $a$ 的最长回文子序列的长度。
- $g(a)$ ：序列 $a$ 中，长度等于 $f(a)$ 的回文子序列的数量。
最终构造出的序列 $a$ 必须满足条件： $g(a) > n$ 。

题目保证在给定的约束下，答案总是存在的。你只需要找到并输出任意一个满足条件的序列 $a$ 。

思路#

注意到当 $n = 5$ 时，我们可以构造以下序列：

a = [1,2,3,4,1]

不难发现这个数列的 $f(a) = 3$ ， $g(a) = 3$ ，显然 $g(a) = 3 \le n$ 不符合题意，但是再想想，我们在最后多放一个 $1$ 呢，我们就可以得到以下序列：

a = [1,2,3,1,1]

此时 $f(a) = 3$ ， $g(a) = 5 = n$ ，到此为止，我们可以大胆构造：

a = [1, 2, \dots, n - 3, n - 2, 1,1]

至于为什么可以，不难证明，请读者自行证明。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
void solve() {
6
    int n;
7
    cin >> n;
8

9
    vector<int> a(n);
10
    iota(a.begin(), a.end(), 1);
11
    // iota用来构造一段递增的序列
12
    // 用法：iota(起始迭代器，终止迭代器，首元素)
13
    a[n - 2] = a[n - 1] = 1;
14

15
    for (int i = 0; i < n; i++) {
16
        cout << a[i] << " \n"[i == n - 1];
17
    }
18
}
19

20
int main() {
21
    ios::sync_with_stdio(false);
22
    cin.tie(nullptr);
23
    int t;
24
    cin >> t;
25
    while (t--) {
26
        solve();
27
    }
28
    return 0;
29
}

E - 神秘的密码#

题目大意#

给定一个整数 $n$ ，你需要构造一个长度为 $n$ 的排列 $p$ （也就是包含 $1$ 到 $n$ 中所有数字，且每个数字仅出现一次的序列）。

这个排列 $p$ 需要满足一个非常特殊的条件：对于 $p$ 本身，以及它的所有循环移位（就是把最后一个元素不断地拿到最前面去），总共个不同的序列，它们每一个都必须有且仅有一个“不动点”。

如果能找到满足条件的排列，就输出任意一个；如果找不到，就输出 -1。

思路#

注意到当 $n$ 为奇数时，排列 $p = [n, n - 1, \dots,2,1]$ 满足题意。

当 $n$ 为偶数时，发现奇数的构造方法不满足题意，因此大胆猜测当 $n$ 为偶数时满足条件的排列不存在。

详细证明#

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
void solve() {
6
    int n;
7
    cin >> n;
8

9
    if (n % 2 == 0) {
10
        cout << -1 << "\n";
11
        return;
12
    }
13

14
    for (int i = n; i >= 1; i--) {
15
        cout << i << " \n"[i == 1];
16
    }
17
}
18

19
int main() {
20
    ios::sync_with_stdio(false);
21
    cin.tie(nullptr);
22
    int t;
23
    cin >> t;
24
    while (t--) {
25
        solve();
26
    }
27
    return 0;
28
}

F - 神秘的排列#

题目大意#

给定一个正整数 $n$ ，我们需要构造一个长度为 $n$ 的排列 $p$ 。

这个排列 p 需要满足一个非常特殊的条件：对于其中任意相邻的两个元素 $p_1$ 和 $p_{i+1}$ (其中 $1 \le i \le n−1$ )，它们的和 $p_i+p_{i+1}$ 都必须是一个合数。

排列 (Permutation)：就是一个包含从 1 到 n 这 n 个不同整数的数组，每个数字都恰好出现一次。
合数 (Composite)：就是一个大于 1 且不是素数的整数。换句话说，它除了 1 和它本身以外，还有别的因数。比如 4, 6, 8, 9 都是合数

如果能找到满足条件的排列，就输出任意一个。如果找不到，就输出 -1。

思路#

因为：

两个偶数的和一定是偶数
两个奇数的和也一定是偶数
所有大于 $2$ 的偶数都是合数

所以可以注意到：

两个偶数的一定是合数
两个奇数的和也一定是合数

那么我们只要把偶数放一块，奇数放一块，偶数和奇数的连接处选两个相加为合数的数字就可以了

不难发现当 $n < 5$ 时候无解，当 $n \ge 5$ 时，连接处选择 $5$ 和 $4$ ，相加为合数 $9$ 。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
void solve() {
6
    int n;
7
    cin >> n;
8

9
    if (n < 5) {
10
        cout << -1 << "\n";
11
        return;
12
    }
13

14
    for (int i = 1; i <= n; i += 2) {
15
        if (i == 5) {
16
            continue; //遇到 5 先跳过，之后在输出
17
        }
18
        cout << i << " ";
19
    }
20
    cout << "5 4" << " "; // 输出中间的连接点
21
    for (int i = 2; i <= n; i += 2) {
22
        if (i == 4) { // 之前输出过 4 了，直接跳过
23
            continue;
24
        }
25
        cout << i << " ";
26
    }
27
    cout << "\n";
28
}
29

30
int main() {
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
    int t;
34
    cin >> t;
35
    while (t--) {
36
        solve();
37
    }
38
    return 0;
39
}

G - 神秘的众数#

题目大意#

这道题是关于一个叫做「众数」(mode) 的概念。

首先，我们来理解一下什么是众数：在一个整数序列中，一个数如果出现的次数是所有数中最多的，那么它就是这个序列的众数。如果好几个数出现的次数一样多，并且都是最多的，那它们都可以是众数。

比如，在序列 [2, 2, 3] 中，2 出现了 2 次，是出现次数最多的，所以众数是 2。
又比如，在序列 [9, 9, 8, 8, 7, 7] 中，9, 8, 7 都出现了 2 次，并列第一，所以 9, 8, 7 都可以是这个序列的众数。

你的任务是：

给定一个长度为 n 的数组 a。你需要构造另一个长度也为 $n$ 的数组 $b$ ，这个数组 $b$ 必须满足以下两个条件：

数组 $b$ 中的每个元素 $b_i$ 都要满足 $1 \le b_i \le n$ 。
对于所有的下标 $i$ （从 $1$ 到 $n$ ），给定的 $a_i$ 都必须是数组 $b$ 的前缀 $[b_1,b_2,\dots ,b_i]$ 的众数。

你需要找到并输出任意一个满足条件的数组 b。

思路#

注意到当所有数的出现次数是 1，那么所有数都是众数。

因此我们只需要构造出一个长度为 $n$ 的排列 $p$ 满足对于 $(1 \le i \le n)$ ， $[a_1,a_2,\dots ,a_i]$ 中出现过的数字要出现在 $[p_1,p_2,\dots ,p_i]$ 中出现

最后我们要求的 $b$ 就是所得的 $p$

具体构造 $p$ 的方法请看代码

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
void solve() {
6
    int n;
7
    cin >> n;
8
    vector<int> a(n);
9
    vector<bool> vis(n + 1); // 判断一个数是否在 a 中出现过
10
    for (int i = 0; i < n; i++) {
11
        cin >> a[i];
12
        vis[a[i]] = true;
13
    }
14

15
    int cur = 1; // cur 表示当前没有在 a 中出现的数
16
    vector<bool> ok(n + 1); // 表示这个数字是否在 b 中出现过
17
    for (int i = 0; i < n; i++) { // 遍历 a
18
        if (ok[a[i]]) { // 在 a 中已经出现过的数
19
            while (vis[cur] || ok[cur]) {
20
                cur++; //来找未出现的数
21
            }
22
            ok[cur] = true; //用了就打上标记，用于之后的判断
23
            cout << cur << " \n"[i == n - 1];
24
        } else { // 在 a 中第一次出现的数
25
            ok[a[i]] = true;
26
            cout << a[i] << " \n"[i == n - 1];
27
        }
28
    }
29
}
30

31
int main() {
32
    ios::sync_with_stdio(false);
33
    cin.tie(nullptr);
34
    int t;
35
    cin >> t;
36
    while (t--) {
37
        solve();
38
    }
39
    return 0;
40
}

新生夏令营第七次训练赛题解

A - 神秘的比赛#

题目大意#

思路#

代码实现#

B - 神秘的网格#

题目大意#

思路#

情况一：m 不能被 k 整除 (else 分支)#

情况二：m 能被 k 整除 (if 分支)#

代码实现#

C - 神秘的直播#

题目大意#

思路#

代码#

D - 神秘的回文#

题目大意#

思路#

代码实现#

E - 神秘的密码#

题目大意#

思路#

详细证明#

代码实现#

F - 神秘的排列#

题目大意#

思路#

代码实现#

G - 神秘的众数#

题目大意#

思路#

代码实现#

情况一：`m` 不能被 `k` 整除 (`else` 分支)#

情况二：`m` 能被 `k` 整除 (`if` 分支)#