【考研】南郵歷年復試上機試題目與題解

個人題目難度評估

花了五個小時把題目整體做了一遍，現在平臺沒有判題機，不能測評，若有問題歡迎在評論區提出。題目整體難度不難，主要考察知識點：簡單模擬、結構體排序、簡單矩陣處理、字符串、STL應用、簡單數論（素數、公倍數等等）、進制轉換、日期問題、板子圖論(最短路、求連通塊)、裸背包問題、遞推。
復試上機平臺：南郵復試上機平臺

歷年上機題目

PROB1002 求最值問題

#include <iostream>using namespace std;int n, a, b, x;int main() {while (cin >> n) {int maxv = -1, minv = 101;for (int i = 1; i <= n; i++) {cin >> x;maxv = max(maxv, x); minv = min(minv, x);}cout << maxv << ' ' << minv << endl;}return 0;
}

PROB1003 新對稱素數問題

#include <iostream>
#include <algorithm>using namespace std;long long n, x;bool check(long long x) {if (x < 2 || x > 10000) return false;for (int i = 2; i <= x / i; i++) {if (x % i == 0)return false;}string str = to_string(x);string s = str;reverse(s.begin(), s.end());return s == str;
}int main() {cin >> n;while (n --) {cin >> x;cout << (check(x) ? "Yes\n" : "No\n");}return 0;
}

PROB1004 進制轉換

#include <bits/stdc++.h>
#include <cstdlib>using namespace std;int t, n, r;string work(int x, int r) {string res;bool flag = x < 0;x = abs(x);while (x) {int k = x % r;res += k <= 9 ? k + '0' : k - 10 + 'A';x /= r;}res += flag ? "-" : "";reverse(res.begin(), res.end());return res;
}int main() {cin >> t;while (t --) {cin >> n >> r;cout << work(n, r) << endl;}return 0;
}

PROB1005 涂色問題 (待補)

PROB1006 最大公約數和最小公倍數

#include <bits/stdc++.h>using namespace std;int main() {int a, b;cin >> a >> b;cout << __gcd(a, b) << " " << a * b / __gcd(a, b) << endl;return 0;
}

PROB1007 斐波那契數列

#include <bits/stdc++.h>using namespace std;const int N = 40;int n, f[N];int main() {cin >> n;f[0] = 0, f[1] = f[2] = 1;for (int i = 3; i <= n; i++) {f[i] = f[i - 1] + f[i - 2];}cout << f[n] << endl;return 0;
}

PROB1008 回文回文

#include <bits/stdc++.h>using namespace std;string str;int main() {cin >> str;for (auto &c : str)  c = tolower(c);string s = str;reverse(str.begin(), str.end());cout << (s == str ? "Yes\n" : "No\n");return 0;
}

PROB1009 單源最短路

#include <bits/stdc++.h>#define int long longusing namespace std;typedef pair<int, int> PII;
const int N = 3000, M = 6500 * 2, inf = 0x3f3f3f3f;int n, m, s, t, a, b, c;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool st[N];void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; 
}void dijkstra() { // 堆優化dijkstrapriority_queue<PII, vector<PII>, greater<PII>> heap;heap.emplace(0, s); // dist - snomemset(dist, 0x3f, sizeof dist);dist[s] = 0;while (!heap.empty()) {auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; ~i; i = ne[i]) {int j = e[i];if (dist[j] > distance + w[i]) {dist[j] = distance + w[i];heap.emplace(dist[j], j);}}}
}signed main() {cin >> n >> m >> s >> t;memset(h, -1, sizeof h);while (m -- ) {cin >> a >> b >> c;add(a, b, c), add(b, a, c);}dijkstra();cout << dist[t] << endl;return 0;
}

PROB1010 萌萌摘蘋果

#include <bits/stdc++.h>using namespace std;const int N = 25;int a[N], n, h, cnt;signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}cin >> h;for (int i = 1; i <= n; i++) {if (h + 30 >= a[i])cnt ++;}cout << cnt << endl;cout << (cnt == n ? "Yes\n" : "No\n");return 0;
}

PROB1011 忠誠的騎士

#include <bits/stdc++.h>using namespace std;int k;
vector<int> v;signed main() {v.push_back(0);for (int i = 1; i <= 200; i++) {for (int j = 1; j <= i; j++)v.push_back(i);}cin >> k;int res = 0;for (int i = 1; i <= k; i++) {res += v[i];}cout << res << endl;return 0;
}

PROB1012 最小質數合數之和問題

#include <bits/stdc++.h>using namespace std;bool isprime(int x) {if (x < 2) return false;for (int i = 2; i <= x / i; i++)if (x % i == 0)return false;return true;
}bool iscomprime(int x) {if (x < 2) return false;for (int i = 2; i <= x / i; i++)if (x % i == 0)return true;return false;
}signed main() {int n, ra, rb;cin >> n;while (1) {n ++;if (isprime(n) && !ra) ra = n;if (iscomprime(n) && !rb) rb = n;if (ra && rb) break;}//cout << ra << ' ' << rb << endl;cout << ra + rb << endl;return 0;
}

PROB1013 級數求和

#include <bits/stdc++.h>using namespace std;int k;
double s;signed main() {cin >> k;for (int i = 1; ; i++) {s += 1.0 * i / k;if (s > k) {cout << i;return 0;}}return 0;
}

PROB1014 小明與選擇題

#include <bits/stdc++.h>using namespace std;string s[5], mp[5];
bool same = true;
double avg;
int up, down, resa, resb;signed main() {for (int i = 1; i <= 4; i++) {cin >> s[i];mp[i] = 'A' + i - 1, avg += s[i].size();}avg /= 4.0;for (int i = 2; i <= 4; i++) {if (s[i].size() != s[i - 1].size())same = false;}string shor = "0000000000000", lon = "";for (int i = 1; i <= 4; i++) {if (s[i].size() > avg) up ++;else if (s[i].size() < avg) down ++;if (s[i].size() < shor.size()) {shor = s[i];resa = i;}if (s[i].size() > lon.size()) {lon = s[i];resb = i;}}if (up >= 3) cout << mp[resa] << '\n';else if (down >= 3) cout << mp[resb] << '\n';else if (same) cout << "B\n";else cout << "C\n";return 0;
}

PROB1017 小明喝可樂

#include <bits/stdc++.h>using namespace std;int n, k;signed main() {cin >> n >> k;int m = n / k, s = n;while (m) {s += m;n = m + n % k;m = n / k;}cout << s << endl;return 0;
}

PROB1018 華強種瓜

#include <bits/stdc++.h>using namespace std;const int N = 250;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int n, k, r;
int g[N][N];signed main() {cin >> n >> k >> r;while (k --) {int x, y;cin >> x >> y;g[x][y] = 1;for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];if (a <= 0 || a > n || b <= 0 || b > n) continue;g[a][b] = 1;}}int res = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (g[i][j]) {//cout << i << ' ' << j << endl;res ++;}}}cout << res << endl;return 0;
}

PROB1019 天子與諸侯

#include <bits/stdc++.h>using LL = long long;
using namespace std;const int N = 1e3 + 7;LL n, a[N];signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}sort(a + 1, a + n + 1);    cout << a[n] + a[n - 1] + a[n - 2] << endl;return 0;
}

PROB1020 矩陣變換問題

#include <bits/stdc++.h>using LL = long long;
using namespace std;const int N = 7e2 + 9;int n, m, x;
int g[N][N]; 
bool st[N][N];signed main() {cin >> n >> m;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> x;g[i][j] = x;st[i][j] = 1;}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (g[i][j] == 1 && st[i][j]) {for (int k = 1; k <= n; k++) g[k][j] = 0, st[k][j] = 0;for (int k = 1; k <= m; k++)g[i][k] = 0, st[i][k] = 0;}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (j != 1) cout << ' ' << g[i][j];else cout << g[i][j];}cout << endl;}return 0;
}

PROB1021 小明的記憶游戲

#include <bits/stdc++.h>using LL = long long;
using namespace std;const int N = 7e2 + 9;int n, m, x;
LL a[N];
unordered_map<LL, bool> st;signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];st[a[i]] = true;}cin >> m;while (m --) {cin >> x;cout << (st.count(x) ? "YES\n" : "NO\n");}return 0;
}

PROB1022 小明算樹

#include <bits/stdc++.h>using LL = long long;
using namespace std;const int N = 1e4 + 9;int n, m, x, l, a, b;
bool st[N];signed main() {cin >> l >> m;while (m --) {int a, b;cin >> a >> b;for (int i = a; i <= b; i++) st[i] = true;}cout << count(st, st + l + 1, 0) << endl;return 0;
}

PROB1023 小明的抽獎游戲

#include <bits/stdc++.h>using LL = long long;
using namespace std;const int N = 7e2 + 9;int n, m, x;
LL a[N], b[N];
unordered_map<LL, bool> st;signed main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}cin >> m;for (int i = 1; i <= m; i++) {cin >> b[i];}int res = 0;for (int i = 1; i <= n; i++) {bool flag = false;for (int j = 1; j <= m; j++) {if (a[i] % b[j] == 0) {flag = true;break;}}if (flag) res ++;}cout << res << endl;return 0;
}

PROB1024 小明算分

#include <bits/stdc++.h>using LL = long long;
using namespace std;const int N = 7e2 + 9;int n, m;signed main() {cin >> n >> m;double res = 0;for (int i = 1; i <= n; i++) {double s = 0, x, minv = 100, maxv = -1;for (int j = 1; j <= m; j++) {cin >> x;s += x;maxv = max(maxv, x), minv = min(minv, x);}s = s - maxv - minv;res = max(res, s);}printf("%.2f\n", res / (m - 2));return 0;
}

PROB1025 開普勒星球歷法

#include <bits/stdc++.h>using namespace std;int y, m, d, n;
int days[15] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 30, 31};bool isleap(int y) {return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}void work(int year, int n) {days[2] += isleap(year);int m = 1, d = n;while (d > days[m]) {d -= days[m], m ++;}cout << m << ' ' << d << endl;
}signed main() {cin >> y >> n;work(y, n);return 0;
}

PROB1026 子串計數

#include <bits/stdc++.h>using namespace std;int n;signed main() {cin >> n;while (n --) {string s, q;cin >> s >> q;int res = 0;for (int i = 0; i < s.size(); i++) {string cur = s.substr(i, q.size());if (cur == q)res ++;}cout << res << endl;}return 0;
}

PROB1027 房屋裝修

#include <bits/stdc++.h>using namespace std;signed main() {long long n, m, a;cin >> n >> m >> a;cout << ceil(1.0 * n / a) * ceil(1.0 * m / a) << endl;return 0;
}

PROB1028 最長連續上升子序列

#include <bits/stdc++.h>using namespace std;const int N = 1e4 + 7;int n, a[N];signed main() {cin >> n;for (int i = 0; i < n; i ++ ) {cin >> a[i];}int cur = 1, res = 1;for (int i = 1; i < n; i ++ ) {if (a[i] > a[i - 1])cur ++;else res = max(res, cur), cur = 1;}cout << res << endl;return 0;
}

PROB1029 社交網絡

#include <bits/stdc++.h>using LL = long long;
using namespace std;const int N = 1e4 + 7;int n, a[N];
unordered_map<LL, LL> mp;signed main() {cin >> n;while (n -- ) {int a, b;cin >> a >> b;mp[a] ++, mp[b] ++;}LL res = 0;for (auto [k, v] : mp) {res = max(res, v);}cout << res << endl;return 0;
}

PROB1029 極速狂飆

#include <bits/stdc++.h>using LL = long long;
using namespace std;typedef pair<int, string> PIS;
const int N = 1e4 + 7;int n, a[N];
string b[N];
vector<PIS> v;signed main() {cin >> n;for (int i = 0; i < n; i ++ ) {cin >> a[i];}for (int i = 0; i < n; i ++ ) {cin >> b[i];}for (int i = 0; i < n; i ++ ) {v.emplace_back(a[i], b[i]);}sort(v.begin(), v.end(), [&](auto &a, auto &b) {return a.first < b.first;});for (int i = 0; i < 3; i++) {cout << v[i].second << endl;}return 0;
}

PROB1030 灰獵犬號

#include <bits/stdc++.h>using LL = long long;
using namespace std;typedef pair<int, string> PIS;
const int N = 1e2 + 7;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int n, m;
int g[N][N];void dfs(int x, int y) {g[x][y] = 0;for (int i = 0; i < 4; i++) {int a = x + dx[i], b = y + dy[i];if (a <= 0 || a > n || b <= 0 || b > m) continue;if (g[a][b] == 1) dfs(a, b);}
}signed main() {cin >> n >> m;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> g[i][j];int res = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)if (g[i][j]) dfs(i, j), res ++;cout << res << endl;return 0;
}

PROB1031 拿破侖傳 (背包)

#include <bits/stdc++.h>using namespace std;const int N = 2e4 + 7;int n, m, a[N], f[N];signed main() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) {for (int j = m; j >= a[i]; j--) {f[j] = max(f[j], f[j - a[i]] + a[i]);}}cout << f[m] << endl;return 0;
}

2024南京郵電大學上機復試：現場編程（第一場）

A. 密碼問題

描述：

寒假結束后，小明回到了久違的實驗室，結果……小明突然發現他忘記了他的密碼。幸好，他曾經給自己留下了一些提示。
看起來，小明的提示是由兩個字符串 $S_1$和 $S_2$組成，他依稀的記得，密碼是由第一個字符串 $S_1$，去掉第二個字符串 $S_2$中所有出現過的字符得到的。

現在，小明想要你幫助他算出密碼。

輸入：

第一行包含一個字符串 $S_1$，長度不超過 105，至少包含 1個字符。
第二行包含一個字符串 $S_2$，長度不超過 105，至少包含 1個字符。

題目保證， $S_1$ 和 $S_2$都只包含$ASCII$碼 $[32,126]$的可見字符（即大小寫字母、數字、標點符號和空格），且空格不會出現在字符串的首尾。

輸出：

輸出一個字符串，即小明的密碼。題目保證，密碼不為空或者全為空格。

樣例輸入：

This_is_not_my_password
_not_

樣例輸出：

Thisismypasswrd

=

樣例輸入：

NJUPT
njupt njupt njupt

#####樣例輸出：

NJUPT

樣例輸入：

a#b^c %d?e
abcdef

樣例輸出：

#^ %?

注釋：

第一個樣例中，S1 為 This_is_not_my_password，S2 為 _not_，去掉 S2
中的所有字符（_、n、o 和 t）后，得到 Thisismypasswrd。
對于 20% 的數據，S2 的長度不超過 1。
對于 40% 的數據， $S_1$ 和 $S_2$的長度不超過10。
對于 60% 的數據， $S_1$ 和 $S_2$僅由小寫字母組成。
對于 80% 的數據， $S_1$ 和 $S_2$不包括空格。
對于 100%的數據， $S_1$ 和 $S_2$都只包含$ASCII$碼 $[32,126]$的可見字符（即大小寫字母、數字、標點符號和空格），長度不超過105，且空格不會出現在字符串的首尾。

AC Code

#include <bits/stdc++.h>using namespace std;const int N = 2e4 + 7;int n, m;
unordered_map<char, int> mp;signed main() {string s1, s2, res;getline(cin, s1);getline(cin, s2);for (auto &c : s2) {mp[c] = 1;}for (auto &c : s1) {if (mp.count(c)) continue;res += c;}cout << res << endl;return 0;
}

B. 掃雷分析器

描述：

《掃雷》是一款單人或者多人的電腦游戲。游戲目標是找出所有沒有地雷的方格，完成游戲；要是按了有地雷的方格，游戲失敗。

小明是一個狂熱的掃雷愛好者，可是自從換到了新電腦后，他發現新電腦沒有裝掃雷游戲。于是他決定自己寫一個掃雷游戲🤣。

小明發現，掃雷的游戲規則是這樣的：

游戲開始于一個 n行m列的雷區，雷區中，一些格子含有隱藏的地雷（稱之為地雷格），而其他格子不含地雷（稱之為非地雷格）。當玩家翻開一個非地雷格時，該格將會出現一個數字——提示周圍八個格子中有多少個是地雷格。玩家可以利用這些數字來推斷哪些格子是地雷格，哪些格子是非地雷格。

現在，小明已經編寫好了生成地雷格的程序，他想請你幫忙編寫一個程序，來生成雷區中的非地雷數字格子，以此提示周圍格子中有多少個地雷格。

輸入：

第一行一三個整數 n， m和 k，表示掃雷棋盤的行數和列數和地雷總數，題目保證，$1\le n,m\le 100，1\le k\le n\times m$。接下來 k行，每行兩個整數 $c_i和r_i$，表示第 i個地雷格位于第 $c_i$列，第$r_i$行。題目保證$(1\le c_i\le m,1\le r_i\le n)$且地雷格坐標不重復。

輸出：

輸出包含n行，m列，表示雷區中的非地雷數字格子。如果一個格子是地雷格，則輸出一個星號*；否則輸出一個數字，表示周圍格子中有多少個地雷格。

樣例輸入：

3 3 2
1 1
2 3

樣例輸出：

*10
221
1*1

樣例輸入：

2 3 2
2 1
1 2

樣例輸出：

2*1
*21

樣例輸入：

4 3 1
1 3

樣例輸出：

000
110
*10
110

注釋：

對于 20% 的數據，$k=1$。
對于 40%的數據，$n=1$或 $m=1$。
對于 60%的數據，$n,m\le 10$。
對于 80%的數據，$n,m\le 50$。
對于 100% 的數據，$1\le n,m\le 100，1\le k\le n\times m$。

AC Code

#include <bits/stdc++.h>using namespace std;const int N = 1e2 + 7;int n, m, k;
char g[N][N];signed main() {cin >> n >> m >> k;while (k -- ) {int x, y;cin >> y >> x;g[x][y] = '*';}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (g[i][j] == '*') {cout << g[i][j];}else  {int cnt = 0;for (int dx = -1; dx <= 1; dx ++)for (int dy = -1; dy <= 1; dy ++) {int curx = i + dx, cury = j + dy;if (curx >= 1 && curx <= n && cury >= 1 && cury <= m && g[curx][cury] == '*')cnt ++;}cout << cnt;}}cout << endl;}return 0;
}

2024南京郵電大學上機復試：現場編程（第二場）

A. 數字游戲

描述：

在馬爾代夫回程的飛機上，百無聊賴的小明和小紅玩起了游戲。為了難倒小明，小紅出了一個很復雜的問題。小紅會給出一個正整數 n，小明則需要統計 [1,n] 中，滿足下列條件的正整數的數目：該數小于或等于 n且各位數字之和為偶數，正整數的各位數字之和是其所有位上的對應數字相加的結果；該數是素數。若找不到滿足上述條件的數，則答案為 0。小紅覺得她贏定了，可是沒想到，小明偷偷地把這個問題告訴了你，并且希望聰明的你能夠發揮計算機的力量，通過編程解決這一問題。

輸入：

輸入包含一個正整數$n(1\le n\le 105)$。

輸出：

輸出一個整數，表示滿足條件的正整數的數目。

樣例輸入：

4

樣例輸出：

1

樣例輸入：

30

樣例輸出：

5

注釋：

對于第一個樣例，滿足條件的正整數為 2。只有 2和 4滿足小于等于 4且各位數字之和為偶數，但是只有 2是素數。
對于第二個樣例，滿足條件的正整數為 2,11,13,17,19。只有 14個整數滿足小于等于 30 且各位數字之和為偶數，分別是： 2,4,6,8,11,13,15,17,19,20,22,24,26,28，但是只有 2,11,13,17,19是素數。
題目保證，對于 20%的數據，$n\le 10$。
題目保證，對于 40%的數據，$n\le 100$。
題目保證，對于 60% 的數據，$n\le 1000$。
題目保證，對于 80% 的數據，$n\le 10^4$。
題目保證，對于 100%的數據，$n\le 10^5$。

AC Code

#include <bits/stdc++.h>using namespace std;int n;bool isprime(int x) {if (x < 2) return false;for (int i = 2; i <= x / i; i++) {if (x % i == 0)return false;}return true;
}signed main() {cin >> n;int res = 0;for (int i = 2; i <= n; i++) {int x = i, s = 0;while (x) {s += x % 10;x /= 10;}if (isprime(i) && s % 2 == 0) res ++ ;}cout << res << endl;    return 0;
}

B. 載人航天 (簡單背包變形，同ROB1038拿破侖傳)

描述：

載人航天是人類探索太空的重要方式之一。載人航天的目的是將宇航員送入太空，進行科學實驗、技術驗證、空間站建設等任務。載人航天的發展歷程可以追溯到20世紀50年代，當時蘇聯和美國開始了載人航天的競賽。1961年，蘇聯宇航員加加林成功地進行了第一次載人航天飛行。1969年，美國宇航員阿姆斯特朗成功地登上了月球。自此之后，載人航天技術不斷發展，人類在太空中進行了大量的科學實驗和技術驗證。

為了盡可能的的延長宇航員在太空中的停留時間，食物是必不可少的，但是飛船的容量有限，僅能裝載一部分食物箱上去。現在，宇航局握有所有食物箱的卡路里和質量，你需要幫助宇航局選擇出一部分食物箱，使得它們的總質量不超過飛船的承載能力，同時總卡路里最大。

輸入：

第一行兩個整數 n 和 m，表示食物箱的數量和飛船的承載能力。題目保證，1≤n≤100， $1\le m\le 1000$。

接下來 n行，每行兩個整數 wi 和 vi，表示第 i個食物箱的質量和卡路里。題目保證，$1\le w_i,v_i\le 100$。

輸出：

輸出一行一個整數，表示能夠帶上飛船的食物箱的最大總卡路里。

樣例輸入：

3 70
71 100
69 1
1 2

樣例輸出：

3

樣例輸入：

4 1
3 5
2 7
4 11
9 2

樣例輸出：

0

樣例輸入：

5 25
1 1
1 2
1 3
1 4
1 5

樣例輸出：

15

注釋：

在第一組樣例中，由于總負載不超過 70 ，所以可以選擇第2和第3個食物箱，總卡路里為 1+2=3。
題目保證，對于 20%的數據點，$(\sum n_i=1w_i)\le m$。
題目保證，對于 20%的數據點，$n\le 3$（類似樣例1）。
題目保證，對于 60% 的數據點，數據中每一個食物箱的質量 $w_i$都是相同的（類似樣例3）。
題目保證，對于 $100$的數據點，$1\le w_i,v_i\le 100，1\le n\le 100，1\le m\le 1000$。

AC Code

#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 7;int n, m;
int f[N];signed main() {cin >> n >> m;for (int i = 1; i <= n; i++) {int w, v;cin >> w >> v;for (int j = m; j >= w; j--) {f[j] = max(f[j], f[j - w] + v);}}cout << f[m] << endl;return 0;
}