上海市计算机学会月赛 2022年8月月赛丙组
上海市计算机学会月赛 2022年8月月赛丙组
-
- 角谷猜想
- 屏幕比例
- 最大子串
- 独立数
- 匹配括号（四）
赶时间，没有对题目错字进行处理
角谷猜想
内存占用上限设定为256 MB；程序运行时长限定在1秒以内；输入参数n为一正整数；当n为偶数值时，请将n进行折半处理；否则请对n执行乘以3后加1的操作；这一猜想具有较高的可信度；目前尚未通过计算找到反例依据
给定 nn，请输出用上述操作将 nn 变成 11 的过程。
输入格式
单个整数表示 nn。
输出格式
若干整数，表示用角谷变换将 nn 变成 11 的过程。
数据范围
2\leq n\leq 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程序运行时长限定：1秒问题说明：在实际应用中通常将屏幕宽度与高度的比例定义为屏幕比例或屏幕长宽比举个例子说分辨率设置为1920×1080时则其比例就被设定为十六比九
现给定一个屏幕的显示分辨率，请您按照X乘以Y的形式输入，并按照指定格式输出该屏幕的长宽比。
在一行中输入一对正整数值x,y（x,y），它们通过星号分隔. 其中第一个数字代表水平方向的像素数量（Horizontal Pixels），第二个数字代表垂直方向的像素数量（Vertical Pixels）.
输出格式
输出共一行，输出该屏幕的长宽比，以 : 分割。
数据范围
对于50%50%的数据，1\leq x,y \leq 10001≤x,y≤1000
对于100%100%的数据，1\leq x,y \leq 10^91≤x,y≤10
9
分析： 无需手写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, 时间运行时长限定在1秒内
题目要求
注
输入格式
第一行：单个整数 nn。
第二行：nn 个整数 a_1,a_2,\dots,a_na
1
,a
2
,…,a
n
。
输出格式
单个整数：表示子串的最大和。
数据范围
对于 30%30% 的数据，1\leq n\leq 2001≤n≤200，
对于 60%60% 的数据，1\leq n\leq 50001≤n≤5000，
对于 100%100% 的数据，1\leq n\leq 200,0001≤n≤200,000。
-10000\leq a_i\leq 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. 题目要求如下：当且仅当一个正整数在其十进制形式中每个数字都不相同时, 称其为独立数. 现在将所有独立数按照升序排列, 给定参数n, 请找出第n小的独立数值.
输入格式
单个整数：表示 nn。
输出格式
单个整数：表示第 nn 个独立数。
数据范围
#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运行时长：1,000 ms
对平衡的括号序列，定义一种计分规则如下：
仅当只有一个单独的一对括号 () 存在时，则其得分为 11 分；
对于形如 (A) 的情况其得分为 A 成绩值的 22 倍；
当两个子结构 AB 组合时其总分等于 A 加 B之和，在这种情况下要求 A 和 B 必须构成平衡的括号序列；
请计算该平衡括号序列对应的总分，并输出结果取模于 1,000,000,07。
输入格式
单个字符串：表示输入的序列。
输出格式
单个整数：表示括号序列的分数模 1,000,000,0071,000,000,007 的余数。
数据范围
设 nn 表示输入字符串的长度，
对于一半左右的数据（即约一半），满足条件的情况是在 n 不超过 2\times 1e^{+} 的情况下成立；而对于全部的数据，则要求 n 不超过 2\times 1e^{+}. 样例输入如下：
输入：
()()()
输出：
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;
}