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

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

Day05：GESP一级2024.09_美丽数字

【提交】

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

【问题描述】

小杨有  个正整数，他认为一个正整数是美丽数字当且仅当该正整数是  的倍数但不是  的倍数。

小杨想请你编写一个程序计算  个正整数中美丽数字的数量。

【输入描述】

第一行包含一个正整数 ，代表正整数个数。

第二行包含  个正整数 。

【输出描述】

输出一个整数，代表其中美丽数字的数量。

【样例输入1】

31 9 72

【样例输出1】

1

【提示】

•  既不是  的倍数，也不是  的倍数；
•  是  的倍数，不是  的倍数；
•  既是  的倍数，也是  的倍数； 因此答案为 。

对于全部数据，保证有 。

参考答案：

/** [GESP202409 一级] 美丽数字* https://www.luogu.com.cn/problem/B4035*/#include<iostream>using namespace std;intmain(){int n;cin >> n;int ans = 0;for (int i = 1;i <= n;i++)     {int x;cin >> x;if (x % 9 == 0 && x % 8 != 0)        {            ans++;        }    }cout << ans << "\n";return 0;}

Day05：GESP二级2023.09_数字黑洞

【提交】

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

【问题描述】

给定一个三位数，要求各位不能相同。例如，352是符合要求的，112是不符合要求的。将这个三位数的三个数字重新排列，得到的最大的数，减去得到的最小的数，形成一个新的三位数。对这个新的三位数可以重复上述过程。神奇的是，最终一定会得到 495！

试试看，重新排列352，得到的最大数为532，最小数为235，它们的差是297；变换297，得到972-279=693；变换693，963-369=594；变换594，954-459=495。因此，352经过4次变换得到了495。

现在，输入的三位数，你能通过编程得出，这个三位数经过多少次变换能够得到495吗？

【输入描述】

输入一行，包含一个符合要求的三位数。

【输出描述】

输出一行，包含一个整数，表示经过次变换得到495。

【样例输入1】

352

【样例输出1】

4

参考答案：

/** [GESP202309 二级] 数字黑洞* https://www.luogu.com.cn/problem/B3866*/# include<iostream># include<algrithm>using namespace std;intmain(){int N, C = 0;cin >> N;while (N!=495)    {int a, b, c;        a = N % 10;        b = N / 10 % 10;        c = N / 100;int a_ = max(max(a, b), c);int c_ = min(min(a, b), c);int b_ = a + b + c - a_ - c_;int max_ = a_ * 100 + b_ * 10 + c_;int min_ = c_ * 100 + b_ * 10 + a_;        N = max_ - min_;        C += 1;    }cout << C;return 0;}

Day05：GESP三级2024.06_移位

【提交】

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

【问题描述】

小杨学习了加密技术移位，所有大写字母都向后按照一个固定数目进行偏移。偏移过程会将字母表视作首尾相接的环，例如，当偏移量是3的时候，大写字母 A 会替换成 D，大写字母 Z 会替换成 C，总体来看，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 会被替换成 DEFGHIJKLMNOPQRSTUVWXYZABC。

注：当偏移量是26的倍数时，每个大写字母经过偏移后会恰好回到原来的位置，即大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 经过偏移后会保持不变。

【输入描述】

第一行包含一个正整数 。

【输出描述】

输出在偏移量为  的情况下，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 移位替换后的结果。

【样例输入1】

3

【样例输出1】

DEFGHIJKLMNOPQRSTUVWXYZABC

【样例解释】

当偏移量是3的时候，大写字母 A 会替换成 D，大写字母 Z 会替换成 C，总体来看，大写字母表 ABCDEFGHIJKLMNOPQRSTUVWXYZ 会被替换成 DEFGHIJKLMNOPQRSTUVWXYZABC。

【数据范围】

对于全部数据，保证有 。

参考答案：

/** GESP202406 三级 移位* https://www.luogu.com.cn/problem/B4003*/#include<iostream>#include<string>using namespace std;intmain(){int n;cin >> n;    n = n % 26;string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";string s1 = s.substr(n, 26 - n);string s2 = s.substr(0, n);cout << s1 << s2;return 0;}

Day05：GESP四级2024.09_黑白方块

【提交】

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

【问题描述】

小杨有一个  行  列的网格图，其中每个格子要么是白色，要么是黑色。

小杨想知道网格图中是否存在一个满足如下条件的子矩形：

• 子矩形由  行  列组成；
• 子矩形的第  行和第  行只包含白色格子；
• 对于子矩形的第  行和第  行，只有第  个和第  个格子是白色的，其余格子都是黑色的；

请你编写程序帮助小杨判断。

【输入描述】

第一行包含一个正整数 ，代表测试用例组数。

接下来是  组测试用例。对于每组测试用例，一共  行。

第一行包含两个正整数 ，含义如题面所示。

之后  行，每行一个长度为  的  串，代表网格图第  行格子的颜色，如果为 ，则对应格子为白色，否则为黑色。

【输出描述】

对于每组测试用例，如果存在，输出 Yes，否则输出 No。

【样例输入1】

31 401105 500000011000110000001011005 50000001100011100000101100

【样例输出1】

NoYesNo

【提示】

满足条件的子矩形形如：

0000011001100000

对于全部数据，保证有 ,,。

参考答案：

方法一：

/** GESP四级：2024.09 黑白方块* https://www.luogu.com.cn/problem/B4040*/#include<iostream>using namespace std;char arr[105][105];char ans[4][4] = {     {'0','0','0','0'},    {'0','1','1','0'},    {'0','1','1','0'},    {'0','0','0','0'} };// (i，j) 开始取16个元素boolcheck(int x, int y){for (int i = 0;i < 4;i++)    {for (int j = 0;j < 4;j++)        {if (ans[i][j] != arr[x + i][y + j])            {return false;            }        }    }return true;}boolfunc(int n, int m){if (n < 4 || m < 4)    {return false;    }for (int i = 0;i < n - 4 + 1;i++)    {for (int j = 0;j < m - 4 + 1;j++)        {//(i,j)左上角坐标if (check(i, j) == true)            {return true;            }        }    }return false;}intmain(){//1. 获取数据int T;cin >> T;for (int i = 0;i < T;i++)    {int n, m;cin >> n >> m;for (int j = 0;j < n;j++)        {for (int k = 0;k < m;k++)            {cin >> arr[j][k];            }        }cout << (func(n, m) == true ? "Yes" : "No") << endl;    }return 0;}

方法二：

/** GESP四级：2024.09 黑白方块* https://www.luogu.com.cn/problem/B4040*/#include<iostream> #include<string>using namespace std;int arr[105][105] = { 0 };int mode[4][4] = {    {0,0,0,0},    {0,1,1,0},    {0,1,1,0},    {0,0,0,0}};boolcheck(int x, int y){for (int i = 0;i < 4;i++)    {for (int j = 0;j < 4;j++)        {if (mode[i][j] != arr[x + i][y + j])            {return false;            }        }    }return true;}boolfunc(int n,int m){if (n < 4 || m < 4)return false;for (int i = 0;i < n - 4 + 1;i++)    {for (int j = 0;j < m - 4 + 1;j++)        {//i,j为左上角坐标        if (check(i, j) == true)return true;        }    }return false;}intmain(){int t,n,m;cin >> t;for (int i = 0;i < t;i++)    {// 获取数据cin >> n >> m;for (int j = 0;j < n;j++)        {string s;cin >> s;for (int k = 0;k < n;k++)            {                arr[j][k] = s[k] - '0';            }        }cout << (func(n, m)==true?"Yes":"No") << endl;    }return 0;}

Day05：GESP五级2024.12_奇妙数字

【提交】

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

【问题描述】

小杨认为一个数字  是奇妙数字当且仅当 ，其中  为任意质数且  为正整数。例如，，所以  是奇妙数字，而  不是。

对于一个正整数 ，小杨想要构建一个包含  个奇妙数字的集合 ，使其满足以下条件：

• 集合中不包含相同的数字。
•  是  的因子（即 , , ,  这  个数字的乘积是  的因子）。

小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。

【输入描述】

第一行包含一个正整数 ，含义如题面所示。

【输出描述】

输出一个正整数，代表满足条件的集合最多包含的奇妙数字个数。

【样例输入1】

128

【样例输出1】

3

【样例解释】

关于本样例，符合题意的一个包含  个奇妙数字的集合是 。首先，因为 ，，，所以 , ,  均为奇妙数字。同时， 是  的因子。

由于无法找到符合题意且同时包含  个奇妙数字的集合，因此本样例的答案为 。

【数据范围】

对于全部数据，保证有 。

参考答案：

/** [GESP202412 五级] 奇妙数字* https://www.luogu.com.cn/problem/B4070*/#include<iostream>using namespace std;intwork(int cnt){int i = 1, ans = 0;while (cnt >= i)    {        cnt -= i;        i++;        ans++;    }return ans;}intmain(){long long n, ans = 0;cin >> n;for (int i = 2; i <= n/i; i++)    {int cnt = 0;while (n % i == 0)        {            cnt++; //同一个质因数的个数            n = n / i;        }if(cnt > 0)            ans += work(cnt);    }if (n > 1)    {        ans += 1;    }cout << ans;return 0;}

Day05：GESP六级2024.06_二叉树

【提交】

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

【问题描述】

小杨有⼀棵包含  个节点的二叉树，且根节点的编号为 。这棵二叉树任意⼀个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行  次操作，每次小杨会选择⼀个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。

小杨想知道  次操作全部完成之后每个节点的颜色。

【输入描述】

第⼀行一个正整数 ，表示二叉树的节点数量。

第二行  个正整数，第 （）个数表示编号为  的节点的父亲节点编号，数据保证是⼀棵二叉树。

第三行一个长度为  的  串，从左到右第 （）位如果为 ，表示编号为  的节点颜色为白色，否则为黑色。

第四行⼀个正整数 ，表示操作次数。

接下来  行每行⼀个正整数 （），表示第  次操作选择的节点编号。

【输出描述】

输出一行一个长度为  的  串，表示  次操作全部完成之后每个节点的颜色。从左到右第 （） 位如果为 ，表示编号为  的节点颜色为白色，否则为黑色。

【样例输入1】

63 1 1 3 41001013132

【样例输出1】

010000

【样例解释】

第一次操作后，节点颜色为：

第二次操作后，节点颜色为：

第三次操作后，节点颜色为：

【数据范围】

对于全部数据，保证有 。

参考答案：

/** [GESP202406 六级] 二叉树* https://www.luogu.com.cn/problem/P10722*/# include<iostream># include<vector>using namespace std;const int N = 1e5 + 5;int n, q;int a[N], cnt[N];vector<int> v[N];//搜索x节点voiddfs(int x, int f)//f结点表示修改的次数{if (f == 1)    {        a[x] ^= 1;    }for (int i : v[x])    {        dfs(i, f ^ cnt[i]);    }}intmain(){// 1、存储数据cin >> n;for (int i = 2;i <= n;i++)    {int x;cin >> x;        v[x].push_back(i);     }for (int i = 1;i <= n;i++)    {char c;cin >> c;        a[i] = c - '0';    }cin >> q;while (q--)    {int x;cin >> x; // 主动去修改一次x        cnt[x]++;        cnt[x] %= 2;    }// 2、处理数据    dfs(1, cnt[1]);// 3、输出结果for (int i = 1;i <= n;i++)    {cout << a[i];    }return 0;}

青少年编程竞赛交流