2022年第四届全国高校计算机能力挑战赛初赛编程题(C++)
-
资源ID:347369955
资源大小:165.28KB
全文页数:9页
- 资源格式: DOCX
下载积分:0金贝
快捷下载
账号登录下载
微信登录下载
微信扫一扫登录
1、金锄头文库是“C2C”交易模式,即卖家上传的文档直接由买家下载,本站只是中间服务平台,本站所有文档下载所得的收益全部归上传人(卖家)所有,作为网络服务商,若您的权利被侵害请及时联系右侧客服;
2、如你看到网页展示的文档有jinchutou.com水印,是因预览和防盗链等技术需要对部份页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有jinchutou.com水印标识,下载后原文更清晰;
3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;
4、文档大部份都是可以预览的,金锄头文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;
5、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;
6、如果您还有什么不清楚的或需要我们协助,可以点击右侧栏的客服。
|
下载须知 | 常见问题汇总
|
2022年第四届全国高校计算机能力挑战赛初赛编程题(C++)
2022年第四届全国高校计算机能力挑战赛初赛个人解答源码及思路,非评分标准答案。(程序设计赛 C+)1.给定一个字符串,输出所有长度至少为2的回文子串。回文子串即从左往右输出和从右往左输出结果是一样的字符串,比如: aa、aba、abba、cccdeedccc都是回文字符串。输入格式:一个字符串,由字母或数字组成。长度500以内。输出格式:输出所有的回文子串,每个子串一行子串长度小的优先输出,若长度相等,则按照其在输入字符串中的出现位置靠左的优先输出。输入样例1:123321125775165561输入样例2:abbacddc123a321输出样例1:331177552332211257756556123321165561输出样例2:bbdd3a3abbacddc23a32123a321参考源码:1. #include<iostream>2. #include <string>3. using namespace std;4. bool judge(string oneStr) 5. int length = oneStr.length();6. for (int i = 0; i < length/2; i+) 7. if (oneStri = oneStrlength - 1 - i) 8. continue;9. else 10. return false;11. 12. 13. return true;14. 15. int main() 16. string str;17. cin >> str;18. int length = str.length();19. for (int i = 2; i <= length; i+) 20. /回文长度为i21. for (int j = 0; j <=length-i; j+) 22. /取出该长度的一个子串23. string temp = str.substr(j, i);24. if (judge(temp) 25. cout << temp << endl;26. 27. 28. 29. return 0;30. 算法思路: 暴力算法,主要边界条件。取出字符串str的全部子串(长度为2,3str.length()),对每个子串进行回文的判断。运行截图:测试用例1(题目输入样例1)测试用例2(题目输入样例2)测试用例32. 编写程序,从键盘上输入两个正整数,较大的数为m和较小的数为n,根据以下公式求P的值,并输出。(m和n为大于0且小于等于30的整数)P =m!/(n! (m - n)!)输入样例1:12 8输入样例2:27 30输出样例1:495输出样例2:4060参考源码:1. #include<iostream>2. using namespace std;3. typedef unsigned long long int ull;4.5. ull cmn(int m,int n)6. 7. long long s = 1;8. int k = 1;9. if(n > m-n)10. n = m-n;11. for(int i=m-n+1;i<=m;i+)12. 13. s *= i;14. while(k<=n && s%k = 0)15. 16. s /= k;17. k+;18. 19. 20. return s;21. 22.23. int main() 24. int m, n;25. cin >> m >> n;26. if (m < n) 27. swap(m, n);28. 29. cout << cmn(m, n) << endl;30. return 0;31. 算法思路: 这道题从表面上看非常简单,可以定义一个阶乘函数就可完成,但是存在整数的溢出问题(采用unsigned long long也存在溢出)。Cmn=Cmm-n,当n > m-n,则n=m-n(使得n比较小,m-n比较大),用m!/(m-n)!把m!和(m-n)!中重叠部分消去,同时每步计算1,2,3n中能除的数。运行截图:测试用例1(题目输入样例1)测试用例2(题目输入样例2)测试用例3这个测试用例如果没有溢出,那么题目参数范围(m和n为大于0且小于等于30的整数)内的所有参数都不会溢出。3.小明玩网络游戏,现在总共有n个天赋点,需要分配给m项技能(0.i.m),其中第i项技能所需的天赋点为ai,能够增加ei的战斗力。若是每项技能仅允许被加点一次,请问小明使用这n个天赋点,能够增加的最多的战斗力是?输入格式:第一行输入两个数字n和m,以空格间隔 (1<=n,m<=1000)之后m行依次输出第i项技能所需要的天赋点数和能够增加的战斗力,以空格间隔。输出格式:输出小明增加的最多的战斗力(1<=ai,ei<=1000)输入样例1:8 312 611 86 8输入样例2:6 32 104 51 4输出样例1:8输出样例2:15参考源码:1. #include <iostream>2. using namespace std;3. const int N = 1001;4. int n, m;5. int fNN;6. /背包体积;背包价值7. int vN, wN;8. int main() 9. cin >> m >> n;10. for (int i = 1; i <= n; i+)11. cin >> vi >> wi;12. for (int i = 1; i <= n; i+)13. for (int j = 0; j <= m; j+) 14. fij = fi - 1j;15. if (j >= vi)16. fij = max(fij, fi - 1j - vi + wi);17. 18. cout << fnm << endl;19. return 0;20. 算法思路: 01背包问题。ai是背包的体积,ei是背包的权重(价值,重量)。运行截图:测试用例1(题目输入样例1)测试用例1(题目输入样例2)4. 某个交通网络为无向图,共有n个节点,m条边,节点编号从1开始。小明初始时在1号节点,他需要将物资一次性运送到n号节点。无向图的每条边有两个权值w和v,分别表示该边最多能通过的物资的重量和通过该边需要上缴的过路费。一旦小明运送的物资重量超过w或者小明剩余的资金不足v,都不能通过该边。现在小明的总预算为c,请问他最多能一次性运送多少物资从1号点到n号点? (不必考虑自环与重边)输入格式:第一行依次输入三个数字n,m,c分别表示点数、边数和小明的总预算 (1<=n<=100,1<=m<=500,1<=c<=100),接下来m行每行输入4个正整数:x、y、w、v,以空格间隔,分别表示节点x到y有一条重量为w过路费为v的边。 (1<=w,v<=100)输出格式:小明一次性最多能运送的物资重量输入样例1:5 6 51 2 3 61 5 2 11 3 2 42 4 5 53 5 8 34 5 6 1输入样例2:6 7 401 2 30 71 3 50 402 3 25 63 4 32 123 5 40 154 5 60 185 6 35 12输出样例1:2输出样例2:255 1 51 2 3 6参考源码:1. #include <iostream>2. #include <algorithm>3. #include <stack>4. using namespace std;5. int nodes;6. stack<int> singleRoad;7. int matrix100100;8. int costs100100;9. int visited100;10. int maxWeight = 0;11. void createGraph(int m) 12. int xNodeIndex, yNodeIndex, weight, cost;13. for (int i = 0; i < m; i+) 14. cin >> xNodeIndex >> yNodeIndex >> weight >> cost;15. xNodeIndex = xNodeIndex - 1;16. yNodeIndex = yNodeIndex - 1;17. matrixxNodeIndexyNodeIndex = weight;18. matrixyNodeIndexxNodeIndex = weight;19. costsxNodeIndexyNodeIndex = cost;20. costsyNodeIndexxNodeIndex = cost;21. 22. 23. void output(int c) 24. int tempsingleRoad.size();25. int minWeight = 101;26. int sum = 0;27. int first, second;28. int size = singleRoad.size();29. for (int i = 0; i < size - 1; i+) 30. first = singleRoad.top();31. singleRoad.pop();32. second = singleRoad.top()