2022年第四届全国高校计算机能力挑战赛初赛
个人解答源码及思路，非评分标准答案。（程序设计赛 C++）
1.给定一个字符串，输出所有长度至少为2的回文子串。回文子串即从左往右输出和从右往左输出结果是一样的字符串，比如: aa、aba、abba、cccdeedccc都是回文字符串。
输入格式：
一个字符串，由字母或数字组成。长度500以内。
输出格式：
输出所有的回文子串，每个子串一行
子串长度小的优先输出，若长度相等，则按照其在输入字符串中的出现位置靠左的优先输出。
输入样例1：
123321125775165561
输入样例2：
abbacddc123a321
输出样例1：
33
11
77
55
2332
2112
5775
6556
123321
165561
输出样例2:
bb
dd
3a3
abba
cddc
23a32
123a321
参考源码：
1. #include
2. #include
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 (oneStr[i] == oneStr[length - 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. //回文长度为i
21. 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，3……str.length()），对每个子串进行回文的判断。
运行截图：
测试用例1（题目输入样例1）
测试用例2（题目输入样例2）
测试用例3
2. 编写程序，从键盘上输入两个正整数，较大的数为m和较小的数为n,根据以下公式求P的值，并输出。(m和n为大于0且小于等于30的整数)
P =m!/（n! (m - n)!）
输入样例1：
12 8
输入样例2：
27 30
输出样例1：
495
输出样例2：
4060
参考源码：
1. #include
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,3⋯n中能除的数。
运行截图：
测试用例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 3
12 6
11 8
6 8
输入样例2：
6 3
2 10
4 5
1 4
输出样例1：
8
输出样例2：
15
参考源码：
1. #include
2. using namespace std;
3. const int N = 1001;
4. int n, m;
5. int f[N][N];
6. //背包体积；背包价值
7. int v[N], w[N];
8. int main() {
9. cin >> m >> n;
10. for (int i = 1; i <= n; i++)
11. cin >> v[i] >> w[i];
12. for (int i = 1; i <= n; i++)
13. for (int j = 0; j <= m; j++) {
14. f[i][j] = f[i - 1][j];
15. if (j >= v[i])
16. f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
17. }
18. cout << f[n][m] << 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 5
1 2 3 6
1 5 2 1
1 3 2 4
2 4 5 5
3 5 8 3
4 5 6 1
输入样例2：
6 7 40
1 2 30 7
1 3 50 40
2 3 25 6
3 4 32 12
3 5 40 15
4 5 60 18
5 6 35 12
输出样例1：
2
输出样例2：
25
5 1 5
1 2 3 6
参考源码：
1. #include
2. #include
3. #include
4. using namespace std;
5. int nodes;
6. stack singleRoad;
7. int matrix[100][100];
8. int costs[100][100];
9. int visited[100];
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. matrix[xNodeIndex][yNodeIndex] = weight;
18. matrix[yNodeIndex][xNodeIndex] = weight;
19. costs[xNodeIndex][yNodeIndex] = cost;
20. costs[yNodeIndex][xNodeIndex] = cost;
21. }
22. }
23. void output(int c) {
24. int temp[singleRoad.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()