2018华中科技大学计算机学院保研机试真题

2018-09-14

2018华中科技大学计算机学院保研机试真题

写在最前面

侥幸在保研上机的时候拿到满分，在此记录下考试的题目以及一些体会。

因为考试试卷和答案代码均不能带出考场，以下内容皆为回忆版，附上我仓促写的答案代码，如有不妥还望指教。

0. 前言

机考成绩在保研中占比越来越重，在最后参加机考的人里，加权相差也不会太大，而机考可以轻轻松松拉开二三十分的差距，所以不夸张的说，上机考试一考定乾坤。

不过学院一直在淡化机考，突出CCF CSP考试的重要性，往后有可能只将CCF CSP作为上机唯一标准，所以希望学弟学妹尽早把CSP刷高。当然，CSP难度比机考大很多，但所谓 “取法乎上，仅得乎中”，如果仅仅准备学院机考，最后成绩可能也未必理想。

Leetcode以及牛客网上的题目比较偏重于完成某个小函数，可能与机考以及CSP套路不太相同，这里更推荐刘汝佳大佬的《算法竞赛入门经典》，完成了上面一定量的题目后，学院机考便不在话下。

1. 梅森素数 (40分)

我们将满足 M = 2^k - 1 的素数称为梅森素数，其中 k 也需要为某一素数。比如 3 = 2^2 - 1 即满足这个条件，但是 2^11 - 1 = 2047 = 23 * 89 就不是梅森素数。

给定一个数M，顺序求出所有不大于M的梅森素数。

样例输入：

样例输出：

1
2
3

M(2) = 3
M(3) = 7
M(5) = 31

题解

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
typedef long long ll;
bool is_prime(ll m) {
    for (ll i = 2; i <= sqrt(m); ++i)
        if (!(m % i)) return false;
    return true;
}
int main (void) {
    ll m, k = 2;
    scanf("%lld", &m);
    while (true) {
        ll n = pow(2, k) - 1;
        if (n > m) break;
        if (is_prime(n)) printf("M(%lld) = %lld\n", k, n);
        while (!is_prime(++k));
    }
    return 0;
}

2. 加密 (30分)

给定一个整数n，之后有n个字符串。针对每个字符串，将数据6个为一组分组，最后一组可能不满6个。比如”huazhongU”，将其分为”huazho” “ngU”，求出6个数字，每个数字分别为对应位置上的字母ASCII码的和。比如’h’ + ‘n’ = 214，’u’ + ‘g’ = 220，得到如下6个数字：214, 220, 182, 122, 104, 111。

之后，针对每个数字，按照数位求和，如果求和结果超过一位，重复执行这个过程直到结果仅为1位。如 ‘a’ + ‘U’ = 182 => 1 + 8 + 2 = 11 => 1 + 1 = 2。对6个数字分别操作结果即位最后的密码。

注意，每个字符串可能有任意长。

样例输入：

1
2
3

2
huazhongU
shangjiaoU

样例输出：

1 2	742553 431647

题解

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int sum_num(int k) {
    int sum = 0;
    while (true) {
        while (k) {
            sum += k % 10;
            k /= 10;
        }
        if (sum < 10) break;
        k = sum;
        sum = 0;
    }
    return sum;
}
int main (void) {
    int n;
    int sum[6];
    scanf("%d", &n); getchar();
    while (n--) {
        char c;
        int cnt = 0;
        memset(sum, 0, sizeof(sum));
        while ((c = getchar()) != EOF && c != '\n')
            sum[cnt++ % 6] += c;
        for (int i = 0; i < 6; ++i)
            printf("%d", sum_num(sum[i]));
        printf("\n");
    }
    return 0;
}

3. 求分式 (20分)

将1-9这9个数字，分别填入到下面公式的括号中，满足数字不能重复，分母不能为1，并且要求分子分母没有除了1以外的公因数。
$$
[\ \ ][\ \ ]/[\ \ ] + [\ \ ][\ \ ]/[\ \ ] = [\ \ ][\ \ ]/[\ \ ]
$$

题解

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N 9
int num[N];
int vis[N];
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
void print_res(void) {
    for (int i = 0; i < N; ++i) {
        if (!((i + 1) % 3)) printf("/");
        if (i == 3) printf(" + ");
        if (i == 6) printf(" = ");
        printf("%d", num[i]);
    }
    printf("\n");
}
void generate(int k) {
    for (int i = 1; i <= (N - k) / 3; ++i) {
        if (num[i * 3 - 1] == 1) return;
        int m = num[i * 3 - 3] * 10 + num[i * 3 - 2];
        int n = num[i * 3 - 1];
        if (gcd(m, n) != 1) return;
    }
    if (!k) {
        int m = (num[0] * 10 + num[1]) * num[5] + (num[3] * 10 + num[4]) * num[2];
        int n = num[2] * num[5];
        int d = gcd(m, n);
        if (m / d > 100) return;
        if (m / d != num[6] * 10 + num[7] || n / d != num[8]) return;
        print_res();
        return;
    }
    for (int i = 0; i < N; ++i) {
        if (vis[i]) continue;
        vis[i] = 1;
        num[N - k] = i + 1;
        generate(k - 1);
        vis[i] = 0;
    }
    return;
}
int main (void) {
    generate(N);
    return 0;
}

4. 有趣的数 (10分)

“有趣的数”这道题，正是CCF CSP 2013年12月的一道原题，所以这里强烈建议把CSP历年考试的 1 - 4 题刷一遍，还是收益良多的。(我目前CSP为380分，虽不是太高，但是学校保研中已经足够用了)

我们把一个数称为有趣的，当且仅当：

它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
最高位数字不为0。

因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。

输入多个n，请计算恰好有n位的有趣的数的个数。你需要连续处理一系列的输入，当输入的n为0的时候，输入截止。由于答案可能非常大，只需要输出答案除以1000000007的余数。

样例输入：

1
2
3

4
6
0

样例输出：

1
2

3
85

题解

#include <stdio.h>
#define MAXN (1000 + 5)
#define MOD (1000000007)
int dp[MAXN][6];
// dp[k][0] only has 2
// dp[k][1] has 0 2
// dp[k][2] has 2 3
// dp[k][3] has 0 1 2
// dp[k][4] has 0 2 3
// dp[k][5] has 0 1 2 3
int main (void) {
    int n;
    for (int i = 1; i < MAXN; ++i) {
        dp[i][0] = 1;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 2 % MOD) % MOD;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
        dp[i][3] = (dp[i - 1][1] + dp[i - 1][3] * 2 % MOD) % MOD;
        dp[i][4] = (dp[i - 1][2] + (dp[i - 1][1] + dp[i - 1][4] * 2 % MOD) % MOD) % MOD;
        dp[i][5] = (dp[i - 1][3] + (dp[i - 1][4] + dp[i - 1][5] * 2 % MOD) % MOD) % MOD;
    }
    while (scanf("%d", &n) == 1 && n) {
        printf("%d\n", dp[n][5]);
    }
    return 0;
}