上海市计算机学会月赛 2022年8月月赛丙组

赶时间，没有对题目错字进行处理

角谷猜想

内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个正整数 nn，若 nn 是偶数，将 nn 的值减少一半，如果 nn 是奇数，将 nn 的值乘 33，再加 11。不断地重复这个操作，任何正整数最后都会变成 11。这个猜想很可能是正确的，因为借助计算机，尚未发现存在反例。

给定 nn，请输出用上述操作将 nn 变成 11 的过程。

输入格式
单个整数表示 nn。

输出格式
若干整数，表示用角谷变换将 nn 变成 11 的过程。

数据范围
2leq nleq 500002≤n≤50000

样例数据
输入:
13
输出:
40 20 10 5 16 8 4 2 1
输入:
7
输出:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
分析：
简单模拟

#include <bits/stdc++.h>
using namespace std;
int main() {
	cin.tie(0);
	int n;
	cin >> n;
	while (n != 1) {
		if (n % 2 == 0)
			n /= 2;
		else
			n = n * 3 + 1;
		cout << n << " ";
	}
	return 0;
}

屏幕比例

内存限制: 256 Mb时间限制: 1000 ms
题目描述
现实生活中，我们一般把屏幕的宽度和高度的比例，称为屏幕比例，或称为屏幕长宽比。例如分辨率为 1920 * 1080 的屏幕，其长宽比即为 16 : 9

现给定一个屏幕的分辨率，以 X * Y 的形式输入，请你按给定格式输出该屏幕的长宽比。

输入格式
输入共一行，两个正整数x,yx,y，由 * 连接.
其中第一个数字为屏幕分辨率的水平像素，第二个数字为屏幕分辨率的竖直像素。

输出格式
输出共一行，输出该屏幕的长宽比，以 : 分割。

数据范围
对于50%50%的数据，1leq x,y leq 10001≤x,y≤1000
对于100%100%的数据，1leq x,y leq 10^91≤x,y≤10
9

样例数据
输入:
1920*1080
输出:
16:9
分析：
没必要手写gcd直接用函数，长宽比例就是x/gcd(x,y):y/gcd(x,y),注意输入

#include <bits/stdc++.h>
using namespace std;
long long x, y, g;
int main() {
	cin.tie(0);
	scanf("%lld*%lld", &x, &y);
	g = __gcd(x, y);
	cout << x / g << ":" << y / g;
	return 0;
}

最大子串

内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 nn 个整数 a_1,a_2,cdots,a_na
1
​
,a
2
​
,⋯,a
n
​
构成一个序列，请为这个序列寻找一个子串，使得它的数字之和达到最大。子串是指给定的序列中连续的一段数字，空串或原序列自身都算一种子串。

输入格式
第一行：单个整数 nn。
第二行：nn 个整数 a_1,a_2,dots,a_na
1
​
,a
2
​
,…,a
n
​
。

输出格式
单个整数：表示子串的最大和。

数据范围
对于 30%30% 的数据，1leq nleq 2001≤n≤200，
对于 60%60% 的数据，1leq nleq 50001≤n≤5000，
对于 100%100% 的数据，1leq nleq 200,0001≤n≤200,000。
-10000leq a_ileq 10000−10000≤a
i
​
≤10000
样例数据
输入:
5
1 2 -10 2 3
输出:
5
输入:
3
-1 -2 -3
输出:
0
输入:
3
3 -2 3
输出:
4
分析：
常规思路前缀和，a[i]为前i个数之和，依次比较哪几个数在一起最大。
非常规思路b记录一串的最大值，a[i]大于零就加上，小于零就另开一串。

前缀和：

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, a[200005], maxn = 0, minn = 2e7;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	for (int i = 1; i <= n; ++i) {
		minn = min(a[i], minn);
		maxn = max(maxn, a[i] - minn);
	}
	cout << maxn;
	return 0;
}

其他：

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, a, b = 0, sum = -100001;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a;
		if (b > 0)
			b += a;
		else
			b = a;
		if (b > sum)
			sum = b;
	}
	if (sum < 0)
		cout << 0;
	else
		cout << sum;
	return 0;
}

独立数

内存限制: 256 Mb时间限制: 1000 ms
题目描述
如果一个正整数的十进制表示中，每一位数字都不同，则称它为独立数。将所有独立数从小到大排列，给定 nn，请求出第 nn 小的独立数。

输入格式
单个整数：表示 nn。

输出格式
单个整数：表示第 nn 个独立数。

数据范围
对于 50%50% 的数据，1leq nleq 10001≤n≤1000
对于 100%100% 的数据，1leq nleq 4,000,0001≤n≤4,000,000
样例数据
输入:
1
输出:
1
输入:
11
输出:
12
说明:
跳过11
分析：
暴力不用想，虽然初测90，综测肯定只有60。满分还是得搜索，就是一个拆数的过程，搜索当前数没有的那个数字。
暴力（初90，复应该60）：

#include <bits/stdc++.h>
using namespace std;
int main() {
	cin.tie(0);
	long long n, f[11], cnt = 0, i = 0, flag;
	cin >> n;
	while (cnt != n) {
		++i;
		memset(f, 0, sizeof(f));
		int tmp = i;
		while (tmp) {
			++f[tmp % 10];
			tmp /= 10;
		}
		flag = 0;
		for (int j = 0; j <= 9; ++j)
			if (f[j] > 1) {
				flag = 1;
				break;
			}
		if (!flag)
			++cnt;
	}
	cout << i;
	return 0;
}

搜索：

#include <bits/stdc++.h>
using namespace std;
long long n, cnt, t = 0;
int flag = 0;
void dfs(int ws, long long k, int b) {
	if (flag == 1)
		return;
	if (ws == b) {
		++cnt;
		if (cnt == n) {
			flag = 1;
			cout << k;
		}
		return;
	}
	long long x = k;
	int f[10] = {0};
	while (x) {
		++f[x % 10];
		if (f[x % 10] > 1)
			return;
		x /= 10;
	}
	for (int i = 0; i <= 9; ++i) {
		if (!f[i]) {
			if (i != 0 || b != 0) {
				dfs(ws, k * 10 + i, b + 1);
			}
		}
	}
}
int main() {
	cin.tie(0);
	cin >> n;
	while (1) {
		++t;
		dfs(t, 0, 0);
		if (cnt == n)
			break;
	}
	return 0;
}

匹配括号（四）

内存限制: 256 Mb时间限制: 1000 ms
题目描述
括号序列是由 ( 与 ) 构成的序列。平衡的括号序列要求 ( 与 ) 出现次数一样多，而且序列的每个前缀里 ( 出现次数不低于 ) 的出现次数。

对平衡的括号序列，定义一种计分规则如下：

如果只有一对括号 ()，只算 11 分；
(A) 的分数是 A 的 22 倍；
AB 的分数是 A 与 B 的和，其中 A 与 B 必须是平衡的括号序列。
给定一个平衡的括号序列，请计算它的分数，由于数字可能很大，输出答案模 1,000,000,0071,000,000,007 的余数。

输入格式
单个字符串：表示输入的序列。

输出格式
单个整数：表示括号序列的分数模 1,000,000,0071,000,000,007 的余数。

数据范围
设 nn 表示输入字符串的长度，

对于 50%50% 的数据，1leq nleq 2001≤n≤200；
对于 100%100% 的数据，1leq nleq 200,0001≤n≤200,000。
样例数据
输入:
()()()
输出:
3
输入:
((()))
输出:
4
分析：
搞清楚测试答案是怎么来的,看一个匹配的括号中有几个已经匹配好的括号的和，记住要模

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
stack<long long> st;
int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); ++i) {
		if (s[i] == '(')
			st.push(0);
		else {
			int x = st.top();
			st.pop();
			if (x == 0)
				++x;
			else
				x *= 2;
			while (!st.empty() && st.top() > 0) {
				x += st.top();
				st.pop();
				x %= mod;
			}
			st.push(x);
		}
	}
	long long sum = st.top();
	cout << sum % mod;
	return 0;
}

最后

以上就是飞快服饰为你收集整理的上海市计算机学会月赛 2022年8月月赛丙组的全部内容，希望文章能够帮你解决上海市计算机学会月赛 2022年8月月赛丙组所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。