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

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$ 次。

代码解析

先读懂题目，题目给出的数据每两位代表一个 16 进制数字，所以第一步处理，我们两两转换成 10 进制数，保存在 pic 数组中，同时统计每个数字出现的次数，保存在 cnt 数组中。压缩的规则是：出现最多次数最多的前 $16$ 个数字，分别修改为 0-F（也就是 0 到 15）。其他的数字需要在 $16$ 个数字中找到差值最小的一个，转换为对应的编号。

提供一个思路，把 0 ~ 255 这 $256$ 个数字按照数组 cnt 中统计的出现次数从大到小排序，保存在 top_16 数组中，数组中的值类似 {235, 23, 43, 143...}，下标就是他们的名次。然后修改 cnt 数组，把 top_16 数组的下标和值反过来，保存在 cnt 数组中，这样就可以通过 cnt[i] 得到数字 i 对应的排名。最后遍历 pic 数组，编写函数 pic_to_char，根据 pic[i][j] 在 cnt 数组中的排名进行处理，如果排名在前 $16$ 名，直接输出对应的十六进制字符；否则，找到排名前 $16$ 名中与 pic[i][j] 差值最小的一个，输出对应的十六进制字符。

1
#include <bits/stdc++.h>
2
using namespace std;
3
int n, m = 0;
4
int pic[25][25];
5
int cnt[256];
6
int top_16[256];
7
int hex_to_int(char a, char b) {
8
  if (isdigit(a)) a -= '0';
9
  else a = a - 'A' + 10;
10
  if (isdigit(b)) b -= '0';
11
  else b = b - 'A' + 10;
12
  return a * 16 + b;
13
}
14
char int_to_char(int a) {
15
  if (a < 10) return a + '0';
16
  return a - 10 + 'A';
17
}
18
string int_to_hex(int a) {
19
  string s;
20
  s += int_to_char(a / 16);
21
  s += int_to_char(a % 16);
22
  return s;
23
}
24
bool cmp(int a, int b) {
25
  if (cnt[a] != cnt[b])
26
    return cnt[a] > cnt[b];
27
  return a < b;
28
}
29
char pic_to_char(int a) {
30
  if (cnt[a] < 16) return int_to_char(cnt[a]);
31
  int ans = 256, idx = 0;
32
  // 打擂台找前16个数字的最小差值
33
  for (int i = 0; i < 16; i++)
34
    if (abs(top_16[i] - a) < ans) {
35
      idx = i;
36
      ans = abs(top_16[i] - a);
37
    }
38
  return int_to_char(idx);
39
}
40
int main() {
41

42
  string s;
43
  cin >> n;
44
  for (int i = 0; i < n; i++) {
45
    cin >> s;
46
    int num = 0;
47
    // 这里把每两个字符转成10进制保存起来
48
    for (int j = 0; j < s.size(); j+=2) {
49
      pic[i][j/2] = hex_to_int(s[j], s[j+1]);
50
      cnt[pic[i][j/2]]++;
51
    }
52
  }
53
  m = s.size()/2;  // 记录一下一行有几个16进制数字
54

55
  // 填充 0 ~ 255
56
  for (int i = 0; i < 256; i++) top_16[i] = i;
57
  // 按照cnt[i]中每个数字i出现的次数序
58
  // 之后只采用前16名
59
  sort(top_16, top_16+256, cmp);
60
  // 构造一个下标到排名的对应关系
61
  for (int i = 0; i < 256; i++) cnt[top_16[i]] = i;
62

63
  for (int i = 0; i < 16; i++)
64
    cout << int_to_hex(top_16[i]);
65

66
  cout << endl;
67
  for (int i = 0; i < n; i++) {
68
    for (int j = 0; j < m; j++)
69
      cout << pic_to_char(pic[i][j]);
70
    cout << endl;
71
  }
72

73
  return 0;
74
}

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$ 。

代码解析

课堂中讲过的原题，注意字符转数字的方法，还有输入的数可能会超过 int 范围，需要用 long long 存储。

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

代码解析

将输入的正整数转换为二进制形式，然后从低位到高位切分成每组 $7$ bit，处理完成之后，将每组从二进制字符串转换为十六进制，最后输出。

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-while 循环，因为 a 可能为 0
12
    do {
13
        s1 += int_to_char(a & 1);
14
        a = a >> 1;
15
    } while (a);
16
    // 末尾补一个空格，方便分割
17
  s2 = dec_to_longbin(s1) + ' ';
18
    for (int i = 0; i < s2.size(); i++) {
19
        if (s2[i] != ' ') {
20
            s += s2[i];
21
        } else {
22
            cout << longbin_to_hex(s) << ' ';
23
            s = "";
24
        }
25
    }
26

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

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

代码解析

这道题是一个简单的字符串处理问题。我们可以用一个结构体数组来存储字典中的每个条目，每个条目包含一个 A 语言单词和它对应的 B 语言翻译。然后，我们可以遍历输入的字符串，每次遇到一个单词，就遍历数组，找到它对应的 B 语言翻译，替换成它。如果没有找到，就用 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 轮比赛。

代码解析

双指针的思想，因为我们处于上帝视角，所以可以先对我们和田忌的马匹进行排序，然后用两个下标 i 和 j，分别指向我们和田忌的第 1 匹马，每次比较我们的第 i 匹马和田忌的第 j 匹，如果我们的第 i 匹马快于田忌的第 j 匹，那么我们就可以用我们的第 i 匹马迎战田忌的第 j 匹，否则，我们就需要用我们的下一匹马继续试，只有我们赢的时候，j 才会增加，所以 j 也就是我们的胜利轮数。

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
}