上海市计算机学会月赛 2022年9月月赛丙组
上海市计算机学会月赛 2022年9月月赛丙组
- 本次考试题目难度较高
- 计算矩形的周长及面积问题
- 探讨机会成本的概念及其经济意义
- 分析三色排序问题的时间复杂度
- 研究阶乘结果末尾零的数量规律
- 探讨前序遍历、中序遍历向后序遍历的转换方法
这次题目真的衡水
文章拖延了一段时间后仍未及时发布
文章拖延了一段时间后仍未及时发布
矩形的周长与面积
内存配置: 256兆字节
时间配置: 1秒
题目要求
请根据给定的矩形长度设为a、宽度设为b,请求输出该矩形所对应的周长与面积计算结果。
输入格式
两个整数表示 a 与 b。
单一数值代表矩形的周长
单一数值代表矩形的周长
数据范围
1≤a,b≤10000
样例数据
输入:
3 2
输出:
10
6
输入:
12 3
输出:
30
36
分析：
不分析
#include <bits/stdc++.h>
using namespace std;
long long a, b;
int main() {
cin >> a >> b;
cout << 2 * (a + b) << endl << a*b;
return 0;
}机会成本
内存占用上限设定为256 MB
用一个整数n来表示
接下来的n行
每个后续的输入包含两个整数a_i和b_i
输出格式
单个整数：表示最大的分数之和
数据范围
对于 30% 的数据，1≤n≤5,000；
对于 60% 的数据，1≤n≤20,000；
对于 100% 的数据，1≤n≤500,000；
0\leq b_i\leq a_i\leq 4000；
样例数据
输入:
3
1 1
2 0
3 2
输出:
5
说明:
选择做好第二件事
分析：
不要想复杂，就是所有的分数加起来再加上分差最大的一门。
#include <iostream>
using namespace std;
int a, b, n, cnt[500001], sum, maxn;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
cnt[i] = a - b;
maxn = max(maxn, cnt[i]);
sum += b;
}
cout << sum + maxn << endl;
return 0;
}三色排序
内存占用: 256 Mb
运行时长: 1000 ms
题目描述
假定有 n 个整数 a_1,a_2,\dots, a_n ，每个数值属于集合 {0,1,2} ，请将其中一部分进行两两交换以实现排序后达到升序状态，请问最少需要多少次交换才能完成排序？
输入格式
第一行：单个整数表示 n
第二行：n 个整数表示 a_1,a_2,\dots, a_n
输出格式
单个整数：表示最少交换次数。
数据范围
对于 30% 的数据，1≤n≤5,000；
对于 60% 的数据，1≤n≤100,000；
对于 100% 的数据，1≤n≤1,000,000；
0\leq a_i\leq 2
样例数据
输入:
5
2 0 1 2 0
输出:
1
说明:
将第一个2与最后一个0交换即可
分析：
看一下有多少个2和0的位置错了就换过来，因为1永远要是在中间的
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+1;
int n, c[MAXN], num[3], x1, x2, e0, e1;
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> c[i];
++num[c[i]];
}
for (int i = 1; i <= num[0]; ++i)
if (c[i] == 1)
x1++;
else if (c[i] == 2)
x2++;
for (int i = num[0] + num[1] + 1; i <= n; ++i)
if (c[i] == 1)
e1++;
else if (c[i] == 0)
e0++;
cout << x1 + x2 + e1 + e0 - min(e0, x2) << endl;
return 0;
}阶乘尾数
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个整数 n，n 的阶乘定义为
n!=1\times 2\times \cdots \times n
请计算在 n! 的十进制表示中，末尾有多少个连续的 0？
例如 n=5，则 n!=120，末尾有 1 个 0，又12!=479001600，末尾有 2 个 0。
输入格式
单个整数表示 n。
输出格式
单个整数表示 n! 中末尾零的个数。
数据范围
满足条件的情况包括以下几种：
- 当n在3到999之间时（即3≤n≤999）；
- 当n达到或超过1,000时（即n≥1,000）；
- 在所有情况下（即无论多大的n值）；
样例数据
输入案例：5 对应的输出结果是1；
另一组输入案例：12对应的输出结果为2；
具体来说，当n=12时，其阶乘值为479,001,600。
分析过程如下：该问题属于基础数学题型。我们需要计算的是n!中包含多少个因子5。由于每遇到一个5的倍数就会增加一个因子5，在更大的数字中则会增加更多。
#include <bits/stdc++.h>
using namespace std;
long long n;
long long f(long long n) {
long long num = 0, i, j;
for (i = 5; i <= n; i += 5) {
j = i;
while (j % 5 == 0) {
++num;
j /= 5;
}
}
return num;
}
int main() {
cin >> n;
cout << f(n);
return 0;
}前序中序转后序
内存占用不得超过256兆字节 时间限定为1秒内
输入格式
第一部分：一个字符串表示二叉树的先序遍历；
第二部分：一个字符串表示二叉树的中序遍历。
输出格式
单独一行：一个字符串，表示二叉树的后序遍历。
数据范围
设二叉树的结点数量为 n，
针对一半的数据（50%），变量n满足条件1≤n≤10。
全部的数据（100%）则满足条件1≤n≤26。
这些样例数据包括：
输入示例包括ACE和CAE，
输出结果为CEA。
分析： 按照前中序原则进行判断根节点和子节点的位置关系。
#include <bits/stdc++.h>
using namespace std;
int cnt = 0;
string n1, n2;
void tree(int l, int r, char ch) {
for (int i = l; i < r; ++i) {
if (n2[i] == ch) {
if (l < i)
tree(l, i, n1[cnt++]);
if (i + 1 < r)
tree(i + 1, r, n1[cnt++]);
cout << ch;
break;
}
}
}
int main() {
cin >> n1 >> n2;
tree(0, n1.size(), n1[cnt++]);
return 0;
}