杭电 2018 年计算机复试真题

写在前面

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

第一题

Problem Description

杭电实验室定期会集体去电影院看电影，按照惯例，每个成员需要先抽个号码。给出 n 个人的名字，各抽取一个数字，自己用一种数据结构存取人的名字和抽取数字信息（票数），例如：Bob9 Alice12 Tom5 Listen7 Nick4
1.1 定义一种数叫丑数，其因子除 1 外只用 2,3,5 的倍数（例如 4,10 是丑数,11,13 不是），输出所有抽到丑数人的名字
1.2 根据个人所抽数字大小升序排序，输出排序后的所有名字。
1.3 现有一个新名字加入，将名字插入所以名字中间（n/2）处，并输出排序后所有人的名字。

1.1

1.1 定义一种数叫丑数，其因子除 1 外只用 2,3,5 的倍数（例如 4,10 是丑数,11,13 不是），输出所有抽到丑数人的名字

Input

输入包含多个测试实例，首先是正整数 n,接着是 n 行，每行包含姓名与抽取数字信息（票数）

Output

输出所有抽到丑数人的名字

Sample Input

5
Bob 9
Alice 12
Tom 5
Listen 7
Nick 4

Sample Output

Bob
Alice
Tom
Nick

解题思路

判断丑数，对 2，3，5 整除

参考源码

// 1.1
#include <algorithm>
#include <iostream>
using namespace std;
struct people {
    char name[20];
    int num;
} p[1000];
bool cmp(people a, people b) { return a.num < b.num; }  //升序
bool isugly(int a) {
    while (a % 2 == 0) a /= 2;
    while (a % 3 == 0) a /= 3;
    while (a % 5 == 0) a /= 5;
    if (a == 1) return true;
    return false;
}
int main() {
    int n;
    while (cin >> n) {
        getchar();
        for (int i = 0; i < n; i++) {
            cin >> p[i].name >> p[i].num;
        }
        sort(p, p + n, cmp);
        for (int i = 0; i < n; i++) {
            if (isugly(p[i].num)) cout << p[i].name << endl;
        }
    }
    return 0;
}

1.2

1.2 根据个人所抽数字大小升序排序，输出排序后的所有名字。

Input

输入包含多个测试实例，首先是正整数 n,接着是 n 行，每行包含姓名与抽取数字信息（票数）

Output

输出排序后的所有名字。

Sample Input

5
Bob 9
Alice 12
Tom 5
Listen 7
Nick 4

Sample Output

Nick
Tom
Listen
Bob
Alice

解题思路

sort()排序

参考源码

// 1.2
#include <algorithm>
#include <iostream>
using namespace std;
struct people {
    char name[20];
    int num;
} p[1000];
bool cmp(people a, people b) { return a.num < b.num; }  //升序
int main() {
    int n;
    while (cin >> n) {
        getchar();
        for (int i = 0; i < n; i++) {
            cin >> p[i].name >> p[i].num;
        }
        sort(p, p + n, cmp);
        for (int i = 0; i < n; i++) {
            cout << p[i].name << endl;
        }
    }
    return 0;
}

1.3

1.3 现有一个新名字加入，将名字插入所以名字中间（n/2）处，并输出排序后所有人的名字。

Input

输入包含多个测试实例，首先是正整数 n,接着是 n 行，每行包含姓名与抽取数字信息（票数），第 n+1 行是一个新名字加入，以及他的票数

Output

输出排序后的所有名字。

Sample Input

5
Bob 9
Alice 12
Tom 5
Listen 7
Nick 4
Emory 10

Sample Output

Bob
Alice
Emory
Tom
Listen
Nick

解题思路

数组插入

参考源码

// 1.3
#include <iostream>
using namespace std;
struct people {
    char name[20];
    int num;
} p[1000], newp;
int main() {
    int n;
    while (cin >> n) {
        getchar();
        for (int i = 0; i < n; i++) {
            cin >> p[i].name >> p[i].num;
        }
        cin >> newp.name >> newp.num;
        for (int i = n - 1; i >= n / 2; i--) {
            p[i + 1] = p[i];
        }
        p[n / 2] = newp;
        for (int i = 0; i < n + 1; i++) {
            cout << p[i].name << endl;
        }
    }
    return 0;
}

第二题

Problem Description

关于某同学没赶上拍毕业照，现用一个算法将他的头像从一张老照片 P 到毕业照某位置，输入源头像起始位置和头像宽，将数据拷贝到目的图片某起始位置某宽度
很长而且有图，没办法全部写出来，大意是给出两张 bmp 图像（可以理解为两个矩阵），将第一张图上的某个部分截取下来放入第二张的某个位置
（把图 1 中的人头像截下来贴到图 2 的人头上），然后给出了接函数的定义和参数的定义，readbmp 读取图像，copybmp 复制图像等。
2.1 一道程序填空题，根据题目函数的定义填岀整个拷贝图像的过程，比较长，但很简单，基本送分题。
2.2 写出 copybmp 的整个具体函数
void copybmp(unsigned char *pOldbuf,unsigned char *pNewbuf,int OldW,int NewW,int BlockW,int BlockH)
pOldbuf 和 pNewbuf 是两张图像首地址
OldW 和 NewW 是两图像宽度
BlockW 和 BlockH 是待截取部分的宽和高

解题思路

参考源码

1	void copybmp(unsigned char pOldbuf,unsigned char pNewbuf,int OldW,int NewW,int BlockW,int BlockH)

第三题

Problem Description

瓜农王大爷去年种西瓜赚了不少钱。看到收入不错，今年他又重新开辟了 n 个西瓜地。为了能给他的 n 个西瓜地顺利的浇上水，对于每个西瓜地他可以选择在本地打井，也可以修管道从另一个瓜地（这个瓜地可能打了井；也可能没打井，他的水也是从其他瓜地引来的）将水引过来。当然打井和修管道的费用有差别。已知在第 i 个西瓜地打井需要耗费 wi 元，在第 i、j 个西瓜地之间修管道需要耗费 pi,j 元。
现在的问题是：王大爷要想使所有瓜地都被浇上水，至少需要花费多少钱（打井与修管道的费用和）？由于瓜地较多，王大爷无法选择在哪些（个）瓜地打井，哪些西瓜地之间修管道。请你编程帮王大爷做出决策，求出最小费用。

Input

第一行为一个整数 n。接下来 n 行每行一个整数 wi,接下来 n 行，每行 n 个整数，第 i 行的第 j 个数，表示连接 i 号田和 j 号田需要的费用 P i,j
1<=N<=300;1<=wi<=100000;p(i,i)=0;1<=p(i,j)=p(j,i)<=100000

Output

输出最小开销

Sample Input

6
5
4
4
3
1
20
0 2 2 2 9 9
2 0 3 3 9 9
2 3 0 4 9 9
2 3 4 0 9 9
9 9 9 9 0 9
9 9 9 9 9 0

Sample Output

解题思路

构图时，可以多加一个隐藏的点，这个点与打井的点相连，可以抽象为地下泉，打井时，实际上是在往地下连边，之后就是最小生成树问题，可以使用 Kruskal 算法

参考源码

#include <algorithm>
#include <iostream>
using namespace std;
int t = 0, ans = 0;
int fa[302], w[302];
struct edge {
    int from, to, c;
} E[100000];
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}
bool cmp(edge a, edge b) { return a.c < b.c; }
int main() {
    int n, temp, num;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> temp;
            if (i != j) {
                E[++t].from = i;
                E[t].to = j;
                E[t].c = temp;
            } else {  //加入打井的原点
                E[++t].from = 0;
                E[t].to = j;
                E[t].c = w[i];
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        fa[i] = i;  //初始化并查集
    }
    sort(E + 1, E + t + 1, cmp);  //边权从小到大排序
    for (int i = 1; i <= t; i++) {
        int ff = find(E[i].from);  //寻找两个端点所在集合的根节点
        int ft = find(E[i].to);
        if (ff != ft) {     //若不在同一集合
            ans += E[i].c;  //累加
            fa[ff] = ft;    //加入集合
            num++;          //最小生成树边数+1
        }
        if (num == n) break;
    }
    cout << ans << endl;
    return 0;
}

杭电2018年计算机复试真题

杭电 2018 年计算机复试真题

写在前面

第一题

1.1

1.2

1.3

第二题

第三题

相关内容