寫在最前面
僥幸在保研上機(jī)的時(shí)候拿到滿分，在此記錄下考試的題目以及一些體會(huì)。
因?yàn)榭荚囋嚲砗痛鸢复a均不能帶出考場掩浙，以下內(nèi)容皆為回憶版，附上我倉促寫的答案代碼秸歧，如有不妥還望指教厨姚。
0. 前言
機(jī)考成績在保研中占比越來越重，在最后參加機(jī)考的人里键菱，加權(quán)相差也不會(huì)太大谬墙，而機(jī)考可以輕輕松松拉開二三十分的差距，所以不夸張的說经备，上機(jī)考試一考定乾坤拭抬。
不過學(xué)院一直在淡化機(jī)考，突出CCF CSP考試的重要性弄喘，往后有可能只將CCF CSP作為上機(jī)唯一標(biāo)準(zhǔn)玖喘，所以希望學(xué)弟學(xué)妹盡早把CSP刷高。當(dāng)然蘑志，CSP難度比機(jī)考大很多累奈，但所謂 “取法乎上，僅得乎中”急但，如果僅僅準(zhǔn)備學(xué)院機(jī)考澎媒，最后成績可能也未必理想。
Leetcode以及挪ㄗ客網(wǎng)上的題目比較偏重于完成某個(gè)小函數(shù)戒努，可能與機(jī)考以及CSP套路不太相同，這里更推薦劉汝佳大佬的《算法競賽入門經(jīng)典》镐躲，完成了上面一定量的題目后储玫，學(xué)院機(jī)考便不在話下。
1. 梅森素?cái)?shù) (40分)
我們將滿足的素?cái)?shù)稱為梅森素?cái)?shù)萤皂，其中
也需要為某一素?cái)?shù)撒穷。比如
即滿足這個(gè)條件，但是
就不是梅森素?cái)?shù)裆熙。
給定一個(gè)數(shù)端礼，順序求出所有不大于
的梅森素?cái)?shù)禽笑。
樣例輸入：
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分)
給定一個(gè)整數(shù)，之后有
個(gè)字符串蛤奥。針對(duì)每個(gè)字符串佳镜，將數(shù)據(jù)6個(gè)為一組分組，最后一組可能不滿6個(gè)凡桥。比如"huazhongU"蟀伸，將其分為"huazho" "ngU"，求出6個(gè)數(shù)字唬血，每個(gè)數(shù)字分別為對(duì)應(yīng)位置上的字母ASCII碼的和望蜡。比如'h' + 'n' = 214，'u' + 'g' = 220拷恨，得到如下6個(gè)數(shù)字：214, 220, 182, 122, 104, 111。
之后谢肾，針對(duì)每個(gè)數(shù)字腕侄，按照數(shù)位求和，如果求和結(jié)果超過一位芦疏，重復(fù)執(zhí)行這個(gè)過程直到結(jié)果僅為1位冕杠。如 'a' + 'U' = 182 => 1 + 8 + 2 = 11 => 1 + 1 = 2。對(duì)6個(gè)數(shù)字分別操作結(jié)果即位最后的密碼酸茴。
注意分预，每個(gè)字符串可能有任意長。
樣例輸入：
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個(gè)數(shù)字薪捍，分別填入到下面公式的括號(hào)中笼痹，滿足數(shù)字不能重復(fù)，分母不能為1酪穿，并且要求分子分母沒有除了1以外的公因數(shù)凳干。
題解
#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. 有趣的數(shù) (10分)
"有趣的數(shù)"這道題，正是CCF CSP 2013年12月的一道原題被济，所以這里強(qiáng)烈建議把CSP歷年考試的 1 - 4 題刷一遍救赐，還是收益良多的。(我目前CSP為380分只磷，雖不是太高经磅，但是學(xué)校保研中已經(jīng)足夠用了)
我們把一個(gè)數(shù)稱為有趣的，當(dāng)且僅當(dāng)：
- 它的數(shù)字只包含0, 1, 2, 3钮追，且這四個(gè)數(shù)字都出現(xiàn)過至少一次预厌。
- 所有的0都出現(xiàn)在所有的1之前，而所有的2都出現(xiàn)在所有的3之前畏陕。
- 最高位數(shù)字不為0配乓。
因此，符合我們定義的最小的有趣的數(shù)是2013。除此以外犹芹，4位的有趣的數(shù)還有兩個(gè)：2031 和 2301崎页。
輸入多個(gè)，請(qǐng)計(jì)算恰好有
位的有趣的數(shù)的個(gè)數(shù)腰埂。你需要連續(xù)處理一系列的輸入飒焦，當(dāng)輸入的
為0的時(shí)候，輸入截止屿笼。由于答案可能非常大牺荠，只需要輸出答案除以1000000007的余數(shù)。
樣例輸入：
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;
}
