杭电 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 是待截取部分的宽和高
解题思路
参考源码
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
19
解题思路
构图时，可以多加一个隐藏的点，这个点与打井的点相连，可以抽象为地下泉，打井时，实际上是在往地下连边，之后就是最小生成树问题，可以使用 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;
}相关内容
- 杭电 2014 年计算机复试真题
- 杭电 2015 年计算机复试真题
- 杭电 2016 年计算机复试真题
- 杭电 2017 年计算机复试真题
- 杭电 2019 年计算机复试真题
