GESP认证C++编程真题解析 | 202412 五级

​欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！

专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。

适合人群：

• 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
• 希望系统学习C++/Python编程的初学者
• 想要提升算法与编程能力的编程爱好者

附上汇总帖：GESP认证C++编程真题解析 | 汇总

编程题

B4070 奇妙数字

【题目来源】

洛谷：B4070 [GESP202412 五级] 奇妙数字 - 洛谷

【题目描述】

小杨认为一个数字x xx是奇妙数字当且仅当x = p a x=p^ax=pa，其中p pp为任意质数且a aa为正整数。例如，8 = 2 3 8=2^38=23，所以8 88是奇妙的，而6 66不是。

对于一个正整数n nn，小杨想要构建一个包含m mm个奇妙数字的集合{ x 1 , x 2 , ⋯ , x m } \{x_1,x_2,⋯,x_m\}{x1​,x2​,⋯,xm​}，使其满足以下条件：

• 集合中不包含相同的数字。
• x 1 × x 2 × ⋯ × x m x_1×x_2×⋯×x_mx1​×x2​×⋯×xm​是n nn的因子（即x 1 , x 2 , ⋯ , x m x_1,x_2,⋯,x_mx1​,x2​,⋯,xm​这m mm个数字的乘积是n nn的因子）。

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

【输入】

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

【输出】

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

【输入样例】

128

【输出样例】

3

【算法标签】

《洛谷 B4070 奇妙数字》 #GESP# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong// 使用长整型intn,ans;// n: 输入的数, ans: 存储结果// 计算将一个数x表示为连续整数和所需的最少项数intcalc(intx){inttemp=1,res=0;// temp: 当前项的值, res: 项数计数while(x>=temp){x=x-temp;// 减去当前项temp++;// 下一项增加1res++;// 项数增加}returnres;}signedmain(){cin>>n;// 输入要分解的数// 质因数分解for(inti=2;i*i<=n;i++){if(n%i==0){// 找到质因数iintcnt=0;// 计算该质因数的指数while(n%i==0){cnt++;n/=i;}// 将指数分解为连续整数和ans+=calc(cnt);}}// 处理剩余的质因数（如果有）if(n!=1)ans++;cout<<ans<<endl;return0;}

【运行结果】

128 3

B4071 武器强化

【题目来源】

洛谷：[B4071 GESP202412 五级] 武器强化 - 洛谷

【题目描述】

小杨有n nn种武器和m mm种强化材料。第i ii种强化材料会适配第p i p_ipi​种武器，小杨可以花费c i c_ici​金币将该材料对应的适配武器修改为任意武器。

小杨最喜欢第1 11种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

【输入】

小杨有n nn种武器和m mm种强化材料。第i ii种强化材料会适配第p i p_ipi​种武器，小杨可以花费c i c_ici​金币将该材料对应的适配武器修改为任意武器。

小杨最喜欢第1 11种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

【输出】

输出一个整数，代表能够使适配第1 11种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。

【输入样例】

4 4 1 1 2 1 3 1 3 2

【输出样例】

1

【算法标签】

《洛谷 B4071 武器强化》 #GESP# #2024#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1005;intn,m,p,c,ans=1e18;vector<int>a[N];// 计算让1号孩子获得x票的最小花费intf(intx){intcnt=x-a[1].size();// 需要从其他孩子那里获取的票数vector<int>temp;// 存储可以购买的武器intres=0;// 总花费// 处理其他孩子for(inti=2;i<=n;i++){if(a[i].empty())continue;// 计算需要从这个孩子拿走多少武器intsz=max(0LL,(longlong)(a[i].size()-x+1));// 拿走最便宜的sz个武器for(intj=0;j<sz;j++){res+=a[i][j];cnt--;}// 如果已经超过当前最优解，提前返回if(res>=ans)returnans;// 剩余的武器加入可选列表for(intj=sz;j<a[i].size();j++){temp.push_back(a[i][j]);}}// 如果还需要更多票，从剩余的武器中选择最便宜的if(cnt>0){sort(temp.begin(),temp.end());for(inti=0;i<cnt&&i<temp.size();i++){res+=temp[i];}}returnres;}signedmain(){cin>>n>>m;// 读入数据并排序for(inti=1;i<=m;i++){cin>>p>>c;a[p].push_back(c);}// 对每个孩子的武器按价格排序for(inti=1;i<=n;i++){sort(a[i].begin(),a[i].end());}// 尝试让1号孩子获得从当前票数到总票数的各种可能intmin_votes=max((longlong)a[1].size(),1LL);for(inti=min_votes;i<=m;i++){ans=min(ans,f(i));}cout<<ans<<endl;return0;}

【运行结果】

4 4 1 1 2 1 3 1 3 2 1