2022年第四届全国高校计算机能力挑战赛决赛编程题(C++)第一套试卷
2022年第四届全国高校计算机能力挑战赛决赛第一套试卷个人解答源码及思路，非评分标准答案。（程序设计赛 C+）1.小明有个嗜好，他特别喜欢“完全立方数”，比如2197=13*13*13,9261=21*21*21，那么2197和9261就是完全立方数。有时候小明会给自己选定某个幸运数字代表自己的气运，比如他某天选定了11作为自己的幸运数字，那么所有11的倍数也都是小明当天的幸运数。今天小明想把区间a，b之间的完全立方数找出来，同时把他今天的幸运立方数给找出来。小明今天选定的幸运数字是x，那么请你数一下区间a，b之间是完全立方数且包含x的倍数的数字有多少个？输入格式：输入一行，用空格隔开的三个整数a、b、x，其中1a=b=1018，1x109。输出格式：输出一行，一个整数，表示满足条件的数的个数输入。输入样例1：3 27 4输出样例1：1参考源码：1. #include2. #include3. usingnamespacestd;4. typedeflonglongintllInt;5. intmain()6. llIntl,r,x,counter=0;7. cinlrx;8. llIntfromData=pow(l,1.0/3);9. llInttoData=pow(r,1.0/3);10. for(inti=fromData;i=toData;i+)11. 12. llInttempData=i*i*i;13. if(tempData%x=0)14. counter+;15. 16. 17. coutcounterendl;18. return0;19. 算法思路： 主要是降低循环次数，将3a 作为循环的起始值，将3b 作为循环的结束值。运行截图：测试用例1（题目输入样例1）8测试用例227 216 729测试用例310002.小李计划编写一个关于幂运数的自动答题机器人程序。机器人运行的规则是这样的：每当用户输入一个数Ai时，机器人就会自动回答下面2个问题：1)用户所输入的前i-1个数中有多少个数是Ai的幂运数；2)这些幂运数的累加和是多少。你能帮助小李完成这个自动答题机器人程序吗?说明：如果一个整数x可以表示成另一个整数y的多次幂，即：x=y*y*y*y(y的个数至少为2)，那么我们就说x是y的幂运数。输入格式：第1行：一个整数N，表示用户会进行N次数据输入，1=N=106。第2到N+1行：每行一个正整数，其中第i+1行的正整数是用户第i次输入的数Ai，2=Ai=106。输出格式：N行：每行两个空格分隔的整数，其中第i行表示机器人对用户第i次输入数据的回答（Ai的幂运数个数，以及它们的累加和除以99999的余数）.输入样例1：38193输出样例1：0 01 812 90参考源码：1. #include2. usingnamespacestd;3. constintmaxNumber=1e6+10;4. constintMOD=99999;5. intvisitedmaxNumber;6. intN;7. intmain()8. cinN;9. intmaxData=0;10. for(inti=0;iai;15. visitedai+;16. inttemp=ai*ai;17. while(temp=maxData)18. counter+=visitedtemp;19. sum=(sum+temp*visitedtemp)%MOD;20. temp*=ai;21. 22. coutcountersumendl;23. maxData=max(maxData,ai);24. 25. return0;26. 算法思路：全局数组的最大值为2G，满足本题的要求106（按照int长度为4进行计算）；当读入一个ai时，把ai在maxData范围内的全部幂运数进行统计和累加。visited用幂运数作为下标，出现次数作为值（没有出现则值为0，这样在上面进行统计和累加的时候不影响，不需要单独处理，保持了代码的统一性）。运行截图：测试用例1（题目输入样例1）测试用例2测试用例33.小张的工厂里的厂房受到台风的袭击，导致部分厂房的顶棚遭到了破坏，急需修理。厂房是由一间间的相同宽度的隔间组成，这些隔间都是连在一起的，连成了一条直线，隔间采用塑钢板作为顶棚，多个隔间可以共用一块长的塑钢板。这些隔间里有的有货物，有的没有货物，因为考虑到最近可能还会有台风，所以必须把有货物的隔间的顶棚修理好。目前塑钢板的供应商能提供的板材的数量有限制，但长度没有限制，所以小张只能尽量的减少板材的数量。请你帮助小张计算需要采购塑钢板的最小长度。输入格式：第1行：M，S和C（用空格分开)。M为能买到的板材的最大数目（1=M=50），S为厂房总的隔间的数量，1=S=200，C为有货物的隔间的数量。第2到C+1行：每行包含一个整数，表示有货物的隔间的编号。编号从1开始，1=C=S。输出格式：输出一行，采购的塑钢板的总长度。输入样例1：1 10 42 5 7 8输出样例1：7输入样例2：3 30 73131517202429输出样例2：14参考源码：1. #include2. #include3. usingnamespacestd;4. #defineMAX_VERTEX_NUM2005. structedge6. intbegin;7. intend;8. intweight;9. edgesMAX_VERTEX_NUM*(MAX_VERTEX_NUM-1)/2+1;10. intvertexMAX_VERTEX_NUM+1;11. intpreMAX_VERTEX_NUM+1;12. intedgeNum;13. intM,S,C;14. boolcmp(structedgea,structedgeb)15. 16. returna.weightMSC;36. for(inti=1;ivertexi;39. prevertexi=vertexi;40. for(intj=1;ji;+j)41. 42. edges+edgeNum.begin=vertexi;43. edgesedgeNum.end=vertexj;44. edgesedgeNum.weight=abs(vertexi-vertexj);45. 46. 47. sort(edges+1,edges+edgeNum+1,cmp);48. intminCost=0;49. intcount=0;50. for(inti=1;i=edgeNum;i+)51. intbeginNode=edgesi.begin;52. intendNode=edgesi.end;53. intweight=edgesi.weight;54. if(find(beginNode)!=find(endNode)55. 56. count+;57. Merge(beginNode,endNode);58. minCost+=weight;59. if(count=C-M)60. 61. break;62. 63. 64. 65. minCost+=M;66. coutminCostendl;67. return0;68. 算法思路：将每个有货物的隔间作为图中的一个点；应用克鲁斯卡尔最小生成树算法，循环执行C-M次，则最后的连通分量个数为M；需要用到并查集算法。当C-M=0时，需要采购塑钢板的最小长度=C，因为每个有货物的隔间都可以安排一块钢板，至于最少需要多少块塑钢板与有货物的隔间分布有关系。运行截图：测试用例1测试用例2测试用例3（最少3块塑钢板）测试用例4（最少1块塑钢板）4.小花和小草正在沙滩上玩挖沙洞的游戏。他们划了一条长度为n米的线作为挖沙洞的参考线路，小花和小草分别从两头开始沿着划好的线开始挖洞，小花每隔a米挖一个洞，小草每隔b米挖一个洞，碰到已经挖过洞的就不需要再挖了。那么，你能帮小花和小草算算，他们全部挖到头之后，一共挖了多少个洞吗？（两头端点位置都要挖洞）输入格式：第1行：一个正整数n，代表线路的长度。（3=n=10000）第2行：用空格分隔的两个正整数，代表a和b的值。（1=a,b=50)输出格式：
收藏
编号：347369894
类型：共享资源
大小：198.25KB
格式：DOCX
上传时间：2023-03-14
10
金贝
- 关 键 词：
-
2022年
第四届
全国高校计算机能力挑战赛
决赛
C++
- 资源描述：
-
2022年第四届全国高校计算机能力挑战赛决赛
第一套试卷
个人解答源码及思路，非评分标准答案。（程序设计赛 C++）
1.小明有个嗜好，他特别喜欢“完全立方数”，比如2197=13*13*13,9261=21*21*21，那么2197和9261就是完全立方数。有时候小明会给自己选定某个幸运数字代表自己的气运，比如他某天选定了11作为自己的幸运数字，那么所有11的倍数也都是小明当天的幸运数。今天小明想把区间[a，b]之间的完全立方数找出来，同时把他今天的幸运立方数给找出来。小明今天选定的幸运数字是x，那么请你数一下区间[a，b]之间是完全立方数且包含x的倍数的数字有多少个？
输入格式：
输入一行，用空格隔开的三个整数a、b、x，其中1≤a<=b<=1018，1≤x≤109。
输出格式：
输出一行，一个整数，表示满足条件的数的个数输入。
输入样例1：
3 27 4
输出样例1：
1
参考源码：
1. #include
2. #include
3. using namespace std;
4. typedef long long int llInt;
5. int main() {
6. llInt l,r,x,counter=0;
7. cin>>l>>r>>x;
8. llInt fromData=pow(l,1.0/3);
9. llInt toData=pow(r,1.0/3);
10. for(int i=fromData;i<=toData;i++)
11. {
12. llInt tempData=i*i*i;
13. if (tempData % x==0){
14. counter++;
15. }
16. }
17. cout<
2. using namespace std;
3. const int maxNumber = 1e6 + 10;
4. const int MOD = 99999;
5. int visited[maxNumber];
6. int N;
7. int main() {
8. cin >> N;
9. int maxData = 0;
10. for (int i = 0; i < N; i--) {
11. int ai;
12. int counter = 0;
13. int sum = 0;
14. cin >> ai;
15. visited[ai]++;
16. int temp = ai * ai;
17. while (temp <= maxData) {
18. counter += visited[temp];
19. sum = (sum + temp * visited[temp]) % MOD;
20. temp *= ai;
21. }
22. cout << counter << " " << sum << endl;
23. maxData = max(maxData, ai);
24. }
25. return 0;
26. }
算法思路：
全局数组的最大值为2G，满足本题的要求106（按照int长度为4进行计算）；当读入一个ai时，把ai在maxData范围内的全部幂运数进行统计和累加。visited用幂运数作为下标，出现次数作为值（没有出现则值为0，这样在上面进行统计和累加的时候不影响，不需要单独处理，保持了代码的统一性）。
运行截图：
测试用例1（题目输入样例1）
测试用例2
测试用例3
3.小张的工厂里的厂房受到台风的袭击，导致部分厂房的顶棚遭到了破坏，急需修理。厂房是由一间间的相同宽度的隔间组成，这些隔间都是连在一起的，连成了一条直线，隔间采用塑钢板作为顶棚，多个隔间可以共用一块长的塑钢板。这些隔间里有的有货物，有的没有货物，因为考虑到最近可能还会有台风，所以必须把有货物的隔间的顶棚修理好。目前塑钢板的供应商能提供的板材的数量有限制，但长度没有限制，所以小张只能尽量的减少板材的数量。请你帮助小张计算需要采购塑钢板的最小长度。
输入格式：
第1行：M，S和C（用空格分开)。M为能买到的板材的最大数目（1<=M<=50），S为厂房总的隔间的数量，1<=S<=200，C为有货物的隔间的数量。
第2到C+1行：每行包含一个整数，表示有货物的隔间的编号。编号从1开始，1<=C<=S。
输出格式：
输出一行，采购的塑钢板的总长度。
输入样例1：
1 10 4
2
5
7
8
输出样例1：
7
输入样例2：
3 30 7
3
13
15
17
20
24
29
输出样例2：
14
参考源码：
1. #include
2. #include
3. using namespace std;
4. #define MAX_VERTEX_NUM 200
5. struct edge{
6. int begin;
7. int end;
8. int weight;
9. }edges[MAX_VERTEX_NUM*(MAX_VERTEX_NUM-1)/2+1];
10. int vertex[MAX_VERTEX_NUM+1];
11. int pre[MAX_VERTEX_NUM+1];
12. int edgeNum;
13. int M,S,C;
14. bool cmp(struct edge a,struct edge b)
15. {
16. return a.weight>M>>S>>C;
36. for(int i=1;i<=C;++i)
37. {
38. cin>>vertex[i];
39. pre[vertex[i]]=vertex[i];
40. for(int j=1;j
展开阅读全文
金锄头文库所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
