写在最前面
侥幸在保研上机的时候拿到满分，在此记录下考试的题目以及一些体会。
因为考试试卷和答案代码均不能带出考场，以下内容皆为回忆版，附上我仓促写的答案代码，如有不妥还望指教。
0. 前言
机考成绩在保研中占比越来越重，在最后参加机考的人里，加权相差也不会太大，而机考可以轻轻松松拉开二三十分的差距，所以不夸张的说，上机考试一考定乾坤。
不过学院一直在淡化机考，突出CCF CSP考试的重要性，往后有可能只将CCF CSP作为上机唯一标准，所以希望学弟学妹尽早把CSP刷高。当然，CSP难度比机考大很多，但所谓 “取法乎上，仅得乎中”，如果仅仅准备学院机考，最后成绩可能也未必理想。
Leetcode以及牛客网上的题目比较偏重于完成某个小函数，可能与机考以及CSP套路不太相同，这里更推荐刘汝佳大佬的《算法竞赛入门经典》，完成了上面一定量的题目后，学院机考便不在话下。
1. 梅森素数 (40分)
我们将满足的素数称为梅森素数，其中
也需要为某一素数。比如
即满足这个条件，但是
就不是梅森素数。
给定一个数，顺序求出所有不大于
的梅森素数。
样例输入：
97
样例输出：
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分)
给定一个整数，之后有
个字符串。针对每个字符串，将数据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个数字分别操作结果即位最后的密码。
注意，每个字符串可能有任意长。
样例输入：
2
huazhongU
shangjiaoU
样例输出：
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。
输入多个，请计算恰好有
位的有趣的数的个数。你需要连续处理一系列的输入，当输入的
为0的时候，输入截止。由于答案可能非常大，只需要输出答案除以1000000007的余数。
样例输入：
4
6
0
样例输出：
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;
}
