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

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

Day05：GESP一级2023.06_累计相加

【提交】

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

【问题描述】

输入一个正整数 ，求形如： 的累计相加。

【输入描述】

输入一个正整数。约定 。

【输出描述】

输出累计相加的结果。

【样例输入1】

3

【样例输出1】

10

【样例输入2】

4

【样例输出2】

20

【样例输入3】

10

【样例输出3】

220

参考答案：

/** [GESP202306 一级] 累计相加* https://www.luogu.com.cn/problem/B3839*/#include<iostream>using namespace std;intmain(){int n = 0;cin >> n;int sum = 0;for (int i = 1; i <= n; i++)        sum += (i + 1) * i / 2;cout << sum << endl;return 0;}

Day05：GESP二级2024.06_平方之和

【提交】

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

【问题描述】

小杨有  个正整数 ，他想知道对于所有的  ()，是否存在两个正整数  和  满足 。

【输入描述】

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

之后  行，每行包含一个正整数，代表 。

【输出描述】

对于每个正整数 ，如果存在两个正整数  和  满足 ，输出 Yes，否则输出 No。

【样例输入1】

254

【样例输出1】

YesNo

【样例解释】

对于第一个正整数，存在 ，因此答案为 Yes。

【数据范围】

对于全部数据，保证有 。

参考答案：

/** [GESP202406 二级] 平方之和* https://www.luogu.com.cn/problem/B4002*/# include<iostream># include<cmath>using namespace std;intmain(){int n;cin >> n;for (int i = 0;i < n;i++)    {int a;cin >> a;bool flag = false;for (int x = 1;x*x < a;x++)        {int y = int(sqrt(a - x * x));if (y * y + x * x == a)            {                flag = true;cout << "Yes" << endl;break;            }        }if (flag == false)        {cout << "No" << endl;        }    }return 0;}

Day05：GESP三级2023.12_小猫分鱼

【提交】

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

【问题描述】

海滩上有一堆鱼，只小猫来分。第一只小猫把这堆鱼平均分为份，多了 个，这只小猫把多的 个扔入海中，拿走了一份。第二只小猫接着把剩下的鱼平均分成份，又多了 个，小猫同样把多的个扔入海中，拿走了一份。第三、第四、……，第 只小猫仍是最终剩下的鱼分成 份，扔掉多了的 个，并拿走一份。

编写程序，输入小猫的数量以及每次扔到海里的鱼的数量，输出海滩上最少的鱼数，使得每只小猫都可吃到鱼。

例如：两只小猫来分鱼，每次扔掉鱼的数量为，为了每只小猫都可吃到鱼，可令第二只小猫需要拿走1条鱼，则此时待分配的有3条鱼。第一只小猫待分配的鱼有条。

【输入描述】

总共 2 行。第一行一个整数 ，第二行一个整数 。

保证 ；。

【输出描述】

一行一个整数，表示满足要求的海滩上最少的鱼数。

特别提醒

在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。

【样例输入1】

21

【样例输出1】

7

【样例输入2】

31

【样例输出2】

25

【样例解释2】

三只小猫来分鱼，每次扔掉鱼的数量为，为了每只小猫都可吃到鱼，可令第三只小猫需要拿走3条鱼（拿走1条和2条不满足要求），则此时待分配的有10条鱼。第二只小猫待分配的鱼有 条。第一只小猫待分配的鱼有 条。

参考答案：

/** [GESP202312 三级] 小猫分鱼* https://www.luogu.com.cn/problem/B3925*/#include<iostream>using namespace std;intmain(){longlong n, i, j, k, ans;bool flag;cin >> n >> i;    k = 1;while (true)    {        flag = true;        ans = k * n + i;for (j = 1; j < n; j++)        {if (ans % (n - 1) != 0)            {                flag = false;break;            }            ans = ans / (n - 1) * n + i;        }if (flag) break;        k++;    }cout << ans;return 0;}

Day05：GESP四级2023.06_幸运数

【提交】

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

【问题描述】

小明发明了一种“幸运数”。一个正整数，其偶数位不变（个位为第 1 位，十位为第 2 位，以此类推），奇数位做如下变换：将数字乘以 7，如果不大于 9则作为变换结果，否则把结果的各位数相加，如果结果不大于 9 则作为变换结果，否则（结果仍大于 9）继续把各位数相加，直到结果不大于 9，作为变换结果。变换结束后，把变换结果的各位数相加，如果得到的和是 8 的倍数，则称一开始的正整数为幸运数。

例如，16347：第 1 位为 7，乘以 7 结果为 49，大于 9，各位数相加为 13，仍大于 9，继续各位数相加，最后结果为 4；第 3 位为 3，变换结果为 3；第 5位为 1，变换结果为 7。最后变化结果为 76344，对于结果 76344 其各位数之和为 24，是 8 的倍数。因此 16347 是幸运数。

【输入描述】

输入第一行为正整数，表示有个待判断的正整数。约定 。

从第 2 行开始的行，每行一个正整数，为待判断的正整数。约定这些正整数小于 1012。

【输出描述】

输出行，对应个正整数是否为幸运数，如是则输出T，否则输出F。

提示：不需要等到所有输入结束在依次输出，可以输入一个数就判断一个数并输出，再输入下一个数。

【样例输入】

21634776344

【样例输出】

TF

参考答案：

/** [GESP202306 四级] 幸运数* https://www.luogu.com.cn/problem/B3850*/#include<iostream>using namespace std;// 处理奇数位数据的函数intfunc(int n){int a = n * 7;if (a <= 9)    {return a;    }int b;do    {        b = 0;// 典型的数位分离方法while (a > 0)        {            b += a % 10;            a = a / 10;        }        a = b;    } while (b > 9);return b;}intmain(){// 输入数据int N;cin >> N;for (int i = 0; i < N; i++)    {int k = 1;//记录当前处理的是第几位int total = 0;//记录累计的结果int x;cin >> x;// 典型的数位分离方法while (x > 0)        {int a = x % 10;if (k % 2 != 0)            {                total += func(a);            }else            {                total += a;            }            k += 1;            x = x / 10;        }if (total % 8 == 0)        {cout << "T" << endl;        }else        {cout << "F" << 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(){longlong 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：Openjudge2.6.2000_最长公共子上升序列

【提交】

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

【描述】

给定两个整数序列，写一个程序求它们的最长上升公共子序列。

当以下条件满足的时候，我们将长度为  的序列  称为长度为  的序列  的上升子序列：

存在  ，使得对所有 ，均有 ，且对于所有的 ，均有 。

【输入】

每个序列用两行表示，第一行是长度 ，第二行是该序列的  个整数 

【输出】

在第一行，输出两个序列的最长上升公共子序列的长度L。在第二行，输出该子序列。如果有不止一个符合条件的子序列，则输出任何一个即可。

【样例输入】

51 4 2 5 -124-12 1 2 4

【样例输出】

21 4

【参考程序】

/** 2000:最长公共子上升序列* http://noi.openjudge.cn/ch0206/2000/*/# include<iostream># include<vector>using namespace std;const int N = 505;int S[N], A[N];//dp[i][j]:S前i个元素与A前j个元素构成的以A[j]为结尾的最长公共上升子序列的长度int dp[N][N]; //seq[j]:当i为某确定值时，S前i个元素与A前j个元素构成的以A[j]为结尾的最长公共上升子序列 vector<int> seq[N];intmain(){int n, m;cin >> n;for (int i = 1; i <= n; ++i)    {cin >> S[i];    }cin >> m;for (int i = 1; i <= m; ++i)    {cin >> A[i];    }for (int i = 1; i <= n; ++i)    {for (int j = 1; j <= m; ++j)        {if (S[i] == A[j])            {                dp[i][j] = 1;                seq[j] = vector<int>();for (int k = 1; k < j; ++k)                {if (A[k] < A[j] && dp[i - 1][k] + 1 > dp[i][j])                    {                        dp[i][j] = dp[i - 1][k] + 1;                        seq[j] = seq[k];                    }                }                seq[j].push_back(A[j]);            }else                dp[i][j] = dp[i - 1][j];        }    }int msj = 1;for (int j = 1; j <= m; j++)    {if (dp[n][j] > dp[n][msj])            msj = j;    }cout << dp[n][msj] << endl;for (int i = 0; i < seq[msj].size(); ++i)    {cout << seq[msj][i] << ' ';    }return 0;}

青少年编程竞赛交流