2014年西电算法题

时间：2025年3月6日21:06:42 start-> 2025年3月6日22:31:17 -》2025年3月7日11:08:45 continue->

Problem 1

题目描述：编写一个程序，读入一组整数，它们的个数N也是由用户输入的，最多不会超过20。然后程序将对这个数组进行统计，把出现次数最多的那个数组元素值打印出来。如果有两个元素值出现的次数相同，即并列第一，那么只打印比较小的那个值。

输入说明：第一行是一个整数N，N<=20；接下来有N行，每一行表示一个整数。

输出说明：输出只有一行，即出现次数最多的那个元素值。

输入样本：

6
10 12 13 2 12 10

输出样本：

10

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
#include <unordered_map>
using namespace std;

int main() {
    int n, num;
    unordered_map<int, int> cnt;
    scanf("%d", &n);

    for (int i = 0; i < n; ++i) {
        scanf("%d", &num);
        ++cnt[num];
    }

    int max = -1, maxNum = 0;
    for (const auto& pair : cnt) {
        if (pair.second > max) {
            max = pair.second;
            maxNum = pair.first;
        } else if (pair.second == max && pair.first < maxNum) { // 如果用map就不用比了，找到返回就行了
            maxNum = pair.first;
        }
    }
    printf("%d\n", maxNum);
    return 0;
}

Problem 2

题目描述：世界杯小组赛（胜得3分，平得1分，负不得分），计算每个队的积分并按排名先后输出，若积分相同，则按净球数排序（保证积分相等时输入的净球数不相等）。输入M个队，出现队N个，输出出线的队伍的排名、名称、积分、净球数。

输入说明：

​ 名称 胜 平 负 进球数 负球数

输入样本：

4 2

德国 1 1 0 9 3

俄罗斯 1 0 0 2 1

威尔士 1 1 1 10 2

芬兰 0 1 0 3 3

输出样本：

1 威尔士 4 8

2 德国 4 6

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

struct Team {
    string name;
    int ranks;     // 积分
    int goal_diff; // 净球数
};

bool cmp(const Team& a, const Team& b) {
    if (a.ranks != b.ranks) {
        return a.ranks > b.ranks;
    } else {
        return a.goal_diff > b.goal_diff;
    }
}
int main() {
    int M, N;
    vector<Team> teams;
    scanf("%d%d", &M, &N);
    // 此题属于排序题目，排序指标：积分、净球数
    for (int i = 0; i < M; ++i) {
        char nameStr[20];
        int wins, draws, loses, goals_for, goals_against;
        scanf("%s%d%d%d%d%d", nameStr, &wins, &draws, &loses, &goals_for,
              &goals_against);
        string name = nameStr;
        teams.push_back({name, wins * 3 + draws, goals_for - goals_against});
    }
    sort(teams.begin(), teams.end(), cmp);
    for (int i = 0; i < N; ++i) {
        printf("%d %s %d %d\n", i + 1, teams[i].name.c_str(), teams[i].ranks,
               teams[i].goal_diff);
    }

    return 0;
}

直接开数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

struct Team {
    char name[20];
    int ranks;     // 积分
    int goal_diff; // 净球数
};

bool cmp(const Team& a, const Team& b) {
    if (a.ranks != b.ranks) {
        return a.ranks > b.ranks;
    } else {
        return a.goal_diff > b.goal_diff;
    }
}
int main() {
    int M, N;
    scanf("%d%d", &M, &N);
    vector<Team> teams;

    teams.resize(M);
    // 此题属于排序题目，排序指标：积分、净球数
    for (int i = 0; i < M; ++i) {

        int wins, draws, loses, goals_for, goals_against;
        scanf("%s%d%d%d%d%d", teams[i].name, &wins, &draws, &loses, &goals_for,
              &goals_against);
        teams[i].ranks = wins * 3 + draws;
        teams[i].goal_diff = goals_for - goals_against;
    }
    sort(teams.begin(), teams.end(), cmp);
    for (int i = 0; i < N; ++i) {
        printf("%d %s %d %d\n", i + 1, teams[i].name, teams[i].ranks,
               teams[i].goal_diff);
    }

    return 0;
}

C++风格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

struct Team {
    string name;
    int ranks;     // 积分
    int goal_diff; // 净球数
};

bool cmp(const Team& a, const Team& b) {
    if (a.ranks != b.ranks) {
        return a.ranks > b.ranks;
    } else {
        return a.goal_diff > b.goal_diff;
    }
}
int main() {
    int M, N;
    vector<Team> teams;
    cin >> M >> N;
    // 此题属于排序题目，排序指标：积分、净球数
    for (int i = 0; i < M; ++i) {
        int wins, draws, loses, goals_for, goals_against;
        string name;
        cin >> name >> wins >> draws >> loses >> goals_for >> goals_against;
        teams.push_back({name, wins * 3 + draws, goals_for - goals_against});
    }
    // sort(teams.begin(), teams.end(), cmp);

    // 也可以选择自己排序，选择排序
    for (int i = 0; i < M - 1; ++i) {
        int k = i;
        for (int j = i + 1; j < M; ++j) {
            if (teams[j].ranks > teams[k].ranks) {
                k = j;
            } else if (teams[j].ranks == teams[k].ranks &&
                       teams[j].goal_diff > teams[k].goal_diff) {
                k = j;
            }
        }
        if (k != i) {
            swap(teams[i], teams[k]);
            /*Team tmp=teams[i];
            teams[i]=teams[k];
            teams[k]=tmp;*/
        }
    }

    for (int i = 0; i < N; ++i) {
        cout << i + 1 << " " << teams[i].name << " " << teams[i].ranks << " "
             << teams[i].goal_diff << endl;
    }

    return 0;
}

Problem 3

题目描述：对于给定的字符序列，从左到右将所有数字字符取出拼接成一个无符号整数（字符序列长度小于100，拼接出的整数小于2^31^），计算并输出该整数的最大因子。

输入说明：有多组数据；每组数据为一行字符序列，当输入一个空行时表示输入结束。

输出说明：对每个字符序列，求出所得整数的最大因子；若字符序列没有数字或找出的整数为0，则输出0。每个整数占一行输出。

输入样本：

3

sdf0ejg3.f?9f

?4afd0s&2d79*(g

abcde

输出样本：

13

857

0

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#include<string>
#include<cctype>

using namespace std;
int main(){
	char strArr[100]={0};
   //  memset(str,0,100);
	string str;
	int num=0;
	while(fgets(strArr,sizeof(strArr),stdin)!=NULL){ // scanf("%s",strArr)!=EOF
		str=strArr; // 赋值
		num=0;
        
        // 检查是否为空行
        int is_empty = 1;
        for (int i = 0; line[i] != '\0' && line[i] != '\n'; ++i) {
            if (!isspace(line[i])) {
                is_empty = 0;
                break;
            }
        }
        if (is_empty) {
            break;
        }
        
		for(int i=0;i<str.size();++i){
			if(isdigit(str[i])){
				num=num*10+str[i]-'0';
			}
		}
		// 取得数字后 找最大公因子
		if(num<=1){
			printf("%d\n",0); // 1也没有最大质因数
			continue;
		}
		// 找出的整数>0 则肯定至少是2。
		for(int i=sqrt(num);i>=2;--i){
			if(num%i==0){
				printf("%d\n",0);
				break;
			}
		}
	}
	return 0;
}

Problem 4

题目描述：请写一个程序，对于一个m行m列的（1<m<10）的方阵，求其每一行，每一列及主对角线元素之和，最后按照从大到小的顺序依次输出。

输入说明：共一组数据，输入的第一行为一个正整数，表示m，接下来的m行，每行m个整数表示方阵元素。

输出说明：从大到小排列的一行整数，每个整数后跟一个空格，最后换行。

输入样本：

4

15 8 -2 6

31 24 18 71

-3 -9 27 13

17 21 38 69

输出样本：

159 145 144 135 81 60 44 28 27

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <algorithm>
#include <cstdio>
#include <functional>
#include <vector>

using namespace std;

bool cmp(int a, int b) { return a > b; }
int main() {
    int m;
    scanf("%d", &m);
    // vector<vector<int>> matrix(m, vector<int>(m)); // 初始化二维vector亦可
    vector<vector<int>> matrix;
    matrix.resize(m);
    for (int i = 0; i < m; ++i) {
        matrix[i].resize(m);
        for (int j = 0; j < m; ++j) {
            scanf("%d", &matrix[i][j]);
        }
    }
    // 处理
    vector<int> sumArr;
    for (int i = 0; i < m; ++i) {
        int curSum = 0;
        for (int j = 0; j < m; ++j) {
            curSum += matrix[i][j];
        }
        sumArr.push_back(curSum);
    }
    for (int j = 0; j < m; ++j) {
        int curSum = 0;
        for (int i = 0; i < m; ++i) {
            curSum += matrix[i][j];
        }
        sumArr.push_back(curSum);
    }
    int curSum = 0;
    for (int i = 0; i < m; ++i) {
        curSum += matrix[i][i];
    }
    sumArr.push_back(curSum);
    sort(sumArr.begin(), sumArr.end(), greater<int>()); // #include<functional>
    // sort(sumArr.begin(),sumArr.end(),cmp);
    for (int i = 0; i < sumArr.size(); ++i) {
        printf("%d ", sumArr[i]);
    }
    printf("\n");
    return 0;
}