上海市计算机学会月赛 2022年7月月赛丙组
上海市计算机学会月赛 2022年7月月赛丙组
-
- 水仙花指数
- 因数之和
- 观光电梯
- 匹配括号（三）
- 打印六芒星
本文仅供学术探讨
水仙花指数
内存占用阈值设定为256 MB（256 \text{ Mb}），时间预算限定为1秒（1 \text{ s}）。详细说明如下：将一个正整数的各位十进制数字分别取立方后相加所得之和定义为其水仙花指数。对于给定的整数值 n（n \in \mathbb{Z}^+），请计算其相应的水仙花指数。
例如 n=1294时，立方数之和为 1^3+2^3+9^3+4^3=1+8+729+64=802。
输入采用固定格式
指定一个整数值来表示 n
输出设置为固定格式
指定一个整数值来表示 n 的水仙花指数
数值范围限定在 1 到 1 万亿之间
示例中当输入值为 153时 程序应输出 water narcissus exponent
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 11;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int len;
long long sum = 0;
char n[MAXN];
cin >> n;
len = strlen(n);
for (int i = 0; i < len; ++i) {
int x;
x = int(n[i]) - '0';
sum += x * x * x;
}
cout << sum;
return 0;
}因数之和
内存占用：256 MB运行时长：1秒
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
long long n, ans = 0;
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
ans += (n / i) * i;
printf("%lld", ans);
return 0;
}观光电梯
内存上限: 256 Mb
运行时长: 1000 ms
题目描述
课余时间里, 同学们自发组织起来乘坐观光电梯欣赏自然风光. 每趟电梯最多可载客4人. 班里被分成了若干小组, 第i个小组共有a_i名成员, 每组成员人数均不超过4人.
因为每个学生都追求与自己的组员在同一时间搭乘电梯，在同一小组中成员无法被分配到两个不同的时间段使用电梯，请协助小爱老师计算如何安排乘坐观光电梯的顺序以使学生们能够在最少次数内都能体验到观光电梯的服务。
输入格式
输入共一行：第一行，若干个正整数a_1,a_2,...分别表示每个组的人数
输出格式
输出共一行，表示学生都乘坐到观光电梯的最少次数。
数据范围
假设学生组数为n
在本题中
说明
分析
#include <iostream>
#include <cstring>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, a[5], minn, ans = 0;
memset(a, 0, sizeof(a)); // 一定要清零啊
while(cin >> n) {
++a[n];
}
ans += a[4];
minn = min(a[1], a[3]); // 组少的就是最大能坐一个电梯的
ans += minn;
a[1] -= minn;
a[3] -= minn;
ans += a[2] / 2;
a[2] %= 2;
if(a[3] == 0)
ans += (a[1] + a[2] * 2 + 3) / 4; //注意要向上取
else
ans += a[2] + a[3];
cout << ans;
return 0;
}匹配括号（三）
内存占用上限设定为256 Mb；运行时间规定为1秒；该系统程序的任务描述规定如下：当且仅当该字符序列仅包含 ( 和 ) 这两种字符时；它被认为是有效的括号匹配结构
空字符串被视为符合规范；
假设一个有效的括号序列s存在，则包围它的(s)同样有效；
若两个独立的有效括号序列分别为s和t，则它们按顺序连接形成的st同样有效。
对于给定整数n，请生成所有满足条件的有效括号组合，并将结果按字典顺序排列（若结果数量超过1,000项，则仅列出前1,000项）。
输入格式
单个整数：表示 n
多行：每一行表示由n对括号组成的所有合法配对序列，并按字典顺序排列。当数量超过1000时，则只输出前1000个序列。
数据范围
1≤n≤50
样例数据
输入:
3
输出:
((()))
(()())
(())()
()(())
()()()
分析:
首先括号数量一定是一致的，直接搜索，如果等于n了就下一轮，同样数目的时候加’('(永远是左括号先的)，左满足了就加右，依次搜索。
#include <cstdio>
#include <iostream>
using namespace std;
int n, cnt;
char c[110];
void dfs(int l, int r) {
if(cnt >= 1000)
return;
if(l == n && r == n) {
++cnt;
printf("%s\n", c);
return;
} else if(l == r) {
c[l + r] = '(';
dfs(l + 1, r);
} else if(l == n) {
c[l + r] = ')';
dfs(l, r + 1);
} else {
c[l + r] = '(';
dfs(l + 1, r);
c[l + r] = ')';
dfs(l, r + 1);
}
}
int main() {
scanf("%d", &n);
c[2 * n] = '\0';
dfs(0, 0);
return 0;
}打印六芒星
内存占用：256 MB；时间限制：1秒
问题陈述
基于输入整数 n 的值，请生成一个具有 n 层的六芒星图形
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *输入格式
单个整数：表示 n。
输出格式
一个六芒星图案。
数据范围
2≤n≤50
样例数据
输入:
4
输出:
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *分析:
找规律，先打印三角形的尖，再打印身体。
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
// 尖
for(int i = 1; i <= 3 * n - 3; ++i)
cout << " ";
cout << "*" << endl;
// 身体
for(int i = 2; i <= n - 1; ++i) {
for(int j = 1; j <= 3 * n - 2 - i; ++j)
cout << " ";
cout << "*";
for(int j = 1; j <= 2 * i - 3; ++j)
cout << " ";
cout << "*" << endl;
}
// 合在一起的边
for(int i = 1; i <= 3 * n - 3; ++i)
cout << "* ";
cout << "*" << endl;
// 两个三角形的身体
for(int i = 1; i <= n - 2; ++i) {
for(int j = 1; j <= i; ++j)
cout << " ";
cout << "*";
for(int j = 1; j <= 2 * (n - 1 - i) - 1; ++j)
cout << " ";
cout << "*";
for(int j = 1; j <= 2 * n - 3 + 2 * i; ++j)
cout << " ";
cout << "*";
for(int j = 1; j <= 2 * (n - 1 - i) - 1; ++j)
cout << " ";
cout << "*" << endl;
}
for(int i = 1; i <= n - 1; ++i)
cout << " ";
cout << "*";
for(int i = 1; i <= 4 * n - 5; ++i)
cout << " ";
cout << "*" << endl;
for(int i = n - 2; i >= 1; --i) {
for(int j = 1; j <= i; ++j)
cout << " ";
cout << "*";
for(int j = 1; j <= 2 * (n - 1 - i) - 1; ++j)
cout << " ";
cout << "*";
for(int j = 1; j <= 2 * n - 3 + 2 * i; ++j)
cout << " ";
cout << "*";
for(int j = 1; j <= 2 * (n - 1 - i) - 1; ++j)
cout << " ";
cout << "*" << endl;
}
for(int i = 1; i <= 3 * n - 3; ++i)
cout << "* ";
cout << "*" << endl;
for(int i = n - 1; i >= 2; --i) {
for(int j = 1; j <= 3 * n - 2 - i; ++j)
cout << " ";
cout << "*";
for(int j = 1; j <= 2 * i - 3; ++j)
cout << " ";
cout << "*" << endl;
}
for(int i = 1; i <= 3 * n - 3; ++i)
cout << " ";
cout << "*" << endl;
return 0;
}