GESP 2023年C++四级编程题解析

202312-1 小杨的字典#

题目描述

在遥远的星球，有两个国家 A 国和 B 国，他们使用着不同的语言：A 语言和 B 语言。小杨是 B 国的翻译官，他的工作是将 A 语言的文章翻译成 B 语言的文章。

为了顺利完成工作，小杨制作了一本字典，里面记录了 $N$ 个 A 语言单词对应的 B 语言单词，巧合的是，这些单词都由地球上的 26 个小写英文字母组成。

小杨希望你写一个程序，帮助他根据这本字典翻译一段 A 语言文章。这段文章由标点符号 !()-.[].{}\|;:'",./?<> 和一些 A 语言单词构成，每个单词之间必定由至少一个标点符号分割，你的程序需要把这段话中的所有 A 语言单词替换成它的 B 语言翻译。特别地，如果遇到不在字典中的单词，请使用大写 UNK 来替换它。

例如，小杨的字典中包含 $2$ 个 A 语言单词 abc 和 d，它们的 B 语言翻译分别为 a 和 def，那么我们可以把 A 语言文章 abc.d.d.abc.abcd. 翻译成 B 语言文章 a.def.def.a.UNK. 其中，单词 abcd 不在词典内，因此我们需要使用 UNK 来替换它。

输入格式

第一行一个整数 $N$ ，表示词典中的条目数。保证 $N \le 100$ 。

接下来 $N$ 行，每行两个用单个空格隔开的字符串 $A$ ， $B$ ,分别表示字典中的一个 A 语言单词以及它对应的 B 语言翻译。保证所有 $A$ 不重复；保证 $A$ 和 $B$ 的长度不超过 $10$ 。

最后一行一个字符串 $S$ ，表示需要翻译的 A 语言文章。保证字符串 $S$ 的长度不超过 $1000$ ，保证字符串 $S$ 只包含小写字母以及标点符号 !()-.[].{}\|;:'",./?<> 。

输出格式

输出一行，表示翻译后的结果。

样例输入 1

2
abc a
d def
abc.d.d.abc.abcd

样例输出 1

a.def.def.a.UNK

样例输入 2

3
abc a
d def
abcd xxxx
abc,(d)d!-abc?abcd

样例输出 2

a,(def)def!-a?xxxx

样例输入 3

1
abcdefghij klmnopqrst
!()-[]{}\|;:'",./?<>abcdefghijklmnopqrstuvwxyz

样例输出 3

!()-[]{}\|;:'",./?<>UNK

代码解析

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
struct dict {
4
    string a, b;
5
} d[100];
6
int N;
7
string str, word;
8
bool is_flag(char c) {
9
    string s = "!()-.[].{}\\|;:\'\",./?<>";
10
    for (int i = 0; i < s.size(); i++) {
11
        if (c == s[i])
12
            return true;
13
    }
14
    return false;
15
}
16
string find(string s) {
17
    if (s == "") return s;
18
    for (int i = 0; i < N; i++) {
19
        if (s == d[i].a)
20
            return d[i].b;
21
    }
22
    return "UNK";
23
}
24
int main() {
25

26
    cin >> N;
27
    for (int i = 0; i < N; i++) {
28
        cin >> d[i].a >> d[i].b;
29
    }
30
    cin >> str;
31
    str += '.';
32
    for (int i = 0; i < str.size(); i++) {
33
        if (is_flag(str[i])) {
34
            cout << find(word);
35
            if (i < str.size() - 1)
36
                cout << str[i];
37
            word = "";
38
        } else {
39
            word += str[i];
40
        }
41
    }
42

43
    return 0;
44
}

202312-2 田忌赛马#

题目描述

你要和田忌赛马。你们各自有 $N$ 匹马，并且要进行 $N$ 轮比赛，每轮比赛，你们都要各派出一匹马决出胜负。

你的马匹的速度分别为 $u_1,u_2,\cdots,u_n$ ，田忌的马匹的速度分别为 $v_1,v_2,\cdots,v_n$ 。田忌会按顺序派出他的马匹，请问你要如何排兵布阵，才能赢得最多轮次的比赛？巧合的是，你和田忌的所有马匹的速度两两不同，因此不可能出现平局。

输入格式

第一行一个整数 $N$ 。保证 $1\le N \le 5\times 10^4$

接下来一行 $N$ 个用空格隔开的整数，依次为 $u_1,u_2,\cdots,u_n$ ，表示你的马匹们的速度。保证 $1\le u_i\le 2N$ 。

接下来一行 $N$ 个用空格隔开的整数，依次为 $v_1,v_2,\cdots,v_n$ ，表示田忌的马匹们的速度。保证 $1\le v_i\le 2N$ 。

输出格式

输出一行，表示你最多能获胜几轮。

样例输入 1

3
1 3 5
2 4 6

样例输出 1

样例输入 2

5
10 3 5 8 7
4 6 1 2 9

样例输出 2

提示

样例解释 1

第 1 轮，田忌派出速度为 2 的马匹，你可以派出速度为 3 的马匹迎战，本轮你获胜。

第 2 轮，田忌派出速度为 4 的马匹，你可以派出速度为 5 的马匹迎战，本轮你获胜。

第 3 轮，田忌派出速度为 6 的马匹，你可以派出速度为 1 的马匹迎战，本轮田忌获胜。

如此，你可以赢得 2 轮比赛。

代码解析

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    int a[50005], b[50005], n;
6
    cin >> n;
7
    for (int i = 0; i < n; i++)
8
        cin >> a[i];
9
    for (int i = 0; i < n; i++)
10
        cin >> b[i];
11
    sort(a, a+n);
12
    sort(b, b+n);
13
    int i = 0, j = 0, cnt = 0;
14
    while (i < n && j < n) {
15
        // 如果我们的第 i 匹马慢于田忌第 j 匹，则拿我们下一匹马继续试
16
        if (a[i] <= b[j]) {
17
            i++;
18
        } else {
19
            i++, j++;
20
        }
21
    }
22
    cout << j;
23

24
    return 0;
25
}

202309-1 进制转换#

题目描述

$N$ 进制数指的是逢 $N$ 进一的计数制。例如，人们日常生活中大多使用十进制计数，而计算机底层则一般使用二进制。除此之外，八进制和十六进制在一些场合也是常用的计数制（十六进制中，一般使用字母 A 至 F 表示十至十五；本题中，十一进制到十五进制也是类似的）。

在本题中，我们将给出个不同进制的数。你需要分别把它们转换成十进制数。

输入格式

输入的第一行为一个十进制表示的整数 $N$ 。接下来 $N$ 行，每行一个整数 $K$ ，随后是一个空格，紧接着是一个 $K$ 进制数，表示需要转换的数。保证所有 $K$ 进制数均由数字和大写字母组成，且不以 $0$ 开头。保证 $K$ 进制数合法。

保证 $N \le 1000$ ；保证 $2 \le K \le 16$ 。

保证所有 $K$ 进制数的位数不超过 $9$ 。

输出格式

输出 $N$ 行，每一个十进制数，表示对应 $K$ 进制数的十进制数值。

样例输入 1

2
8 1362
16 3F0

样例输出 1

754
1008

样例输入 2

2
2 11011
10 123456789

样例输出 2

27
123456789

提示

对于任意一个 $L$ 位 $K$ 进制数，假设其最右边的数位为第 $0$ 位，最左边的数位为第 $L-1$ 位，我们只需要将其第 $i$ 位的数码乘以权值 $K^i$ ，再将每位的结果相加，即可得到原 $K$ 进制数对应的十进制数。下面是两个例子：

八进制数 1362 对应的十进制数为： $1×8^3+3×8^2+6×8^1+2×8^0=754$ ；
十六进制数 3F0 对应的十进制数为： $3×16^2+15×16^1+0×16^0=1008$ 。

代码解析

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
int char_to_int(char c) {
4
    if ('0' <= c && c <= '9')
5
        return c - '0';
6
    return c - 'A' + 10;
7
}
8
long long k_to_dec(int k, string s) {
9
    long long num = 0;
10
    for (int i = 0; i < s.size(); i++) {
11
        num *= k;
12
        num += char_to_int(s[i]);
13
    }
14
    return num;
15
}
16
int main() {
17

18
    int n;
19
    cin >> n;
20
    while (n--) {
21
        int k;
22
        string s;
23
        cin >> k >> s;
24
        cout << k_to_dec(k, s) << endl;
25
    }
26

27
    return 0;
28
}

202309-2 变长编码#

题目描述

小明刚刚学习了三种整数编码方式：原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得，生活中很少用到 $2^{31}-1$ 这么大的数，生活中常用的 $0\sim 100$ 这种数也同样需要用 $4$ 个字节的补码表示，太浪费了些。热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下：

对于给定的正整数，首先将其表达为二进制形式。例如， $(0)_{\{10\}}=(0)_{\{2\}}$ ， $(926)_{\{10\}}=(1110011110)_{\{2\}}$ 。
将二进制数从低位到高位切分成每组 $7$ bit，不足 $7$ bit 的在高位用 $0$ 填补。例如， $(0)_{\{2\}}$ 变为 $0000000$ 的一组， $(1110011110)_{\{2\}}$ 变为 $0011110$ 和 $0000111$ 的两组。
由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上 $0$ ，否则在最高位填上 $1$ 。于是， $0$ 的变长编码为 $00000000$ 一个字节， $926$ 的变长编码为 $10011110$ 和 $00000111$ 两个字节。

这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如， $987654321012345678$ 的二进制为 $(0001101 \ 1011010 \ 0110110 \ 1001011 \ 1110100 \ 0100110 \ 1001000 \ 0010110 \ 1001110)_{\{2\}}$ ，于是它的变长编码为（十六进制表示） CE 96 C8 A6 F4 CB B6 DA 0D，共 $9$ 个字节。

你能通过编写程序，找到一个正整数的变长编码吗？

输入格式

输入第一行，包含一个正整数 $N$ 。约定 $0\le N \le 10^{18}$ 。

输出格式

输出一行，输出 $N$ 对应的变长编码的每个字节，每个字节均以 $2$ 位十六进制表示（其中， A-F 使用大写字母表示），两个字节间以空格分隔。

样例输入 1

样例输出 1

样例输入 2

样例输出 2

9E 07

样例输入 3

987654321012345678

样例输出 3

CE 96 C8 A6 F4 CB B6 DA 0D

代码解析

参考代码

1
#include<bits/stdc++.h>
2
using namespace std;
3
char int_to_char(int a);
4
string dec_to_longbin(string s1);
5
string longbin_to_hex(string s);
6
int main() {
7

8
    long long a;
9
    string s, s1, s2;
10
    cin >> a;
11
    do {
12
        s1 += int_to_char(a & 1);
13
        a = a >> 1;
14
    } while (a);
15
  s2 = dec_to_longbin(s1) + ' ';
16
    for (int i = 0; i < s2.size(); i++) {
17
        if (s2[i] != ' ') {
18
            s += s2[i];
19
        } else {
20
            cout << longbin_to_hex(s) << ' ';
21
            s = "";
22
        }
23
    }
24

25
    return 0;
26
}
27
char int_to_char(int a) {
28
    if (a < 10)
29
        return a + '0';
30
    return a - 10 + 'A';
31
}
32
string dec_to_longbin(string s1) {
33
    string s, s2;
34
    int cnt = 0;
35
    for (int i = 1; i < s1.size(); i++) {
36
        cnt++;
37
        s = s1[i-1] + s;
38
        if (i % 7 == 0) {
39
            s = '1' + s + ' ';
40
            s2 += s;
41
            s = "";
42
            cnt = 0;
43
        }
44
    }
45
    s = s1[s1.size() - 1] + s;
46
    cnt++;
47
    for (int j = 0; j < 8-cnt; j++)
48
        s = '0' + s;
49
    return s2 += s;
50
}
51
string longbin_to_hex(string s) {
52
    string s1;
53
    int n = 0, m = 0;
54
    for (int i = 0; i < 4; i++) {
55
        n *= 2;
56
        n += s[i] - '0';
57
    }
58
    s1 += int_to_char(n);
59
    for (int i = 4; i < 8; i++) {
60
        m *= 2;
61
        m += s[i] - '0';
62
    }
63
    s1 += int_to_char(m);
64
    return s1;
65
}

202306-1 幸运数#

题目描述

小明发明了一种 “幸运数”。一个正整数，其偶数位不变（个位为第 $1$ 位，十位为第 $2$ 位，以此类推），奇数位做如下变换：将数字乘以 $7$ ，如果不大于 $9$ 则作为变换结果，否则把结果的各位数相加，如果结果不大于 $9$ 则作为变换结果，否则（结果仍大于 $9$ ）继续把各位数相加，直到结果不大于 $9$ ，作为变换结果。变换结束后，把变换结果的各位数相加，如果得到的和是 $8$ 的倍数，则称一开始的正整数为幸运数。

例如， $16347$ ：第 $1$ 位为 $7$ ，乘以 $7$ 结果为 $49$ ，大于 $9$ ，各位数相加为 $13$ ，仍大于 $9$ ，继续各位数相加，最后结果为 $4$ ；第 $3$ 位为 $3$ ，变换结果为 $3$ ；第 $5$ 位为 $1$ ，变换结果为 $7$ 。最后变化结果为 $76344$ ，对于结果 $76344$ 其各位数之和为 $24$ ，是 $8$ 的倍数。因此 $16347$ 是幸运数。

输入格式

输入第一行为正整数 $N$ ，表示有 $N$ 个待判断的正整数。约定 $1 \le N \le 20$ 。

从第 $2$ 行开始的 $N$ 行，每行一个正整数，为待判断的正整数。约定这些正整数小于 $10^{12}$ 。

输出格式

输出 $N$ 行，对应 $N$ 个正整数是否为幸运数，如是则输出 T，否则输出 F。

提示：不需要等到所有输入结束再依次输出，可以输入一个数就判断一个数并输出，再输入下一个数。

样例输入 1

2
16347
76344

样例输出 1

T
F

代码解析

参考代码

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

4
int f(int a) {
5
    int sum = 0;
6
    while (a) {
7
        sum += a % 10;
8
        a /= 10;
9
    }
10
    if (sum > 9)
11
      return f(sum);
12
    return sum;
13
}
14

15
int main() {
16

17
    int n;
18
    cin >> n;
19
    while (n--) {
20
        long long num, cnt = 0;
21
        cin >> num;
22
        bool flag = true;
23
        while (num) {
24
            int ans = num % 10;
25
            if (flag) {
26
                ans *= 7;
27
                ans = f(ans);
28
            }
29
            cnt += ans;
30
            num /= 10;
31
            flag = !flag;
32
        }
33

34
        cout << (cnt % 8 == 0 ? 'T' : 'F') << endl;
35
    }
36

37
    return 0;
38
}

202306-2 图像压缩#

题目描述

图像是由很多的像素点组成的。如果用 $0$ 表示黑， $255$ 表示白， $0$ 和 $255$ 之间的值代表不同程度的灰色，则可以用一个字节表达一个像素（取值范围为十进制 0-255、十六进制 00-FF）。这样的像素组成的图像，称为 $256$ 级灰阶的灰度图像。

现在希望将 $256$ 级灰阶的灰度图像压缩为 $16$ 级灰阶，即每个像素的取值范围为十进制 0-15、十六进制 0-F。压缩规则为：统计出每种灰阶的数量，取数量最多的前 $16$ 种灰阶（如某种灰阶的数量与另外一种灰阶的数量相同，则以灰阶值从小到大为序），分别编号 0-F（最多的编号为 0，以此类推）。其他灰阶转换到最近的 $16$ 种灰阶之一，将某个点的灰阶值（灰度，而非次数）与 $16$ 种灰阶中的一种相减，绝对值最小即为最近，如果绝对值相等，则编号较小的灰阶更近。

输入格式

输入第 $1$ 行为一个正整数 $n(10\le n \le 20)$ ，表示接下来有 $n$ 行数据组成一副 $256$ 级灰阶的灰度图像。

第 $2$ 行开始的 $n$ 行，每行为长度相等且为偶数的字符串，每两个字符用十六进制表示一个像素。约定输入的灰度图像至少有 $16$ 种灰阶。约定每行最多 $20$ 个像素。

输出格式

第一行输出压缩选定的 $16$ 种灰阶的十六进制编码，共计 $32$ 个字符。

第二行开始的 $n$ 行，输出压缩后的图像，每个像素一位十六进制数表示压缩后的灰阶值。

样例输入 1

10
00FFCFAB00FFAC09071B5CCFAB76
00AFCBAB11FFAB09981D34CFAF56
01BFCEAB00FFAC0907F25FCFBA65
10FBCBAB11FFAB09981DF4CFCA67
00FFCBFB00FFAC0907A25CCFFC76
00FFCBAB1CFFCB09FC1AC4CFCF67
01FCCBAB00FFAC0F071A54CFBA65
10EFCBAB11FFAB09981B34CFCF67
01FFCBAB00FFAC0F071054CFAC76
1000CBAB11FFAB0A981B84CFCF66

样例输出 1

ABCFFF00CB09AC07101198011B6776FC
321032657CD10E
36409205ACC16D
B41032657FD16D
8F409205ACF14D
324F326570D1FE
3240C245FC411D
BF4032687CD16D
8F409205ACC11D
B240326878D16E
83409205ACE11D

提示

【样例 $1$ 解释】

灰阶 AB、CF 和 FF 出现 $14$ 次，00 出现 $10$ 次，CB 出现 $9$ 次，09 出现 $7$ 次，AC 出现 $6$ 次，07 出现 $5$ 次，10、11 和 98 出现 $4$ 次，01、1B、67、76 和 FC 出现 $3$ 次。

代码解析

参考代码

1
#include <iostream>
2
#include <string>
3
using namespace std;
4
struct int_16 {
5
    string n_16;
6
    int n = 0;
7
};
8
int char_to_int(char c) {
9
    if ('0' <= c && c <= '9')
10
        return c - '0';
11
    return c - 'A' + 10;
12
}
13
char int_to_char(int a) {
14
    if (a < 10)
15
        return a + '0';
16
    return a - 10 + 'A';
17
}
18
string dec_to_hex(int n) {
19
    string s;
20
    char c;
21
    for (int i = 0; i < 2; i++) {
22
        s = int_to_char(n % 16) + s;
23
        n /= 16;
24
    }
25
    return s;
26
}
27
int hex_to_dec(char a, char b) {
28
    return char_to_int(a) * 16 + char_to_int(b);
29
}
30
int main() {
31
    int_16 cnt[256];
32
    int pic[20][20] = {0};
33
    int cnt_16[16] = {0};
34
    int n;
35
    string s = "";
36
    cin >> n;
37
    for (int i = 0; i < n; i++) {
38
        string str;
39
        cin >> str;
40
        int j;
41
        for (j = 0; str[2*j+1]; j++) {
42
            int n_10 = 0;
43
            n_10 = hex_to_dec(str[2*j], str[2*j+1]);
44
            pic[i][j] = n_10;
45
            if (!cnt[n_10].n)
46
                cnt[n_10].n_16 = dec_to_hex(n_10);
47
            cnt[n_10].n++;
48
        }
49
        pic[i][j+1] = -1;
50
    }
51
    for (int i = 0; i < 16; i++) {
52
        for (int j = 255; j > i; j--) {
53
            if (cnt[j].n > cnt[j-1].n)
54
                swap(cnt[j], cnt[j-1]);
55
        }
56
        s += cnt[i].n_16;
57
        cnt_16[i] = hex_to_dec(cnt[i].n_16[0], cnt[i].n_16[1]);
58
    }
59
    cout << s << endl;
60
    for (int i = 0; i < n; i++) {
61
        for (int j = 0; pic[i][j+1] >= 0; j++) {
62
            int min = abs(pic[i][j] - cnt_16[0]);
63
            int idx = 0;
64
            for (int k = 1; k < 16; k++) {
65
                if (abs(pic[i][j] - cnt_16[k]) < min) {
66
                    min = abs(pic[i][j] - cnt_16[k]);
67
                    idx = k;
68
                }
69
            }
70
            cout << int_to_char(idx);
71
        }
72
        cout << endl;
73
    }
74

75
    return 0;
76
}