上海市计算机学会月赛 2022年4月月赛丙组
上海市青少年算法竞赛月赛2022年4月月赛丙组
-
-
T1 闰年的判定
-
T2 打印栅格
-
T3 匹配括号（一）
-
-
- 非栈做法
-
-
栈做法
-
T4 调整序列
-
T5 调整序列
-
T1 闰年的判定
内存限制: 256 Mb 时间限制: 1000 ms
请判断给定的正整数 y 所代表的那一年是否是闰年。需要注意的是，在这个体系中我们称分为普通闰年和平世纪闰 year two types of leap years.
- 普通闰年的年份是 4 的倍数，但不能是 100 的倍数；
- 世纪闰年的年份是 400 的倍数。
输入格式
单个整数：表示 y。
输出格式
若是闰年，输出 Leap year；
若不是闰年，输出 Common year；
数据范围
- 1≤y≤10000
样例数据
输入:
2020
输出:
Leap year
输入:
1900
输出:
Common year
输入:
2000
输出:
Leap year
算法分析:
直接复制要求，依瓢画葫芦
#include <iostream>
using namespace std;
long long y;
int main()
{
cin.tie(0); // cin速度可以和printf一样了
cin >> y;
if (y % 400 == 0)
cout << "Leap year";
else {
if (y % 4 == 0 && y % 100 != 0)
cout << "Leap year";
else
cout << "Common year";
}
return 0;
}T2 打印栅格
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
给定两个整数 n 和 m 请请求生成一个由n行m列单元格组成的网格结构的具体说明如下
例如当n=2且m=3时应当输出
具体来说
这样的网格将包含n \times m个单元格并以特定的方式排列组合以满足需求
+-+-+-+
||||
+-+-+-+
||||
+-+-+-+输入格式
两个整数：表示 n 与 m。
输出格式
根据题意输出规模为 n×m 的栅格网络。
数据范围
- 1≤n,m≤100
样例数据
输入:
2 3
输出:
+-+-+-+
||||
+-+-+-+
||||
+-+-+-+输入:
4 5
输出:
+-+-+-+-+-+
||||||
+-+-+-+-+-+
||||||
+-+-+-+-+-+
||||||
+-+-+-+-+-+
||||||
+-+-+-+-+-+算法分析
根据样例数据，观察’+ -‘和’| '的规律
#include <iostream>
using namespace std;
int n, m;
int main()
{
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n * 2 + 1 ; ++i) {
if (i % 2 == 1) {
for (int j = 1; j <= m ; ++j) {
cout << "+" << "-"; // 加减号的规律
}
cout << "+" << endl;
} else {
for (int j = 1; j <= m + 1 ; ++j) {
cout << "| "; // 有一个空格不要漏了
}
cout << endl; // 换行
}
}
return 0;
}T3 匹配括号（一）
内存占用限制为：256 MB 时间上限设定为：1秒
题目描述
请确定一个仅包含左右括号的序列，请计算最少需要删除多少个括号方能使其成为一个匹配的序列。具体来说，请根据以下规则判断字符串是否匹配：
- 单独的一个左括号'('或右括号')'无法构成匹配
- 单独一对连续的左右括号'()'即视为成功匹配
- 当多个连续左括号被删除后才可形成有效配对
- 左右配对必须按照顺序出现
空序列是匹配的；
如果括号序列 s 是匹配的，那么 (s) 也是匹配的；
如果括号序列 s 与 t 是匹配的，那么 st 也是匹配的。输入格式
单个字符串：表示输入的序列。
单个整数：即表示为最少需删除多少个括号才能使得输入序列成为一个匹配序列
数据范围
- 设 n 表示输入序列的长度
- 对于 50% 的数据，1≤n≤1,000；
- 对于 100% 的数据，1≤n≤1,000,000；
样例数据
输入:
( ) ( )
输出:
0
说明:
已经是正确匹配
输入:
( ( )
输出:
1
说明:
缺少一个正确的左括号
输入:
) (
输出:
2
说明:
需要全部删除
算法分析:
可以用栈结构，不过对于这一题来说麻烦了.我们只需要设一个变量判断左括号，是的话++z，不是就判断左括号是否大于零，大于就删除一个左括号(–z)，然后总数+2.
非栈做法
#include <iostream>
#include <string>
using namespace std;
int z, cnt;
string s;
int main() {
cin.tie(0);
cin >> s;
for (int i = 0 ; i < s.length(); ++i) {
if (s[i] == '(')
++z; // 左括号
else if (z) // 左括号数量>0
--z, cnt += 2; //ans总数+2(一对)
}
cout << z - cnt;
return 0;
}栈做法
#include<iostream>
#include<string>
#include<stack>
using namespace std;
stack<char> z, y; // 左右括号
string s;
int main() {
cin.tie(0);
cin >> s;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '(')
z.push(s[i]); // 左括号进栈z
if (s[i] == ')')
y.push(s[i]); //右括号就进栈y
if (!z.empty() && !y.empty()) {
if (s[i] == ')' && z.top() == '(') {
z.pop();
y.pop(); // 匹配就删一对括号
}
}
}
cout << z.size() + y.size();
return 0;
}T4 调整序列
内存限制: 256 Mb 时间限制: 1000 ms
给定一个整数序列 a_1,a_2,\dots,a_n 小爱必须修改其中某些数字使其成为一个连续递增的整数序列 即每一个数字都比前一个大 1
若某个数字a被替换成a',则将其转换代价定义为\vert a-a'\vert.确定一种转换方法,使其总和最小化,并计算该最小值.
输入格式
第一行：单个整数 n，表示数列长度；
第二行：n 个整数，表示 a_1,a_2,\dots,a_n
输出格式
单个整数：表示最小的修改工作量。
数据范围
- 对于 30% 的数据，1≤n≤20，1≤a_i≤20；
- 对于 60% 的数据，1≤n≤5000，1≤a_i≤5000；
- 对于 100% 的数据，1≤n≤500000，-10^{9} ≤a_i≤10^{9}
样例数据
输入:
5
2 3 3 3 3输出:
5
说明:
改成1 2 3 4 5
输入:
5
-3 3 0 2 4输出:
7
说明:
改成 -1 0 1 2 3
算法分析 在解题过程中有一定的挑战性。这道题目采用了排序后取中间值的方法来确定数值大小（而不是计算平均值），容易忽视使用long long类型变量的情况（我确实忽略了这一点）。
#include <iostream>
#include <algorithm> // 排序包含
using namespace std;
long long n, sum = 0, a[500001];
int main() {
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i], a[i] -= i;
}
sort(a + 1, a + n + 1); // 排序
for (int i = 1; i <= n; ++i) {
// 中位数要+1，不然基数个会偏移一位
sum += abs(a[i] - a[n / 2 + 1]);
}
cout << sum;
return 0;
}T5 调整序列
内存限制: 256 Mb 时间限制: 1000 ms
设有循环排列a_1,a_2,\dots,a_n长度为n，请从这些数字中选择一个独立集合使其所选元素之和最大化。\n\n其中所谓的循环排列是指考虑相邻关系时将首尾视为相连的情况。\n所谓的独立集合即为被选元素在圆周上不能直接相邻的情况
输入格式
第一行：单个整数表示 n。
第二行：n 个整数表示 a_1,a_2,\dots,a_n。
输出格式
单个整数：表示独立的数字之和的最大值。
数据范围
- 对于 30% 的数据，1≤n≤20；
- 对于 60% 的数据，1≤n≤5000；
- 对于 100% 的数据，1≤n≤500,000，
- 1≤a_i≤1,000,000。
样例数据
输入:
5
1 1 1 1 1输出:
2
输入:
6
100 1 1 100 1 1输出:
200
说明:
这个例子告诉我们最优独立集不一定是最大独立集
算法分析:
相对简单的动态规划问题（另一种常见的方法是记忆化搜索）。不过这里暂时不讨论将dp转换为两个dfs函数的方法（一种常见的做法是在递归过程中分别处理头和尾的情况）。
#include <iostream>
using namespace std;
long long n, dp1[500005], dp2[500005], a[500005];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
if (n == 1) {
// 剪枝
cout << a[1];
return 0;
}
//保留尾部，1不能要
dp1[0] = dp1[1] = 0;
for (int i = 2; i <= n; i++) {
//是平移还是间隔的位置+自己
dp1[i] = max(dp1[i - 1], dp1[i - 2] + a[i]);
}
// 保留最后一个
dp2[1] = a[1];
for (int i = 2; i <= n - 1; i++) {
dp2[i] = max(dp2[i - 1], dp2[i - 2] + a[i]);
}
cout << max(dp1[n], dp2[n - 1]);
return 0;
}