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

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

Day11：GESP一级2025.09_商店折扣

【提交】

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

【问题描述】

商店正在开展促销活动，给出了两种方案的折扣优惠。第一种方案是购物满  元减  元；第二种方案是直接打  折，也就是说价格变为原先的 。这里的  均是正整数，并且 ，。

需要注意的是，第一种方案中满减优惠只能使用一次。例如购物满  元减  元时，若挑选了价格总和为  元的物品，只能减免  元，需要支付  元。

小明在商店挑选了价格总和为  元的物品，结账时只能使用一种优惠方案。小明最少需要支付多少钱呢？

【输入描述】

一行，四个正整数 ，含义见题目描述。

【输出描述】

一行，一个小数，表示小明最少需要支付多少钱，保留两位小数。

【样例输入1】

8 7 9 10

【样例输出1】

3.00

【样例输入2】

8 7 2 11

【样例输出2】

2.20

【提示】

对于所有测试点，保证 ，，。

参考答案：

/** [GESP202509 一级] 商店折扣* https://www.luogu.com.cn/problem/B4409*/# include<iostream># include<iomanip>using namespace std;intmain(){int x, y, n, p;cin >> x >> y >> n >> p;double c = p * n / 10.0;if (p >= x)    {if (p - y < c)        {            c = p - y;        }    }cout << fixed << setprecision(2) << c << endl;return 0;}

Day11：GESP二级2024.06_计数

【提交】

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

【问题描述】

小杨认为自己的幸运数是正整数 （注：保证 ）。小杨想知道，对于从  到  的所有正整数中， 出现了多少次。

【输入描述】

第一行包含一个正整数 。

第二行包含一个正整数 。

【输出描述】

输出从  到  的所有正整数中， 出现的次数。

【样例输入1】

252

【样例输出1】

9

【样例解释】

从  到  中， 出现的正整数有 ，一共出现了  次。

【数据范围】

对于全部数据，保证有 。

参考答案：

/** [GESP202406 二级] 计数* https://www.luogu.com.cn/problem/B4007*/# include<iostream>using namespace std;intmain(){int n, k, cnt = 0;cin >> n >> k;for (int i = 1;i <= n;i++)    {int a = i;while (a != 0)        {if (a % 10 == k)            {                cnt += 1;            }            a = a / 10;        }    }cout << cnt;return 0;}

Day11：GESP三级2025.03_2025

【提交】

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

【问题描述】

小 A 有一个整数 ，他想找到最小的正整数  使得下式成立：

其中  表示二进制按位与运算， 表示二进制按位或运算。如果不存在满足条件的 ，则输出 。

【输入描述】

一行，一个整数 。

【输出描述】

一行，一个整数，若满足条件的  存在则输出 ，否则输出 。

【样例输入1】

1025

【样例输出1】

1000

【数据范围】

对于所有测试点，保证 。

【提示】

其中：

•  表示按位与运算，运算符为 &。
•  表示按位或运算，运算符为 |。

参考答案：

某一位上，a为1，b为1，这时a & b为1，a | b为1，两者之和为2，而1+1=2，相等。如果a的那一位是1，b是0，那么a & b是0，a | b是1，则总和是0+1=1，1+0=1，相等。同样，如果a为0，b为1，同理结果也是对的。如果两位都是0的话，相加结果也是0。所以每一位的和，两种情况的总和恰好等于两数的每一位的二进制位相加的总和。因此，整个数的和确实是x + y。

因此原来的等式可以简化为x + y = 2025。换句话说，y 等于2025 - x。所以问题转为，找到最小的正整数y，即若2025 - x是一个正整数，并且同时符合所有的条件。

方法一：

/** [GESP202503 三级] 2025* https://www.luogu.com.cn/problem/B4261*/#include<iostream>using namespace std;intmain(){int x;cin >> x;for (int y = 1;y <= 2025;y++)    {if ((x & y) + (x | y) == 2025)        {cout << y;return 0;        }    }cout << -1;return 0;}

方法二：

/** [GESP202503 三级] 2025* https://www.luogu.com.cn/problem/B4261*/#include<iostream>usingnamespacestd;intmain(){int x;cin >> x;cout << 2025 - x;return0;}

Day11：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(){longlong 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;}

Day11：Openjudge1.11.04_网线主管

【提交】

http://noi.openjudge.cn/ch0111/04/

【描述】

仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。

为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线越长越好，这样选手们之间的距离可以尽可能远一些。

该公司的网线主管承接了这个任务。他知道库存中每条网线的长度（精确到厘米），并且只要告诉他所需的网线长度（精确到厘米），他都能够完成对网线的切割工作。但是，这次，所需的网线长度并不知道，这让网线主管不知所措。

你需要编写一个程序，帮助网线主管确定一个最长的网线长度，并且按此长度对库存中的网线进行切割，能够得到指定数量的网线。

【输入】

第一行包含两个整数 和 ，以单个空格隔开。 是库存中的网线数，是需要的网线数量。

接下来  行，每行一个数，为库存中每条网线的长度（单位：米）。所有网线的长度至少1m，至多100km。输入中的所有长度都精确到厘米，即保留到小数点后两位。

【输出】

网线主管能够从库存的网线中切出指定数量的网线的最长长度（单位：米）。必须精确到厘米，即保留到小数点后两位。

若无法得到长度至少为1cm的指定数量的网线，则必须输出“0.00”（不包含引号）。

【样例输入】

4 118.027.434.575.39

【样例输出】

2.00

【参考程序】

题目问：要找最长的网线长度。对应的模板为：求满足某一条件的最大值。

网线长度需要满足的条件为：将库存中的网线按该长度进行切割，得到的网线数量大于等于居民需要的网线数量。

假设要判断网线长度  是否满足条件，先遍历所有库存中网线长度，每条网线长度记为 ，那么  即为这条库存网线可以切出的成品网线的条数，加和求出总条数。看处理得到的网线总条数是否大于等于居民需要的网线数量 ，如果是，那么满足条件，否则不满足条件。

/** 04:网线主管* http://noi.openjudge.cn/ch0111/04/submit/*/#include<iostream>#include<iomanip>using namespace std;int n, k, a[10005];//a[i]:第i条网线的长度 单位：厘米 boolcheck(int l){//如果需要网线长度为l，最多可以得的网线段数是否大于等于k longlong ct = 0;//计数for (int i = 1; i <= n; ++i)        ct += a[i] / l;//整除运算return ct >= k;}intmain(){double t;cin >> n >> k;for (int i = 1; i <= n; ++i)    {cin >> t;        a[i] = int(t * 100);//单位变为厘米    }if (check(1) == false)    {//如果切成1厘米一段也不能达到要求的数量，则没有切割方案cout << "0.00";return 0;    }int l = 1, r = 1e7;while (l <= r)//二分答案求满足条件的最大值    {int m = (l + r) / 2;if (check(m))//如果网线长为m满足条件            l = m + 1;else            r = m - 1;    }cout << fixed << setprecision(2) << (double)r / 100;//单位转为米return 0;}

Day11：Openjudge3.3.1696_波兰表达式

【提交】

http://noi.openjudge.cn/ch0303/1696/

【描述】

波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值，其中运算符包括+ - * /四个。

【输入】

输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。

【输出】

输出为一行，表达式的值。

可直接用printf("%f\n", v)输出表达式的值v。

【样例输入】

* + 11.0 12.0 + 24.0 35.0

【样例输出】

1357.000000

【提示】

可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。

此题可使用函数递归调用的方法求解。

【参考程序】

/** 1696:波兰表达式* http://noi.openjudge.cn/ch0303/1696/*/# include<iostream># include<string># include<iomanip>using namespace std;string s;doublef(){cin >> s;if (s == "+")return f() + f();else if (s == "-")return f() - f();else if (s == "*")return f() * f();else if (s == "/")return f() / f();elsereturn stod(s);}intmain(){cout << fixed << setprecision(6) << f();return 0;}

青少年编程竞赛交流