【第36期】21天养成编程习惯:C++刷题第08天
- 2026-09-24 23:57:31
涉及考试：计算机学会编程能力等级认证（GESP） 活动内容：提供不同等级的真题供小朋友们选择练习 备考建议：根据自己备考的等级选择相应题目 附加价值：可作为白名单比赛的备考训练 本月打卡：本月打卡题目
Day08：GESP一级2025.06_值日
【提交】
https://www.luogu.com.cn/problem/B4355
【问题描述】
小杨和小红是值日生，负责打扫教室。小杨每 天值日一次，小红每 天值日一次。今天他们两个一起值日，请问至少多少天后，他们会再次同一天值日？
【输入描述】
第一行，一个正整数 ，表示小杨的值日周期；
第二行，一个正整数 ，表示小红的值日周期。
【输出描述】
一行，一个整数，表示至少多少天后他们会再次同一天值日。
【样例输入1】
46【样例输出1】
12【样例输入2】
57【样例输出2】
35【提示】
对于所有测试点，保证 。
参考答案：
/** [GESP202506 一级] 值日* https://www.luogu.com.cn/problem/B4355*/#include<iostream>using namespace std;intmain(){int m, n;cin >> m >> n;for (int i = 1; i <= m * n; i++) {if (i % m == 0 && i % n == 0) {cout << i << endl;return 0; } }return 0;}Day08：GESP二级2025.12_黄金格
【提交】
https://www.luogu.com.cn/problem/B4448
【问题描述】
小杨在探险时发现了一张神奇的矩形地图，地图有 行和 列。每个格子的坐标是 ，其中 表示行号从 到 ， 表示列号 到 。
小杨听说地图中隐藏着一些“黄金格”，这些格子满足一个神秘的数学挑战：当格子坐标 代入特定的不等式关系成立时，该格子就是黄金格。具体来说，黄金格的条件是： 。
例如，如果参数 ，那么格子 就是黄金格。因为左边坐标平方和的平方根 算出来是 ，而右边 算出来是 ， 小于等于 ，符合条件。
【输入描述】
三行，每行一个正整数，分别表示 。含义如题面所示。
【输出描述】
一行一个整数，代表黄金格数量。
【样例输入1】
442【样例输出1】
4【样例解释】
图中标注为黄色的四个格子是黄金格，坐标分别为 ，，，。
【数据范围】
对于所有测试点，保证给出的正整数不超过 。
参考答案：
/* * [GESP202512 二级] 黄金格 * https://www.luogu.com.cn/problem/B4448 */# include<iostream># include<cmath>using namespace std;intmain(){int H, W, x, cnt = 0;cin >> H >> W >> x;for (int r = 1;r <= H;r++) {for (int c = 1;c <= W;c++) {if (sqrt(r * r + c * c) <= x + r - c) { cnt++; } } }cout << cnt << endl;return 0;}Day08：GESP三级2024.03_完全平方数
【提交】
https://www.luogu.com.cn/problem/B3957
【问题描述】
小杨同学有一个包含 个非负整数的序列 ，他想要知道其中有多少对下标组合 ，使得 是完全平方数。
如果 是完全平方数，则存在非负整数 使得 。
【输入描述】
第一行一个非负整数 ，表示非负整数个数。
第二行包含 个非负整数 ，表示序列 包含的非负整数。
【输出描述】
输出一个非负整数，表示和是完全平方数的非负整数对数。
【样例输入1】
51 4 3 3 5【样例输出1】
3【样例输入2】
23 5【样例输出2】
0对于全部数据，保证有 。
参考答案：
/** [GESP202403 三级] 完全平方数* https://www.luogu.com.cn/problem/B3957*/# include<iostream># include<cmath>using namespace std;intmain(){int arr[1005];int n, cnt = 0;cin >> n;for (int i = 1;i <= n;i++) {cin >> arr[i]; }for (int i = 1;i < n;i++) {for (int j = i + 1;j <= n;j++) {int s = arr[i] + arr[j];if (int(sqrt(s)) * int(sqrt(s)) == s) { cnt += 1; } } }cout << cnt;return 0;}Day08：GESP四级2023.09_变长编码
【提交】
https://www.luogu.com.cn/problem/B3870
【问题描述】
小明刚刚学习了三种整数编码方式：原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得，生活中很少用到这么大的数，生活中常用的 这种数也同样需要用4个字节的补码表示，太浪费了些。
热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下：
1、对于给定的正整数，首先将其表达为二进制形式。例如，， 。
2、将二进制数从低位到高位切分成每组7bit，不足7bit的在高位用0填补。例如，变为的一组，变为和的两组。
3、由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上0，否则在最高位填上1。于是，0的变长编码为一个字节，926的变长编码为和两个字节。
这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，的二进制为，于是它的变长编码为（十六进制表示） ，共9个字节。
你能通过编写程序，找到一个正整数的变长编码吗？
【输入描述】
输入第一行，包含一个正整数。约定 。
【输出描述】
输出一行，输出对应的变长编码的每个字节，每个字节均以2位十六进制表示（其中，A-F使用大写字母表示），两个字节间以空格分隔。
【样例输入1】
0【样例输出1】
00【样例输入2】
926【样例输出2】
9E 07【样例输入3】
987654321012345678【样例输出3】
CE 96 C8 A6 F4 CB B6 DA 0D参考答案：
/** GESP202309 四级 变长编码* https://www.luogu.com.cn/problem/B3870*/#include<iostream>#include<string>using namespace std;// 把整数转换成二进制stringfuncto2(longlong n){string s = "";while (n != 0) {if (n % 2 == 0) { s = '0' + s; }else { s = '1' + s; } n = n / 2; }// 长度为7的倍数，前面补0int len = 7 - s.size() % 7;while (len != 0) { s = '0' + s; len -= 1; }return s;}stringto16(int i){string a;if (i >= 0 && i <= 9) { a = char('0' + i - 0); }else { a = char('A' + i - 10); }return a;}stringfuncto16(string s){int k1 = 1, k2 = 1, total1 = 0, total2 = 0;for (int i = 7;i >= 4;i--) { total1 += (s[i] - '0') * k1; k1 *= 2; }for (int i = 3;i >= 0;i--) { total2 += (s[i] - '0') * k2; k2 *= 2; }return to16(total2) + to16(total1); }intmain(){long long n;cin >> n;string s = functo2(n);int len = s.length();for (int i = len-7;i >= 0;i -= 7) {string a = s.substr(i, 7);if (i == 0) { a = '0' + a; // 最高位补0 }else { a = '1' + a; // 非最高位补1 }cout << functo16(a) << " "; }return 0;}Day08：GESP五级2024.09_挑战怪物
【提交】
https://www.luogu.com.cn/problem/B4050
【问题描述】
小杨正在和一个怪物战斗，怪物的血量为 ，只有当怪物的血量恰好为 时小杨才能够成功击败怪物。
小杨有两种攻击怪物的方式：
物理攻击。假设当前为小杨第 次使用物理攻击，则会对怪物造成 点伤害。 魔法攻击。小杨选择任意一个质数 （ 不能超过怪物当前血量），对怪物造成 点伤害。由于小杨并不擅长魔法，他只能使用至多一次魔法攻击。
小杨想知道自己能否击败怪物，如果能，小杨想知道自己最少需要多少次攻击。
【输入描述】
第一行包含一个正整数 ，代表测试用例组数。
接下来是 组测试用例。对于每组测试用例，第一行包含一个正整数 ，代表怪物血量。
【输出描述】
对于每组测试用例，如果小杨能够击败怪物，输出一个整数，代表小杨需要的最少攻击次数，如果不能击败怪物，输出 。
【样例输入1】
361889999【样例输出1】
24-1【解释】
对于第一组测试用例，一种可能的最优方案为，小杨先对怪物使用魔法攻击，选择质数 造成 点伤害，之后对怪物使用第 次物理攻击，造成 点伤害，怪物血量恰好为 ，小杨成功击败怪物。
【数据范围】
对于全部数据，保证有 ，。
参考答案：
/** [GESP202409 五级] 挑战怪物* https://www.luogu.com.cn/problem/B4050*/#include<iostream>#include<vector>using namespace std;vector<bool> Eratosthenes(int n){vector<bool> is_primes(n + 1);for (int i = 2;i * i <= n;i++) {if (is_primes[i] == 0) {for (int j = i * i;j <= n;j += i) { is_primes[j] = 1; } } }return is_primes;}intmain(){vector<bool> is_primes = Eratosthenes(1e5);int t,h;cin >> t;for (int i = 0;i < t;i++) {cin >> h;int j = 0;while (h > 0) {if (is_primes[h] == 0)break; h -= 1 << j; j++; }if (h > 0) {cout << j + 1 << endl; }elseif (h == 0) {cout << j << endl; }else {cout << "-1" << endl; } }return 0;}Day08：Openjudge3.6.1758_二叉树
【提交】
http://noi.openjudge.cn/ch0306/1758/
【描述】
如上图所示，由正整数 组成了一棵无限大的二叉树。从某一个结点到根结点（编号是1的结点）都有一条唯一的路径，比如从10到根结点的路径是 ，从4到根结点的路径是 ，从根结点1到根结点的路径上只包含一个结点1，因此路径就是 。对于两个结点 和 ，假设他们到根结点的路径分别是 和 （这里显然有 ，），那么必然存在两个正整数 和 ，使得从 和 开始，有 , , , 现在的问题就是，给定 和 ，要求 （也就是 ）。
【输入】
输入只有一行，包括两个正整数 和 ，这两个正整数都不大于1000。
【输出】
输出只有一个正整数 。
【样例输入】
10 4【样例输出】
2【参考程序】
/** 1758:二叉树* http://noi.openjudge.cn/ch0306/1758/*/# include<iostream># include<stack>using namespace std;intmain(){stack<int> st1, st2;int x, y;cin >> x >> y;while (x != 0) { st1.push(x); x = x / 2; }while (y != 0) { st2.push(y); y = y / 2; }int ans = 1;while (st1.empty()==false && st2.empty()==false) {if (st1.top() == st2.top()) { ans = st1.top(); } st1.pop(); st2.pop(); }cout << ans << endl;return 0;}青少年编程竞赛交流
「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），添加小助手微信，让他邀请大家进入学习群。进群之后大家可以参与定期组织的21天刷题打卡、等级考试测评、教育部白名单比赛辅导以及青少年编程组队竞赛等活动。
