GESP 四级题单（简单） • 附免费参考答案

[GESP样题 四级] 绝对素数

题目描述

如果一个两位数是素数，且它的数字位置经过对换后仍为素数，则称为绝对素数，例如 $13$。给定两个正整数 $A,B$，请求出大于等于 $A$、小于等于 $B$ 的所有绝对素数。

输入格式

输入 $1$ 行，包含两个正整数 $A$ 和 $B$。保证 $10<A<B<100$。

输出格式

若干行，每行一个绝对素数，从小到大输出。

样例 #1

样例输入 #1

11 20

样例输出 #1

11
13
17

参考答案

// absolutePrime.cpp
// 素筛、模拟
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int l, r;

bool isPrime(string num)
{
    int n = stoi(num);
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    cin >> l >> r;
    for (int i = l; i <= r; i++)
    {
        string num2 = to_string(i);
        string num1 = num2;
        reverse(num2.begin(), num2.end());
        if (isPrime(num1) && isPrime(num2))
        {
            cout << i << endl;
        }
    }
    return 0;
}

[GESP样题 四级] 填幻方

题目描述

在一个 $N\times N$ 的正方形网格中，每个格子分别填上从 1 到 $N\times N$ 的正整数，使得正方形中任一行、任一列及对角线的几个数之和都相等，则这种正方形图案就称为“幻方”（输出样例中展示了一个 $3\times 3$ 的幻方）。我国古代称为“河图”、“洛书”，又叫“纵横图”。

幻方看似神奇，但当 $N$ 为奇数时有很方便的填法：

1. 一开始正方形中没有填任何数字。首先，在第一行的正中央填上 $1$。
2. 从上次填数字的位置向上移动一格，如果已经在第一行，则移到同一列的最后一行；再向右移动一格，如果已经在最右一列，则移动至同一行的第一列。如果移动后的位置没有填数字，则把上次填写的数字的下一个数字填到这个位置。
3. 如果第 2 步填写失败，则从上次填数字的位置向下移动一格，如果已经在最下一行，则移到同一列的第一行。这个位置一定是空的（这可太神奇了！）。把上次填写的数字的下一个数字填到这个位置。
4. 重复 2、3 步骤，直到所有格子都被填满，幻方就完成了！

快来编写一个程序，按上述规则，制作一个 $N\times N$ 的幻方吧。

输入格式

输入为一个正奇数 $N$，保证 $3\le N\le 21$。

输出格式

输出 $N$ 行，每行 $N$ 个空格分隔的正整数，内容为 $N\times N$ 的幻方。

样例 #1

样例输入 #1

3

样例输出 #1

8 1 6
3 5 7
4 9 2

参考答案

// magicSquare.cpp
// 数组、模拟
#include <iostream>
using namespace std;

int n;
int x, y;
int tx, ty;
int fnum = 1;
int a[25][25];

int main()
{
    // 输入
	cin >> n;
	
	// 第一步
	x = 1;
	y = n/2+1;
	a[x][y] = 1;
	
	// 第二步 & 第三步
	while (fnum < n * n)
	{
	    // 试图完成第二步
		tx = x;
		ty = y;
		tx = ((tx == 1) ? n : tx - 1);
		ty = ((ty == n) ? 1 : ty + 1);
		if (a[tx][ty] == 0)
		{
			a[tx][ty] = ++fnum;
			x = tx, y = ty;
			continue;
		}
		
		// 第二步失败，完成第三步
		tx = x, ty = y;
		tx = ((tx == n) ? 1 : tx + 1);
		a[tx][ty] = ++fnum;
		x = tx, y = ty;
	}
	
	// 输出
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

[GESP202309 四级] 进制转换

题目描述

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

2
8 1362
16 3F0

样例输出 #1

754
1008

样例 #2

样例输入 #2

2
2 11011
10 123456789

样例输出 #2

27
123456789

提示

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

1. 八进制数 1362 对应的十进制数为：$1\times 8^3+3\times 8^2+6\times 8^1+2\times 8^0=754$；

2. 十六进制数 3F0 对应的十进制数为：$3\times 16^2+15\times 16^1+0\times 16^0=1008$。

参考答案

// toDecimalNumber.cpp
// 字符串、进制
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int n;
int len;
int base;
char num[15];
int num2[15];
long long sum;

int main()
{
    cin >> n;
    
    while (n--)
    {
        // 输入
        cin >> base >> num;
        
        // 转十进制数
        len = strlen(num);
        sum = 0;
        
        // 1. 转对应数字
        for (int i = 0; i < len; i++)
        {
            if (num[i] >= '0' && num[i] <= '9')
            {
                num2[i] = num[i] - '0';
            }
            else
            {
                num2[i] = 10 + (num[i] - 'A');
            }
        }
        // 2. 权值展开求和
        for (int i = 0; i < len; i++)
        {
            sum += num2[i] * pow(base, len-i-1);
        }
        // 上述内容可以合二为一
        
        // 输出
        cout << sum << endl;
    }
    return 0;
}

★[GESP202312 四级] 小杨的字典

题目描述

在遥远的星球，有两个国家 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

样例输入 #1

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

样例输出 #1

a.def.def.a.UNK

样例 #2

样例输入 #2

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

样例输出 #2

a,(def)def!-a?xxxx

样例 #3

样例输入 #3

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

样例输出 #3

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

新知

在这类字符串替换的题目当中，我们一般使用 map 容器进行作答。

map 容器，是 STL 关联容器，它提供一对一的数据处理能力，很类似 Python 中的字典。这里的字典指的就是生活中的字典，会有东西和对应的解释两个部分组成。

而 map 容器也非常适合 [GESP202312 四级] 小杨的字典。

map 容器的定义方法：

#include <map>
// 格式: map<查找东西的数据类型, 对应解释的数据类型> 容器名字;
// 示例:
map<string, string>dic; // 这个就是本题的定义方法

当然，[GESP202312 四级] 小杨的字典 也可以使用两个数组进行作答。

参考答案

// dictionary.cpp
#include <iostream>
#include <string>
#include <map>
using namespace std;

int n;
string a, b;
string tmp;
string s, ans;
map<string, string>m;

int main()
{
    // 输入
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a >> b;
        m[a] = b;
    }
    cin >> s;
    s += '.'; // 结束符
    
    for (char c : s)
    {
        if (c >= 'a' && c <= 'z')
        {
            tmp += c;
        }
        else
        {
            if (tmp != "")
            {
                if (m.count(tmp))
                {
                    ans += m[tmp];
                }
                else
                {
                    ans += "UNK";
                }
                tmp = "";    
            }
            ans += c;
        }
    }
    ans.pop_back();
    
    // 输出
    cout << ans;
    return 0;
}

代码详解

[GESP202403 四级] 相似字符串

题目描述

对于两个字符串 $A$ 和 $B$，如果 $A$ 可以通过删除一个字符，或插入一个字符，或修改一个字符变成 $B$，那么我们说 $A$ 和 $B$ 是相似的。

比如 $\text{apple}$ 可以通过插入一个字符变成 $\text{applee}$，可以通过删除一个字符变成 $\text{appe}$，也可以通过修改一个字符变成 $\text{bpple}$。因此 $\text{apple}$ 和 $\text{applee}$、$\text{appe}$、$\text{bpple}$ 都是相似的。但 $\text{applee}$ 并不能 通过任意一个操作变成 $\text{bpple}$，因此它们并不相似。

特别地，两个完全相同的字符串也是相似的。

给定 $T$ 组 $A,B$，请你分别判断它们是否相似。

输入格式

第一行一个正整数 $T$。
接下来 $T$ 行，每行两个用空格隔开的字符串 $A$ 和 $B$。

输出格式

对组 $A,B$，如果他们相似，输出 similar，否则输出 not similar。

样例 #1

样例输入 #1

5
apple applee
apple appe
apple bpple
applee bpple
apple apple

样例输出 #1

similar
similar
similar
not similar
similar

提示

对全部的测试数据，保证 $1\le T\le 100$，$A$ 和 $B$ 的长度不超过 $50$，仅含小写字母。

参考答案

// similarString.cpp
// 字符串、双指针
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int T;
string A, B;

bool isSimilar(string A, string B)
{
    // 两者完全相同
    if (A == B) return true;
    
    // 初始化
    int m = A.length();
    int n = B.length();
    int cnt = 0; // 记录变化字符数量
    int l = 0, r = 0; // 记录插入、删除的位置
    
    
    // 长度差大于1
    if (abs(m-n) > 1) return false;
    
    // 两者长度相等，判断是否只修改了一个字符
    else if (m - n == 0)
    {
        for (int i = 0; i < m; i++)
        {
            if (A[i] != B[i]) cnt++;
            if (cnt > 1) return false;
        }
    }
    
    // 两者长度相差1
    else
    {
        // B比A多一个字符，判断是否插入一个字符
        if (m - n == -1)
        {
            int i = 0, j = 0;
            while (i < m)
            {
                if (A[i] != B[j])
                {
                    // 记录插入的位置
                    l = i;
                    r = j;
                    // 直接比较后面的字符是否相等
                    while (i < m && j < n)
                    {
                        if (A[i] != B[j+1]) return false;
                        i++;
                        j++;
                    }
                    
                    // 如果后面的字符都相等，则必须是A的剩余字符都相等
                    if (i < m) return false;
                    break;
                }
                else
                {
                    i++;
                    j++;
                }
            }
        }
        
        // A比B多一个字符，判断是否删除一个字符
        else
        {
            int i = 0, j = 0;
            while (i < m)
            {
                if (A[i] != B[j])
                {
                    // 记录删除的位置
                    l = j;
                    r = i;
                    // 直接比较后面的字符是否相等
                    while (i < m && j < n)
                    {
                        if (A[i+1] != B[j]) return false;
                        i++;
                        j++;
                    }
                    
                    // 如果后面的字符都相等，则必须是B的剩余字符都相等
                    if (j < n) return false;
                    break;
                }
                else
                {
                    i++;
                    j++;
                }
            }
        }
    }
    
    return true;
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> A >> B;
        cout << (isSimilar(A, B) ? "similar\n" : "not similar\n");
    }
    return 0;
}