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：
1
10 6 3 4 6
输出样例1：
4 2
输入样例2：
3
7 5 4 5 8
7 5 4 5 2
20 53 45 26 4
输出样例2：
2 6
-1
1 3
1. 参考源码：#include
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<
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
点击显示更多内容>>
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号