杭电 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

解题思路

奇偶数判断

参考源码

#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

解题思路

直接暴力破解，找最大值

参考源码

#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;
}

---

第三题

解题思路

参考源码

---

第四题

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

参考源码

// 方法一：并查集
#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;
}

---

相关内容

• 杭电 2014 年计算机复试真题
• 杭电 2015 年计算机复试真题
• 杭电 2016 年计算机复试真题
• 杭电 2017 年计算机复试真题
• 杭电 2018 年计算机复试真题