杭电2019年计算机复试真题

本文最后更新于:7 个月前

杭电 2019 年计算机复试真题

写在前面

此题目是根据 CSDN 博客粥粥同学发布的内容进行收集整理,记录了本人的解题过程和一些想法。仅供大家参考,如有错误,欢迎大家指出!


第一题

Problem Description

大家去电影院看电影,总共有 n 人来看电影,其中年龄不低于 18 岁的成年人的座位号为奇数,不满 18 岁的未成年人的座位号为偶数。现在请统计成年人与未成年的数目,以及他们在总人数里的比例。n<=1000


Input

第一行输入 n ,表示有 n 个人去看电影 (1<=n<1000),接下来是 n 个座位号


Output

依次输出此次看电影成人的人数以及成人在所有人中所占的比例、未成年人的人数以及未成年人在所有人中所占的比例,计算出的比例保留两位小数,每个输出用空格隔开


Sample Input

5
2 3 6 7 11


Sample Output

3 0.60 2 0.40

解题思路

奇偶数判断

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int main() {
int n, num, a = 0, b = 0;
cin >> n;
while (n--) {
cin >> num;
if (num % 2 != 0)
a++; //成年人
else
b++; //未成年人
}
printf("%d %.2f %d %.2f\n", a, 1.0 * a / (a + b), b, 1.0 * b / (a + b));
return 0;
}

第二题

Problem Description

有一个大容器,现在向其中加入若干铅锤的木板,每个木板的顶端坐标记为 (i,yi)


Input

第一行输入 n ,表示有 n 个木板 (1<=n<1000),接下来是 n 个木板高度


Output

输出该容器最大能装多少体积的水(容器不允许倾斜)


Sample Input

8
1 8 6 4 5 3 7 2


Sample Output

35

解题思路

直接暴力破解,找最大值

参考源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cmath>
#include <iostream>
using namespace std;
int main() {
int n, v = 0, num[1001], maxv = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> num[i];
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
v = min(num[i], num[j]) * (j - i); //最大体积
maxv = max(maxv, v);
}
}
cout << maxv << endl;
return 0;
}

第三题

解题思路

参考源码

1


第四题

Problem Description

有一群人,现在告诉你他们之间的朋友关系。若 A 与 B 是朋友,B 是 C 的朋友,则 A 与 C 也是朋友。朋友关系都是双向的,即 A 与 B 是朋友,B 与 A 也是朋友。那么 A、B、C 就在同一个 “朋友圈”


Input

首先输入 n,m 表示有 n 个人,m 对关系 (1<=n<2000),接下来有 m 行每一行表示一对关系


Output

输出在当前输入关系的情况下 “朋友圈” 的数量


Sample Input

8 7
1 2
2 4
4 1
5 7
4 3
6 2
7 8


Sample Output

2

解题思路

求连通分量的个数,使用并查集或者是DFS

参考源码

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
60
61
62
// 方法一:并查集
#include <iostream>
using namespace std;
int fa[2001];
int find(int x) {
if (x == fa[x])
return x;
else
return find(fa[x]);
}
int main() {
int n, m, a, b, ans = 0;
for (int i = 0; i < n; i++) fa[i] = i; //初始化
cin >> n >> m;
while (m--) {
cin >> a >> b;
int fa1 = find(a);
int fa2 = find(b);
if (fa1 != fa2) fa[fa1] = fa2; //合并
}
for (int i = 0; i < n; i++) {
if (i == fa[i]) ans++; //根节点
}
cout << ans << endl;
system("pause");
return 0;
}


// 方法二:DFS
#include <cstring>
#include <iostream>
using namespace std;
int map[2001][2001];
bool vis[2001];
void DFS(int u, int n) {
vis[u] = true; //标记为已访问
for (int i = 1; i <= n; i++) { //对每个顶点
if (!vis[i] && map[u][i]) {
vis[i] = true;
DFS(i, n);
}
}
}
int main() {
int n, m, a, b, count = 0;
memset(map, 0, sizeof(map));
memset(vis, false, sizeof(vis));
cin >> n >> m;
while (m--) {
cin >> a >> b;
map[a][b] = map[b][a] = 1;
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) { //若未访问
DFS(i, n);
count++; //联通分量个数
}
}
cout << count << endl;
return 0;
}

相关内容


本文作者: EmoryHuang
本文链接: https://emoryhuang.cn/blog/1416939000.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明来自EmoryHuang