2022年第四届全国高校计算机能力挑战赛决赛编程题(C++)第二套试卷

2022年第四届全国高校计算机能力挑战赛决赛第二套试卷个人解答源码及思路，非评分标准答案。（程序设计赛 C+）1. 小丽好朋友的生日快到了，她打算做一些折纸放在幸运罐中作为生日礼物。小丽计划总共 需要a颗星星以及b只纸鹤。现在市场上卖的到的星星纸(折小星星的专用纸)一张可以折c颗小星星，一张纸鹤纸(折纸鹤的专用纸)可以折d只小纸鹤。她准备一共买k张折纸，要优先满足星星纸的需求，剩余的再去买纸鹤纸，请你帮忙计算一下，买来的k张折纸能否满足小丽的折纸需求，能满足的话分别给出需要购买的星星纸和纸鹤纸的数量，不能的话则输出-1。若有满足条件的折纸方案，星星优先折叠，剩下的折纸都属于纸鹤。输入格式：第一行输入一个整数T，表示共有T组情况需要判断。接下来T行，每行包含5个整数a，b，c，d，k。其中1<=T,a,b,c,d,k<=100输出格式：输出T行，如果可以满足要求，输出两个整数x，y以空格分隔，分别表示需要采购的星星纸数量和纸鹤纸数量。如果不存在合理方案，输出-1。输入样例1：110 6 3 4 6输出样例1：4 2输入样例2：37 5 4 5 87 5 4 5 220 53 45 26 4输出样例2：2 6-11 31. 参考源码：#include <iostream>2. using namespace std;3. int main() 4.     int n, a, b, c, d, k;5.     cin >> n;6.     for (int i = 0; i < n; i+) 7.         cin >> a >> b >> c >> d >> k;8.         int number1, number2;9.         number1 = (a % c = 0 ? a / c : a / c + 1);10.         number2 = (b % d = 0 ? b / d : b / d + 1);11.         if (number1+number2>k)12.             cout<<-1<<endl;13.          else14.             cout<<number1<<" "<<k-number1<<endl;15.         16.     17.     return 0;18. 算法思路： 模拟算法。纸的总数（number1最少的星星纸数量，number2最少的纸鹤纸数量）是否满足需要（number1+ number2<=k），然不满足输出-1，满足则输出number1和k- number1。从逻辑上分析，星星优先折叠属于“伪优先”，因为当满足条件时，星星和纸鹤都能获得必须的数量，且纸鹤有可能获得超过的数量。运行截图：测试用例1（题目输入样例1）测试用例2（题目输入样例2）2.小李计划编写一个关于幂运数的自动答题机器人程序。机器人运行的规则是这样的：每当用户输入一个数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. #include<iostream>2. using namespace std;3. const int maxNumber = 1e6 + 10;4. const int MOD = 99999;5. int visitedmaxNumber;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.         visitedai+;16.         int temp = ai * ai;17.         while (temp <= maxData) 18.             counter += visitedtemp;19.             sum = (sum + temp * visitedtemp) % 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测试用例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. #include<iostream>2. #include<algorithm>3. using namespace std;4. #define MAX_VERTEX_NUM 2005. struct edge6.     int begin;7.     int end;8.     int weight;9. edgesMAX_VERTEX_NUM*(MAX_VERTEX_NUM-1)/2+1;10. int vertexMAX_VERTEX_NUM+1;11. int preMAX_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<b.weight;17. 18.19. int find(int x)20. 21.     if (prex = x)22.         return x;23.     return find(prex);24.25. 26.27. void Merge(int x,int y)28. 29.     int fx = find(x), fy = find(y);30.     if (fx != fy)31.         prefx = fy;32. 33.34. int main()35.     cin>>M>>S>>C;36.     for(int i=1;i<=C;+i)37.     38.         cin>>vertexi;39.         prevertexi=vertexi;40.         for(int j=1;j<i;+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.     int minCost=0;49.     int count=0;50.     for (int i=1; i<=edgeNum; i+) 51.         int beginNode=edgesi.begin;52.         int endNode=edgesi.end;53.         int weight=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.     cout<<minCost<<endl;67.     return 0;68. 算法思路：将每个有货物的隔间作为图中的一个点；应用克鲁斯卡尔最小生成树算法，循环执行C-M次，则最后的连通分量个数为M；需要用到并查集算法。当C-M<=0时，需要采购塑钢板的最小长度=C，因为每个有货物的隔间都可以安排一块钢板，至于最少需要多少块塑钢板与