杭电 2016 年计算机复试真题

写在前面

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

第一题

Problem Description

判断一个数 N 是否是素数，是的话输出 “YES”，否则输出 “NO”

Input

输入包含多个测试实例，每行包含一个正整数

Output

若是的素数输出 “YES”，否则输出 “NO”

Sample Input

1000000007
100

Sample Output

YES
NO

解题思路

整除或者打表

参考源码

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 <cmath>
#include <iostream>
using namespace std;
bool isprime(long long a) {
    if (a <= 1) return false;
    for (long long i = 2; i <= sqrt(a); i++) {
        if (a % i == 0) return false;
    }
    return true;
}
int main() {
    long long n;
    while (cin >> n) {
        if (isprime(n))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

//方法二：打表
#include <cstring>
#include <iostream>
using namespace std;
#define MAX 1000000
bool prime[MAX];
void findprime() {
    prime[0] = false;
    prime[1] = false;
    memset(prime, true, sizeof(prime));
    for (int i = 2; i < MAX; i++)
        if (prime[i])  //如果是素数
            for (int j = 2 * i; j < MAX; j += i) {
                prime[j] = false;  //筛去所有i的倍数
            }
}
int main() {
    int n;
    findprime();
    while (cin >> n) {
        if (prime[n])
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

第二题

Problem Description

在一个二维平面内有 n 个点，每个点坐标为（x，y），求最近的两点的距离

Input

输入首先是一个正整数，表示平面上点的个数，接下来是 n 行，分别是每个点的坐标（x，y）

Output

最近的两点的距离

Sample Input

5
1 2
100 200
1000 2000
1000 1
1 3

Sample Output

1

解题思路

暴力破解，计算每个点之间的距离

参考源码

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 <cmath>
#include <iostream>
#include <vector>
using namespace std;
struct node {
    int x, y;
} temp;
int main() {
    int n;
    double min = 0x3fffffff;
    vector<node> vt;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> temp.x >> temp.y;
            vt.push_back(temp);
        }
        for (int i = 0; i < n - 1; i++) {  //遍历每个点
            for (int j = i + 1; j < n; j++) {
                double dis = sqrt(pow((vt[i].x - vt[j].x), 2) + pow((vt[i].y - vt[j].y), 2));
                if (min > dis) min = dis;
            }
        }
        cout << min << endl;
    }
    return 0;
}

第三题

Problem Description

有一个文件记录了学生期末考试的几门成绩和学号，求出这几门课程的平均分和总分，并按照总分排序，从高到底，如果成绩相同，按照学号从小到大的顺序。

Input

数据从文件读入。第一行是表头，接下来数行每一行表示一个学生的数据

Output

按照总分排序，从高到底，如果成绩相同，按照学号从小到大的顺序输出

Sample Input

姓名 学号 语文 数学 英语
A 1 20 40 40
B 2 30 39 31
C 3 99 5 5

Sample Output

B C A

解题思路

文件处理题，需要使用 fstream，另外注意表头的处理

参考源码

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
#include <algorithm>
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;
struct student {
    char name[20], id[20];
    int a, b, c, d;
} stu[1000];
bool cmp(student m, student n) {
    if (m.a + m.b + m.c + m.d != n.a + n.b + n.c + n.d)
        return m.a + m.b + m.c + m.d > n.a + n.b + n.c + n.d;
    else
        return m.id < n.id;
}
int main() {
    int n = 0;
    fstream in;
    in.open("..\\HDU2016test\\student.txt", ios::in);
    if (!in) cout << "error" << endl;
    string s;
    getline(in, s);  //处理第一行
    while (!in.eof()) {
        in >> stu[n].name >> stu[n].id;
        in >> stu[n].a >> stu[n].b >> stu[n].c >> stu[n].d;
        n++;
    }
    in.close();  //文件关闭
    sort(stu, stu + n, cmp);
    for (int i = 0; i < n; i++) {
        if (i == 0)
            cout << stu[i].name;
        else
            cout << " " << stu[i].name;
    }
    cout << endl;
    return 0;
}

第四题

Problem Description

有一个由数字组成的二维矩阵，大小为 N*M；还有一个大小为 n*m 小二维矩阵，想象将小二维矩阵上面（小矩阵左上角位置和大矩阵某个位置对应放置），在不同的位置，这两个二维矩阵对应位置的数字绝对值之差的和一般是不同的，求这个绝对值之差的和的最小值，并求出对应的大矩阵位置

Input

输入首先是 N 与 M，接着是N*M的矩阵，之后是 n 与 m，接着n*m的小二维矩阵

Output

输出大矩阵与小矩阵对应元素绝对值差的和 s，并输出起始坐标

Sample Input

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

Sample Output

1 (1,1)

解题思路

把小矩阵放到大矩阵上一一计算，找到绝对值之差的和的最小值

参考源码

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
#include <cmath>
#include <iostream>
using namespace std;
int map1[1000][1000];
int map2[1000][1000];
int main() {
    int N, M, n, m;
    int posi, posj, min;
    while (cin >> N >> M) {
        posi = posj = 0;
        min = 0x3fffffff;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) cin >> map1[i][j];
        cin >> n >> m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) cin >> map2[i][j];
        for (int i = 0; i <= N - n; i++) {  // i,j为小矩阵起始位置
            for (int j = 0; j <= M - m; j++) {
                int temp = 0;
                for (int p = 0; p < n; p++) {
                    for (int q = 0; q < m; q++) {
                        temp += fabs(map1[i + p][j + q] - map2[p][q]);
                    }
                }
                if (min > temp) {
                    posi = i;
                    posj = j;
                    min = temp;
                }
            }
        }
        cout << min << " (" << posi + 1 << "," << posj + 1 << ")" << endl;
    }
    return 0;
}

相关内容