上海市计算机学会2022年10月月赛乙组试题
第1题 录制节目
题目描述
电视里即将播放n个节目。每个第i个节目从时间点s_i开始播放，在t_i时刻结束播放，并且没有回放。小爱拥有两台摄像机，并希望通过这两台摄像机尽可能多地录制完整且不重叠的节目。
当一节目在某一刻结束时点与另一节目在同一刻开始播放时，则这两项内容可依时无缝衔接并存于同一台录影设备之中
输入格式
第一行：单个整数 n
第二行到第 n+1 行：第 i+1 行有两个整数 s_i 和 t_i
输出格式
单个整数：表示最大可以录制的节目数量。
数据范围
对于 30\% 的数据，n\leq 500
对于 60\% 的数据，n\leq 2000
对于 100\% 的数据，1\leq n\leq 200,000,0\leq s_i,t_i\leq 1,000,000,000
样例输入
5
1 5
2 6
8 10
3 9
5 10
样例输出
4
问题分析
类似于经典的活动选择问题的贪心策略。不同之处在于这里使用了两台摄像机来同时记录多个不重叠的节目，并且算法稍作改动即可实现高效的节目安排。首先将所有节目按结束时间排序以便后续处理会更加高效地进行节目安排。然后分别用两个变量 endt1 和 endt2 来记录两台摄像机所录制节目结束的时间点，并保持 endt1 始终小于等于 endt2 以确保合理利用摄像机资源。对于每一个即将播放的节目我们比较其与当前两台摄像机最后一个播放结束时间的关系：如果该节目的开始时间晚于当前两台摄像机中较晚的那个结束时间则优先选择使用该摄像机并更新相应的结束时间记录；如果两个摄像机当前的最大播放截止时间相同则任选其一使用；如果其中一台摄像机已满载则必须切换到另一台继续播放以此类推直到所有节目都被成功安排完毕。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2E5 + 10;
struct nod{
int s, t;
}a[MAXN];
bool cmp(nod p, nod q){
return p.t < q.t;
}
int n, ans = 0;
int main(){
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i].s >> a[i].t;
sort(a, a + n, cmp);
int endt1 = 0, endt2 = 0;
for (int i = 0; i < n; ++i)
if (a[i].s >= endt2){
ans++;
endt2 = a[i].t;
} else if (a[i].s >= endt1){
ans++;
endt1 = a[i].t;
if (endt1 > endt2) swap(endt1, endt2);
}
cout << ans << endl;
return 0;
}第2题 算式求值（二）
题目描述
给定一个由正整数、加号、减号 、小括号构成的表达式，请计算表达式的值。
输入格式
单个字符串，表示输入的算式。
输出格式
单个整数：表示算式的值。
数据范围
数据保证输入的字符串长度不超过 100,000，其中出现的整数不超过 10000。
样例输入1
12-(2+5)
样例输出1
5
样例输入2
12-((5+2)-(4-2))
样例输出2
7
样例输入3
2+(3-4-5)
样例输出3
-4
问题分析
跑一个括号匹配，递归求解。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1E5 + 10;
string s;
int vh[MAXN];
void readp(){
cin >> s;
//求括号匹配
stack<int> stk;
for (int i = 0; i < s.size(); ++i){
if (s[i] == '(')
stk.push(i);
else if (s[i] == ')'){
vh[stk.top()] = i;
stk.pop();
}
}
}
//求解区间[l, r]表达式的值
int cal(int l, int r){
if (s[l] == '(' && r == vh[l]) return cal(l + 1, r - 1);//括号，递归求解
int ans = 0, op = '+', num = 0;
for (int i = l; i <= r; ++i){
if (s[i] <= '9' && s[i] >= '0')
num = num * 10 + s[i] - '0';
else if (s[i] == '(')
num = cal(i, vh[i]), i = vh[i];
else {
if (op == '+') ans += num;
else ans -= num;
num = 0;
op = s[i];
}
}
if (op == '+') ans += num;
else ans -= num;
return ans;
}
int main(){
readp();
cout << cal(0, s.size() - 1) << endl;
return 0;
}第3题 田忌赛马
题目描述
田忌与齐王各有 n 套马匹，在赛跑中它们的速度分别为 a_{1}, a_{2}, \dotsc, a_{n} 和 b_{1}, b_{2}, \dotsc, b_{n}
在与齐王的比赛中进行 n 轮较量，在每一轮中双方各选出一匹新的马匹进行比较。如果田忌选出的马比齐王快，则田忌获得一分；如果齐王选出的马更快，则田忌失去一分；若两者的速度相同，则分数不变
齐王始终按照标准顺序调用马，并且他一直保持着这种固定的模式不变。田忌应该如何制定最佳策略以最大化自己的积分？
输入格式
第一行：单个整数 n
第二行：n 个整数 a_1,a_2,\dots,a_n
第三行：n 个整数 b_1,b_2,\dots,b_n
输出格式
单个整数：表示田忌能够获得的最大分数
数据范围
对于 30\% 的数据，n\leq 20
对于 60\% 的数据，n\leq 2000
对于 100\% 的数据，n\leq 200,000
1\leq a_i,b_i\leq 1,000,000
样例输入
3
10 20 30
15 25 35
样例输出:
1
问题分析
贪心算法：最优策略是通过从A数组选取最高分k名选手与B数组中最低分k名选手进行对决，并舍弃其余n−k轮的比赛。通过排序后遍历所有可能值并逐个测试即可得到结果。该算法的时间复杂度为O(n\log n),计算量较大容易超出时间限制。
定义f(k)表示从A数组中选择最高分k名选手与B数组中最低分k名选手进行对决所能获得的总积分。由于该函数呈现出单峰特性,适合采用模拟退火算法优化以寻找全局最优解
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2E5 + 10;
int n, a[MAXN], b[MAXN];
int cal(int d){
int s = -d;
for (int i = 0; i < n - d; ++i)
if (a[i + d] > b[i]) s++;
else if (a[i + d] < b[i]) s--;
return s;
}
int main(){
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
sort(a, a + n);
sort(b, b + n);
int d = 0, v = cal(0), m = n;
while (m > 0){
for (int i = 1; i <= 10; ++i){
int x = rand() % m, newd, newv;
if (d + x < n){
newd = d + x;
newv = cal(newd);
if (newv >= v){
d = newd;
v = newv;
}
}
if (d - x >= 0){
newd = d - x;
newv = cal(newd);
if (newv >= v){
d = newd;
v = newv;
}
}
}
m = m / 2;
}
cout << v << endl;
return 0;
}认 （网）真 （上）思 （学）考 （习）了一下，这题可以直接用贪心完成。
排序后：
- 若a数组中的最小速度大于b数组中的最小速度，则直接赢得一场比赛。
- 若a队中最小的速度不大于b队中最大的速度，则将该队派出最快的赛手与对方最快的进行对比。
- 若两队最小速度相同，则比较双方的最大值。若a方可以取胜，则依次递进至下一组（立即赢得一场比赛），直至出现某一方无法取胜的情况，则此时将a队派出了最弱赛手对阵b队最强选手。
时间复杂度：O(n \log n)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2E5 + 10;
int n, a[MAXN], b[MAXN];
int main(){
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) cin >> b[i];
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
int ans = 0, la = 1, ra = n, lb = 1, rb = n;
while (la <= ra){
if (a[la] < b[lb]){
la++, rb--, ans--;
} else if (a[la] > b[lb]){
la++, lb++, ans++;
} else {
while (la <= ra && a[ra] > b[rb]){
ra--, rb--, ans++;
}
if (la < ra){
if (a[la] < b[rb]) ans--;
la++, rb--;
} else if (la == ra){
la++, lb++;
}
}
}
cout << ans << endl;
return 0;
}第4题 树的颜色
题目描述
给定一棵包含n个结点的树, 根节点为1号. 每个节点都具有某种颜色, 而可能存在不同或相同的颜色. 最多有n种不同的颜色, 编号范围在1到n. 假设第i个节点的颜色标记为c_i. 请计算每个节点在其子节点中（自身除外）有多少个与之具有相同颜色的节点.
输入格式
仅用一个整数来表示 n
其中每个p_i（i=2,3,...,n）代表i
号节点的父亲节点编号
并且满足条件1 ≤ p_i < i
每个c_i（i=1,2,...,n）代表i
号节点的颜色值
并且颜色值满足1 ≤ c_i ≤ n
输出格式
共 1 行：表示第 i 个点的子孙后代中有多少点的颜色与它相同。
数据范围
对于 30\% 的数据， n\leq 200；
对于 60\% 的数据， n\leq 5000；
对于 100\% 的数据， 1\leq n\leq 200,000。
样例输入
7
1 1 1 2 3 4
1 3 1 3 1 3 1
样例输出
3 0 0 0 0 0 0
问题分析
colfa[i]表示当前搜索路径上与i颜色相关的最近祖先。cnt[i]则存储i点所在子树中与之颜色相同的相关信息。在深度优先搜索过程中不断更新colfa数组，在处理完某个子树后立即增加其cnt[i]值。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2E5 + 10;
int n, col[MAXN], colfa[MAXN], cnt[MAXN];
vector<int> g[MAXN];
void readp(){
cin >> n;
int tmp;
for (int i = 2; i <= n; ++i){
cin >> tmp;
g[tmp].push_back(i);
}
for (int i = 1; i <= n; ++i)
cin >> col[i];
}
void dfs(int k){
cnt[k] = 1;
int tmp = colfa[col[k]];
colfa[col[k]] = k;
for (int i = 0; i < g[k].size(); ++i)
dfs(g[k][i]);
cnt[tmp] += cnt[k];
colfa[col[k]] = tmp;
}
int main(){
readp();
memset(colfa, 0, sizeof(colfa));
memset(cnt, 0, sizeof(cnt));
dfs(1);
for (int i = 1; i <= n; ++i)
cout << cnt[i] - 1 << " ";
cout << endl;
return 0;
}