上海市计算机学会月赛 2022年5月月赛丙组
上海市青少年算法竞赛月赛2022年5月月赛丙组
-
- 三数排序
- 珠玑妙算（一）
- 打印金字塔
- 最远城市距离
- 最大割
三数排序
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
给定三个整数 a,b,c，请将它们以从小到大的顺序排序后输出。
输入格式
单独一行：三个整数表示 a,b,c。
输出格式
单独一行：表示按升序排列后的三个数。
数据范围
-1000\leq a,b,c\leq 1000。
样例数据
输入:
6 4 2
输出:
2 4 6
输入:
1 1 1
输出:
1 1 1
简简单单排序题，直接sort（虽然只有三个数）
#include<iostream>
#include<algorithm>
using namespace std;
int a[3];
int main() {
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
cout << a[0] << " " << a[1] << " " << a[2];
return 0;
}珠玑妙算（一）
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
珠玑妙算（Mastermind）是一种猜谜游戏。
在游戏开始之前，系统将随机生成一个十位自然数（每位数字均不重复）作为谜底供玩家解答。玩家需输入一个十位自然数（每位数字也均不重复）作为答案。
请计算谜底中有多少个情况既被正确猜测了数字也确定了位置（称为完全命中），以及有多少个情况仅正确猜测了数字而未确定位置（称为部分命中）。
第一行：a 代表一个四位整数作为谜底。
第二行：b 对应于答案。
第一行：单一数值（表示完全命中次数）；
第二行：单一数值（表示部分命中次数）。
样例数据
输入:
5678
8671
输出:
2
1
说明:
6与7为完全猜中，8为部分猜中
首先将每个数字拆分为单独的位并存储到数组中，在初始存储过程中如果各位数值保持一致，则表示位置数组完全一致；随后进一步验证各位数值是否保持一致以确保数据的一致性
#include<iostream>
using namespace std;
int nums_a[4], nums_b[4], cnt[2] = {0, 0};
int i, j, a, b, len;
int main() {
cin >> a >> b;
for (i = 0; i < 4 ; ++i) {
nums_a[i] = a % 10, a /= 10;
nums_b[i] = b % 10, b /= 10;
if (nums_a[i] == nums_b[i])
++cnt[0];
}
for (i = 0; i < 4 ; ++i)
for (j = 0; j < 4 ; ++j)
if (nums_b[j] == nums_a[i])
++cnt[1];
cout << cnt[0] << endl << cnt[1] - cnt[0]; // 减去重复
return 0;
}打印金字塔
内存占用不超过256MB 时间限定为1秒
/\
/__\
/\ /\
/__\/__\
/\ /\ /\
/__\/__\/__\输入格式
单个整数：表示 n。
输出格式
根据题意输出层次为 n 的三角形金字塔。
数据范围
1\leq n\leq 30。
样例数据
输入:
3
输出:
/\
/__\
/\ /\
/__\/__\
/\ /\ /\
/__\/__\/__\输入:
8
输出:
/\
/__\
/\ /\
/__\/__\
/\ /\ /\
/__\/__\/__\
/\ /\ /\ /\
/__\/__\/__\/__\
/\ /\ /\ /\ /\
/__\/__\/__\/__\/__\
/\ /\ /\ /\ /\ /\
/__\/__\/__\/__\/__\/__\
/\ /\ /\ /\ /\ /\ /\
/__\/__\/__\/__\/__\/__\/__\
/\ /\ /\ /\ /\ /\ /\ /\
/__\/__\/__\/__\/__\/__\/__\/__\找规律，打空格，奇数打印左边，偶数打印右边。
#include <iostream>
using namespace std;
int i, j, k, l, n, m, x = 1;
char t = '\ '; // 转义字符，需要两个
int main() {
cin >> n;
n *= 2, m = n;
for (i = 0; i < n ; ++i) {
--m;
for (j = 0; j < m ; ++j)
cout << " ";
if (i % 2 == 0) {
for (k = 0; k < x ; ++k) {
if (k == 0)
cout << "/" << t;
else
cout << " /" << t;
}
cout << endl;
} else {
for (k = 0; k < x ; ++k)
cout << "/__" << t;
++x, cout << endl;
}
}
return 0;
}最远城市距离
内存限制设为256 Mb；时间限制设定为1秒。
第一行为单一数值n。
接下来从第二行开始一直到第n+1行中的一条记录包含两个数值代表一个数据点的位置。
输出格式
单个整数：表示最大的城市距离。
数据范围
- 占比为30%的数据集满足：$2\leq n\leq 5千；
- 占比为60%的数据集满足：$2\leq n\leq 5万；
- 所有数据集均满足：$2\leq n\leq 五百万。
- x_i,y_i的取值范围介于-五亿至+五亿之间。
样例数据
输入:
4
0 0
0 1
1 3
3 2
输出:
5
说明:
(0,0)与(3,2)的城市距离是最大的
递推，类似于曼哈顿距离化为切比雪夫距离求极差
#include <iostream>
using namespace std;
int i, n, x, y, max1, min1 = 2e9, max2, min2 = 2e9;
int main() {
cin >> n;
for (i = 0; i < n ; ++i) {
cin >> x >> y;
max1 = max(max1, x + y);
min1 = min(min1, x + y);
max2 = max(max2, x - y);
min2 = min(min2, x - y);
}
cout << max(max1 - min1, max2 - min2);
}最大割
内存占用：256MB；运行时间：1秒
问题陈述如下：
假设有一张无向图包含n个顶点和m条边。如果存在一种划分方式使得图上的所有顶点被不重复且不遗漏地分为两个非空的部分（分别记为集合S与\bar{S}），则称(S,\bar{S})为此图的一个分割（Cut）。
对于该分割(S,\bar{S})而言，则有多少条边跨越了这个分割？这个数值即为此分割的大小。我们的目标是找到具有最大割值的那个划分，并输出其对应的大小数值。
由两个整数组成的一行数字表示n和m；对于每一条边来说，其两端点分别由u和v这两个整数标识。
输出格式
单个整数：表示最大割的大小。
数据范围
- 对于 50\% 的数据，2\leq n\leq 16；
- 对于 100\% 的数据，2\leq n\leq 24；
- 1\leq m\leq 10000。
样例数据 输入: 输出:
深搜确定集合两个集合中的元素，使用二维数组标记
#include <iostream>
using namespace std;
int n, m, g[25][25], v[25], ans;
void dfs(int x, int num, int step)
{
for (int i = 1; i <= n; i++)
if (v[i])
num -= g[x][i]; //在T内
else
num += g[x][i]; //在S内
ans = max(ans, num);
if (step >= n)
return;
for (int i = x + 1; i <= n; i++)
{
v[i] = 1;
dfs(i, num, step + 1);
v[i] = 0;
}
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
++g[u][v], g[v][u] = g[u][v]; //无向边
}
v[1] = 1; //将点1放入T
dfs(1, 0, 1);
cout << ans;
return 0;
}