跟老马一起“升级打怪”学编程！

• 涉及考试：计算机学会编程能力等级认证（GESP）
• 活动内容：提供不同等级的真题供小朋友们选择练习
• 备考建议：根据自己备考的等级选择相应题目
• 附加价值：可作为白名单比赛的备考训练
• 本月打卡：本月打卡题目

Day21：Openjudge1.4.16_三角形判断

【提交】

http://noi.openjudge.cn/ch0104/16/

【描述】

给定三个正整数，分别表示三条线段的长度，判断这三条线段能否构成一个三角形。

【输入】

给定三个正整数，分别表示三条线段的长度，判断这三条线段能否构成一个三角形。

【输出】

如果能构成三角形，则输出“yes” ，否则输出“no”。

【样例输入】

3 4 5

【样例输出】

yes

【参考程序】

C语言版本

/** 16:三角形判断* http://noi.openjudge.cn/ch0104/16/*/# include<cstdio>intmain(){int a, b, c;scanf("%d%d%d", &a, &b, &c);if (a + b > c && a + c > b && b + c > a)    {printf("yes");    }else    {printf("no");    }return 0;}

C++版本

/** 16:三角形判断* http://noi.openjudge.cn/ch0104/16/*/#include<iostream>#include<iomanip>using namespace std;intmain(){int a, b, c;cin >> a >> b >> c;if (a + b > c && a + c > b && b + c > a)    {cout << "yes";    }else    {cout << "no";    }return 0;}

Day21：Openjudge1.5.44_第n小的质数

【提交】

http://noi.openjudge.cn/ch0105/44/

【描述】

输入一个正整数，求第小的质数。

【输入】

一个不超过的正整数。

【输出】

第小的质数。

【样例输入】

10

【样例输出】

29

【参考程序】

C语言版本

/** 44:第n小的质数* http://noi.openjudge.cn/ch0105/44/*/#include<cstdio>intmain(){int n, a = 2, cnt = 0;scanf("%d", &n);while (cnt != n)    {bool flag = true;for (int i = 2; i * i <= a; i++)        {if (a % i == 0)            {                flag = false;break;            }        }if (flag == true)            cnt += 1;        a += 1;    }printf("%d", a - 1);return 0;}

C++语言版本

/** 44:第n小的质数* http://noi.openjudge.cn/ch0105/44/*/#include<iostream>using namespace std;intmain(){int n, a = 2, cnt = 0;cin >> n;while (cnt != n)    {bool flag = true;for (int i=2; i * i <= a; i++)        {if (a % i == 0)            {                flag = false;break;            }        }if (flag == true)            cnt += 1;        a += 1;    }cout << a-1;return 0;}

Day21：GESP三级2023.09_进制判断

【提交】

https://www.luogu.com.cn/problem/B3868

【问题描述】

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

现在有个数，请你分别判断他们是否可能是二进制、八进制、十进制、十六进制。例如，15A6F 就只可能是十六进制，而 1011 则是四种进制皆有可能。

【输入描述】

输入的第一行为一个十进制表示的整数。接下来行，每行一个字符串，表示需要判断的数。保证所有字符串均由数字和大写字母组成，且不以 0 开头。保证不会出现空行。

保证 ，保证所有字符串长度不超过10。

【输出描述】

输出行，每行4个数，用空格隔开，分别表示给定的字符串是否可能表示一个二进制数、八进制数、十进制数、十六进制数。使用 1 表示可能，使用 0 表示不可能。

例如，对于只可能是十六进制数的 15A6F，就需要输出 0 0 0 1；而对于四者皆有可能的 1011 ，则需要输出 1 1 1 1。

【样例输入1】

215A6F1011

【样例输出1】

0 0 0 11 1 1 1

【样例输入2】

4123456712345678FFGG

【样例输出2】

0 1 1 10 0 1 10 0 0 10 0 0 0

参考答案：

方法一：

/** [GESP202309 三级] 进制判断* https://www.luogu.com.cn/problem/B3868*/#include<iostream>#include<string>using namespace std;intmain(){int n;cin >> n;for (int i = 0; i < n; i++)    {string s = "1 1 1 1";string str;cin >> str;for (int j = 0; j < str.size(); j++)        {char a = str[j];if (a > '1')            {                s[0] = '0';            }if (a > '7')            {                s[2] = '0';            }if (a > '9')            {                s[4] = '0';            }if (a > 'F')            {                s[6] = '0';            }                  }cout << s << endl;    }return 0;}

方法二：

/** [GESP202309 三级] 进制判断* https://www.luogu.com.cn/problem/B3868*/#include<iostream>using namespace std;intmain(){int N;cin >> N;for (int i = 0;i < N;i++)    {string str;cin >> str;char max = '0';for (int j = 0;j < str.size();j++)        {if (str[j] > max)                max = str[j];        }cout << (max <= '1') << ' ' << (max <= '7') << ' ' << (max <= '9') << ' ' << (max <= 'F');    }return 0;}

Day21：Openjudge1.10.01_谁考了第k名

【提交】

http://noi.openjudge.cn/ch0110/01/

【描述】

在一次考试中，每个学生的成绩都不相同，现知道了每个学生的学号和成绩，求考第名学生的学号和成绩。

【输入】

第一行有两个整数，分别是学生的人数，和求第名学生的。

其后有行数据，每行包括一个学号（整数）和一个成绩（浮点数），中间用一个空格分隔。

【输出】

按照要求排序后输出一行，包含排序后的10个整数，数与数之间以一个空格分开。

【样例输入】

4 7 3 13 11 12 0 47 34 98

【样例输出】

47 13 11 7 3 0 4 12 34 98

【参考程序】

C++版本

/** 01:谁考了第k名* http://noi.openjudge.cn/ch0110/01/*/#include<iostream>#include<string>#include<algorithm>using namespace std;structStudent{string id;double score;};boolcmp(Student a, Student b){return a.score > b.score;}intmain(){    Student arr[105];int n, k;cin >> n >> k;for (int i = 0;i < n;i++)    {cin >> arr[i].id >> arr[i].score;    }    sort(arr, arr + n, cmp);cout << arr[k - 1].id << " " << arr[k - 1].score;return 0;}

Day21：GESP五级2023.09_巧夺大奖

【提交】

https://www.luogu.com.cn/problem/B3872

【问题描述】

小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：

1、游戏分为  个时间段，参加者每个时间段可以选择一个小游戏。

2、游戏中共有  个小游戏可供选择。

3、每个小游戏有规定的时限和奖励。对于第  个小游戏，参加者必须在第  个时间段结束前完成才能得到奖励 。

小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才能使得总奖励最高？

【输入描述】

输入第一行，包含一个正整数 。 既是游戏时间段的个数，也是小游戏的个数。约定 。

输入第二行，包含  个正整数。第  个正整数为 ，即第  个小游戏的完成期限。约定 。

输入第三行，包含  个正整数。第  个正整数为 ，即第  个小游戏的完成奖励。约定 。

【输出描述】

输出一行，包含一个正整数 ，为最高可获得的奖励。

【样例输入1】

74 2 4 3 1 4 670 60 50 40 30 20 10

【样例输出1】

230

【样例解释】

 个时间段可分别安排完成第 4、2、3、1、6、7、5 个小游戏，其中第 4、2、3、1、7 个小游戏在期限内完成。因此，可以获得总计  的奖励。

参考答案：

/** [GESP202309 五级] 巧夺大奖* https://www.luogu.com.cn/problem/B3872*/# include<iostream># include<algorithm>using namespace std;structGame{int T;int R;};Game games[505];boolcmp(Game n1, Game n2){return n1.R > n2.R;}int arr[505];//记录中间结果，把游戏放到合适的位置。intmain(){// 1. 存储数据int n;cin >> n;for (int i = 0;i < n;i++)    {cin >> games[i].T;     }for (int i = 0;i < n;i++)    {cin >> games[i].R;    }// 2. 处理数据int ans = 0;// 奖励降序    sort(games, games + n, cmp);for (int i = 0;i < n;i++)    {int t = games[i].T;int j = t;while (arr[j] != 0)        {            j--;        }if (j > 0)        {            arr[j] = games[i].R;            ans += arr[j];        }    }// 3. 输出结果cout << ans << endl;return 0;}

Day21：Openjudge2.6.2988_计算字符串距离

【提交】

http://noi.openjudge.cn/ch0206/2988/

【描述】

对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为：

• 修改一个字符（如把“a”替换为“b”）
• 删除一个字符（如把“traveling”变为“travelng”）

比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。

给定任意两个字符串，写出一个算法来计算出他们的距离。

【输入】

第一行有一个整数。表示测试数据的组数，接下来共行，每行两个字符串，用空格隔开。表示要计算距离的两个字符串，字符串长度不超过1000。

【输出】

针对每一组测试数据输出一个整数，值为两个字符串的距离。

【样例输入】

3abcdefg  abcdefab abmnklj jlknm

【样例输出】

104

【参考程序】

/** 2988:计算字符串距离* http://noi.openjudge.cn/ch0206/2988/*/# include<iostream># include<vector># include<algorithm>using namespace std;intEditDistance(string& str1, string& str2){int n = str1.length();int m = str2.length();vector<vector<int>> dp(n + 1, vector<int>(m + 1));for (int i = 0; i <= n; i++)    {        dp[i][0] = i;    }for (int j = 0; j <= m; j++)    {        dp[0][j] = j;    }for (int i = 1; i <= n; i++)    {for (int j = 1; j <= m; j++)        {if (str1[i - 1] == str2[j - 1])            {// 字符相同，无需操作，继承左上角的值                dp[i][j] = dp[i - 1][j - 1];            }else            {                dp[i][j] = 1 + min(                    {                         dp[i - 1][j], // 删除str1[i-1]                        dp[i][j - 1], // 在str1插入str2[j-1]                        dp[i - 1][j - 1] // 替换str1[i-1]为str2[j-1]                    });            }        }    }return dp[n][m];}intmain(){int n;cin >> n;for (int i = 0; i < n; i++)    {string str1, str2;cin >> str1 >> str2;cout << EditDistance(str1, str2) << endl;    }return 0;}

青少年编程竞赛交流