【考研】复试相关上机题目

22机试回忆版

1、判断燃气费

描述

在某国，由于能源短缺，家庭用燃气费居高不下，政府提倡每家每户节约用气，特制定了阶梯燃气费的政策:

• 每户每月用气量在0~30立方米时，每立方米价格为5元;
• 超过30立方米之后，每立方米价格为8元;

现在给定某户人家某月的用气量，请计算输出该户人家这月的燃气费，
输出结果显示两位小数，两位小数之后的部分四舍五入。
注:请使用双精度浮点数，以确保计算对精度的要求。
提示:可以使用printf("%.21f",.....)实现显示两位小数，两位小数之后的部分四舍五入。

输入格式

输入为一个浮点数，表示用气量

输出格式

输出为燃气费

输入样例

40

输出样例

230.00

$Code$

void solve() {double x;cin >> x;cout << fixed << setprecision(2) << (x > 30 ? 30.0 * 5 + (x - 30) * 8 : x * 30) << '\n';
}

2、统计闰年数量

描述

闰年是指(年份能够被400整除)或(年份能够被4整除但不能够被100整除)的年份。现给定起止年份，输出从起始年份到终止年份(包括起止年份)共有多少个闰年。

输入格式

两个正整数，$n$和$m$$(0<n<m<=2022)$，分别表示起止年份。

输出格式

输出闰年的数量

输入样例

2000 2022

输出样例

6

$Code$

void solve() {int n, m;cin >> n >> m;int res = 0;for (int i = n; i <= m; i++) {res += (i % 400 == 0 || (i % 4 == 0 && i % 100 != 0));}cout << res << '\n';
}

3、打印图形

描述

给定正整数$n$，输出如下边长为n的星号平行四边形。
例如$n=3$时，输出

*
**
******

例如 $n=4$ 时，输出

*
**
***
**********

要求星号平行四边形上部不能有多余空行，左边不能有多余空列

输入格式

一个正整数$n(n<=30)$

输出格式

如题要求的星号平行四边形。

$Code$

void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++)cout << '*';cout << '\n';}for (int i = 1; i < n; i++) {for (int j = 1; j <= i; j++) cout << ' ';for (int j = i + 1; j <= n; j++) cout << '*';cout << '\n';}
}

4、密文数据

描述

$n$位的正整数$(0<n<10)$，现在由键盘输入正整数n，请编程输出密文数据。加密规则为:每位数字加6，然后用和除以8的余数再加1，代替该数字，即为密文数据。

输入格式

一个正整数 $n(0<n<10)$

输出格式

密文数据

输入样例

123

输出样例

812

$Code$

void solve() {string s;cin >> s;for (auto &c : s) {int x = c - '0';cout << (x + 6) % 8 + 1;}
}

5、（NOIP2015）金币

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续$N$天每天收到$N$枚金币后，骑士会在之后的连续$N+1$天里，每天收到$N+1$枚金币。
请计算在前$K$天里，骑士一共获得了多少金币。

输入格式

一个正整数 $n(0<n<10000)$

输出格式

骑士获得的金币数。

输入样例

6

输出样例

14

$Code$

void solve() {// 预处理vector<int> v; v.push_back(0);for (int i = 1; i <= 500; 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;
}

6、记忆密码

描述

王教授是一位数学家，他在上网时，总喜欢用4个数字给自己的帐号设置密码，为了便于记忆密码，王教授选择的4个数字正好构成等差数列，例如下面四个数字4 8 12 16当每一次出现忘记4个密码数字中的某一个数字时，王教授都可以通过另外3个数推算出忘记的数字，现在轮到你来算出被忘记的数字。按数列顺序给定还记得的3个数，问忘记的数是多少?

输入格式

第一行三个整数

输出格式

输出被忘记的数字（如果满足条件的数字不止一个，输出最小的那一个）

输入样例

2 4 8

输出样例

6

$Code$

void solve() {int a, b, c;cin >> a >> b >> c;// 等差数列int d1 = b - a, d2 = c - b;if (d1 == d2) cout << a - d1;else if (d1 < d2) cout << b + d1;else cout << b - d2;
}

7、真质数

描述

找出正整数M和N之间(N不小于M)的所有真质数。真质数的定义:如果一个正整数P为质数，且其反序也为质数，那么P就是真质数。例如，11，13均为真质数，因为11的反序还是为11，13的反序为31也为质数。

输入格式

输入两个数$M$和$N$，空格间隔，$1\le M\le N\le 1000$。

输出格式

按从小到大输出M和N之间(包括M和N)的真质数，每行一个。
如果之间没有真质数，则输出N0。

输入样例

10 35

输出样例

11
13
17
31

$Code$

bool check(int x) {if (x < 2) return false;for (int i = 2; i < x / i; i++) {if (x % i == 0) return false;}return true;
}void solve() {int a, b;cin >> a >> b;int res = 0;for (int i = a; i <= b; i++) {string s = to_string(i);reverse(s.begin(), s.end());if (check(i) && check(stoi(s))) {res ++;cout << i << '\n';}}if (!res) cout << "NO\n";
}

8、倒置句子

描述

给定一行英文句子(以回车结束，由字母、标点符号和空格组成，最长不超过120字符)，现要求将句子中的每一个英文单词倒置过来，其它符号位置不变。例如:
I ma yppah yadot! 处理完变成 I am happy today!
注:为了简化处理，假设句子中不存在合成形式，例如doesn’t，也不存在复合词，例如well-being

输入格式

一行英文句子，以回车结束，最长不超过120字符

输出格式

单词倒置后的句子

输入样例

oT eb, ro ton ot eb

输出样例

To be, or not to be

$Code$

void solve() {string str;getline(cin, str, '\n');string res;stack<char> st; // 使用栈翻转for (auto c : str) {if (isalpha(c)) {st.push(c);} else {while (!st.empty()) {res += st.top();st.pop();}res.push_back(c);}}while (!st.empty()) {res += st.top();st.pop();}cout << res << endl;
}

9、分割子串

一个字符串序列只包含左右括号两种字符，并且确保它是一个合法的括号序列。现在我们想把这个字符串分割成若干个子串，且分割后的每个子串仍是一个合法的括号序列，请问分割后最多能得到多少个子串。
比如括号序列”（()）()”，可以在第四个字符处分割得到最多两个子串，因此答案是2，而括号序列”（()())”，无法分割得到合法的子串，答案是1。

输入格式

第一行一个整数 $n$ 表示字符串长度。$（2<=n<=80）$
第二行一个学符串。

输出格式

分割后最多能得到子串数量。

输入样例

10
()()(()())

输出样例

3

$Code$

void solve() {int n;string str;cin >> n >> str;// 贪心int cnt = 0, res = 0;for (auto &c : str) {c == '(' ? cnt ++ : cnt --;if (cnt == 0) res ++;}cout << res << endl;
}

10、修剪二叉树

一棵二叉树的每个结点都有一个美丽值（可能为负值），所有结点的美丽值之和为二叉树的美丽值。作为农业大学的学生，你需要修剪某些结点使得树的美丽值尽可能的大。注意当你剪掉某个结点时，这个结点的所有子结点也会被剪掉。请输出修剪后二叉树后可能得到的最大美丽值。

输入格式

第一行一个整数n,表示结点数量，结点编号1至n，且1为根节点。$（1<=n<=10000)$
第二行$n$个整数，代表结点$1$至$n$的美丽值。之后$n$行，每行3个整数，3个数字分别为结点编号，结点左孩子和右孩子编号。

输出格式

一个整数，修剪后二叉树的最大美丽值。
注意：不论如何修剪，必须保留根结点，因为根结点都没有，树还在吗？

输入样例

5
5 -16 23 12 -17
1 2 5
2 3 4
3 0 0
4 0 0
5 0 0

输出样例

24

$Code$

const int N = 1e4 + 7;int n;
int a[N], l[N], r[N];int dfs(int u) {if (u == 0) return 0;int left = dfs(l[u]);int right = dfs(r[u]);return max(left, 0) + max(right, 0) + a[u];
}void solve() {cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {int x, lv, rv;cin >> x >> lv >> rv;l[x] = lv, r[x] = rv;}cout << dfs(1) << endl;
}

11、吃豆子

小明是一位游戏高手，他最喜欢的游戏是一种吃豆子游戏：
在一个n行m列的方格内，每一个方格中有一个豆子，每一个豆子有相应的分值，当游戏玩家控制吃豆人进入方格时就会立即吃掉该格的豆子，得到该豆子的分值，但是并不是每一次都加分，有些有毒的豆子吃了会减分。
游戏开始时，吃豆人会首先出现在最左上的方格内，玩家可以通过键盘上的上下左右键控制吃豆人向上下左右第一次走一格，当吃豆人走到最右下的方格内时，游戏结束。小明每次玩这个游戏都能得到非常高的分数，然而今天，他的键盘“向上”和“向左”的控制键坏了，他只能通过键盘控制吃豆人向右和向下走，小明一下子变得不太会玩这个游戏了，他希望你帮忙，给定一个n行m列的游戏布局，问在“向上”和“向左”两个控制键损坏的情况下，游戏结束时最多能吃到多少分数？

输入格式

第一行两个数$n$和$m(0<m,n=100)$，分别代表行数和列数。
此后$n$行，每行$m$个数（每个数在$[-100，100]$范围内），以空格分隔

输出格式

输出能得到的最高分数

输入样例

2 3
2 5 -2
3 -8 4

输出样例

9

$Code$

const int N = 1e2 + 7;int n, m;
int dp[N][N], a[N][N];void solve() {cin >> n >> m;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> a[i][j];}}// 初始化dp[0][0] = a[0][0];for (int i = 1; i < n; i++) {dp[i][0] = dp[i - 1][0] + a[i][0];}for (int i = 1; i < m; i++) {dp[0][i] = dp[0][i - 1] + a[0][i];}// dpfor (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];}}cout << dp[n - 1][m - 1] << endl;
}

12、恋爱配对

小D同学最近在开发一款恋爱配对的社交软件。若有单身男和单身女各$n$人，配对软件根据各人性格、爱好、家庭和条件等，为任意两个男女计算了一个配对矩阵$P$和$Q$。$P[i][j]$值表示若以男$i$为主导和女$j$进行配对的分值，$Q[i][j]$值表示若以女$j$为主导和男$i$进行配对的分值，由于心理状态等因素，$P[i][j]$不一定和$Q[i][j]$相等。那么，将男i和女恋爱配对的适配度记为$P[i][j]\ast Q[i][j]$。
请你设计一个恋爱配对算法，计算这$2n$个单身男女（共$n$对）的每一对男女的适配度总和，使他们整体上的适配度总和达到最大。如下的$P$和$Q$矩阵为例，最佳男女恋爱配对应该为（男1，女1）、（男3，女2）和（男2，女3），适配度总和最大值为$10\ast 2+4\ast 5+4\ast 3=52$。
$$P=\left[\begin{array}{ccc}10& 2& 3\\ 2& 3& 4\\ 3& 4& 5\end{array}\right]Q=\left[\begin{array}{ccc}2& 2& 2\\ 3& 5& 3\\ 4& 5& 1\end{array}\right]$$

输入格式

输入数据第一行有1个正整数为$n(1<n<10)$。接下来的$2n$行，每行$n$个正整数，以空格间隔。
前$n$行是$P$，后$n$行是$Q$。

输出格式

输出所有配对方案中整体上男女适配度总和的最大值。

输入样例

3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1

输出样例

52

思路

全排列搜索所有答案并更新

$Code$

#include <bits/stdc++.h>using namespace std;const int N = 15;int n;
int p[N][N], q[N][N], girls[N];
bool vis[N];
int res = 0;void dfs(int x, int sum) {if (x == n) { // 男生选完res = max(res, sum);return ;}for (int y = 0; y < n; y++) { if (!vis[y]) {// 未被匹配的女生配对vis[y] = true;dfs(x + 1, sum + p[x][y] * q[x][y]);vis[y] = false;}}
}void solve() {cin >> n;for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)cin >> p[i][j];for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)cin >> q[i][j];for (int i = 0; i < n; i++) girls[i] = i;// do {//     int cur = 0;//     for (int i = 0; i < n; i++) {//         int x = i, y = girls[i];//         cur += p[x][y] * q[x][y];//     }//     res = max(res, cur);// } while (next_permutation(girls, girls + n));dfs(0, 0);cout << res << endl;
}int main() {int t = 1;// cin >> t;while (t--) solve();return 0;
}

---

杂

N1478喝饮料

题目描述

商店里有$n$中饮料，第i种饮料有$m_i$毫升，价格为$w_i$。
小明现在手里有$x$元，他想吃尽量多的饮料，于是向你寻求帮助，怎么样买才能吃的最多。
请注意，每一种饮料都可以只买一部分。

输入描述:

有多组测试数据。
第一行输入两个非负整数$x$和$n$。
接下来$n$行，每行输入两个整数，分别为$m_i$和$w_i$。
所有数据都不大于$1000$。
$x$和$n$都为$-1$时程序结束。

输出描述:

请输出小明最多能喝到多少毫升的饮料，结果保留三位小数。

输入样例

233 6 
6 1
23 66
32 23
66 66
1 5
8 5
-1 -1

输出样例

136.000

思路

贪心 根据每种饮料的性价比排序， 按性价比依次购买即可

$Code$

typedef pair<double, double> PDD;
const int N = 1e3 + 7, inf = 0x3f3f3f3f;int n, m;void solve() {while (cin >> m >> n) {if (m == -1 && n == -1) break;vector<PDD> v;for (int i = 1; i <= n; i++) {double x, y;cin >> x >> y;v.emplace_back(x ,y);}sort(v.begin(), v.end(), [&] (PDD &a, PDD &b) {return a.y / a.x < b.y / b.x;});int s = m;double res = 0;for (auto &p : v) {if (s <= 0) break;int mi = p.x, wi = p.y;if (s >= wi) {res += mi, s -= wi;} else {res += mi * (1.0 * s / wi);s = 0;}}printf("%.3f\n", res);}
}

N1111斐波那契数列

题目描述

存在如下数列1、1、2、4、7、13、24、44、81、149……，现要求该数列第n项的值(n从0开始算)。

输入描述:

输入包含多组测试数据，每组数据包含一个整数$n(0<=n<=70)$。

输出描述:

每组输出只占一行，包含一个整数，表示该数列第n项的值。输出结果用64位数字保存。

输入样例

0
1
2
3
4
5
6
7
8
9

输出样例

1
1
2
4
7
13
24
44
81
149

$Code$

#define int long long
const int N = 70 + 7, inf = 0x3f3f3f3f;int n, f[N];void init() {f[0] = 1, f[1] = 1, f[2] = 2;for (int i = 3; i <= 70; i++) {f[i] = f[i - 1] + f[i - 2] + f[i - 3];}
}void solve() {init();while (cin >> n) {cout << f[n] << endl;}
}

N1542这是第几天？

题目描述

输入一个年月日的有效日期，输出这一天是今年第几天？

输入样例

2018-01-11

输出样例

11

$Code$

const int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};bool check(int y) {return (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0));
}void solve() {int y, m, d;scanf("%d-%d-%d", &y, &m, &d);int res = d + (m > 2 && check(y));for (int i = 1; i < m; i++) res += months[i];printf("%d\n", res);
}

N1520字符游戏

题目描述

明又得到了一个字符数组，每个字符都是a-z其中的一个，你需要统计出每种字符出现的次数，他的幸运数字还是5和7，所以需要你按出现顺序输出其中个数是5和7的倍数的字符，并输出其个数。

输入描述

第一行包含一个正整数$n(1<=n<=1000)$，第二行是一个含有n个字符的字符数组

输出描述

按题意输出

输入样例

24
aaaaabbbbbbbbbbccddddddd

输出样例

a 5
b 10
d 7

$Code$

int n, mp[26];
string str;void solve() {cin >> n >> str;string seq;for (auto &c : str) {if (++ mp[c - 'a'] == 1)seq.push_back(c);}for (auto &c : seq) {int k = mp[c - 'a'];if (k % 5 == 0 || k % 7 == 0)cout << c << ' ' << k << endl;}
}

N1870字符值

题目描述

给定一个字符串S，s1为S的子串，求s1的ASCll值之和。

输入描述

第一行输入一行字符串S（不含空格）。
第二行输入一个整数n，代表有n次询问。
接下来n行，每行两个整数$l，r（1<=l<=r<=|S|）$。表示$s1$的开始和结束（下标从1开始）。

输出描述

对于每次询问，输出一个整数x表示答案

输入样例

asdfgKL
3
1 2
2 3
1 7

输出样例

212
215
668

提示

数据范围：
对于30%的数据：$S<=100,1<=q<=1000$
对于50%的数据：$S<=1000,1<=q<=100$
对于100%的数据：$S<=1000,1<=q<=100000$

$Code$

//
// Created by SpareLin on 2025/2/20.
// 给定一个字符串S，s1为S的子串，求s1的ASCll值之和。 前缀和处理
//
#include <bits/stdc++.h>using namespace std;const int N = 1e3 + 7;int q, l, r, s[N];
string str;int main() {cin.tie(nullptr)->ios::sync_with_stdio(false);cin >>  str;cin.get();int n = str.size();for (int i = 0; i < n; i++) {s[i + 1] = s[i] + str[i];}cin >> q;while (q --) {cin >> l >> r;cout << s[r] - s[l - 1] << '\n';}return 0;
}

ISBN号码识别

题目描述

每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如x-xxx-xxxxx-x，其中符号-就是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符-之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。
识别码的计算方法如下：
首位数字乘以1加上次位数字乘以2……以此类推，用所得的结果与 11求余，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1,2,…,9再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的结果4作为识别码。

你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出Right；如果错误，则输出你认为是正确的ISBN号码。

输入描述

一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。

输出描述

一行，假如输入的ISBN号码的识别码正确，那么输出Right，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符-）。

输入样例

0-670-82162-4

输出样例

Right

$Code$

//
// Created by SpareLin on 2025/2/20.
// ISBN号码识别
#include <bits/stdc++.h>using namespace std;int main() {string str;cin >> str;int res = 0, k = 1;for (int i = 0; i < str.size() - 1; i++) {if (isdigit(str[i]))res += (str[i] - '0') * k ++;}res %= 11;if ((res == 10 && str.back() == 'X') || res == str.back() - '0') {cout << "Right\n";} else {if (res == 10) str.back() = 'X'; else  str.back() = res + '0'; cout << str << '\n';}return 0;
}

怎么借书

题目描述

小明有n本书，他的好朋友小红、小新、小林想向小明借书，若每人只能借一本书，可以有多少种不同的借法？

输入描述

一个整数n，代表书的序号为（1、2、……、n）。

输出描述

用A，B，C分别代表三个好朋友
依次输出每个人可借的书序号
以及有效的借阅方法总数。

输入样例

3

输出样例

A:1 B:2 C:3
A:1 B:3 C:2
A:2 B:1 C:3
A:2 B:3 C:1
A:3 B:1 C:2
6

$Code$

const int N = 1e4 + 7;int path[N], res;
bool vis[N];void dfs(int u) {if (u == 3) {res ++;for(int i = 0; i < 3; i++) printf("%c:%d ",'A' + i, path[i]);printf("\n");return ;}for (int i = 1; i <= n; i++) {if (!vis[i]) {path[u] = i;vis[i] = true;dfs(u + 1);vis[i] = false;}}
}void solve() {int n;cin >> n;// dfs(0);for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {if (i == j || i == k || j == k) continue;res ++;cout << "A:" << i << " " << "B:" << j << " " << "C:" << k << endl;}}}cout << res << endl;
}