概述
第1题 录制节目
题目描述
电视里将要播放 n n n 个节目,第 i i i 个节目从时刻 s i s_i si 开始,到 t i t_i ti 结束,没有回放。小爱有两台录像机,利用这两台录像机,小爱最多可以录下多少完整的节目呢?
如果某节目的结束时间等于另一个节目的开始时间,那么这两个节目是可以用一台录像机的。
输入格式
第一行:单个整数
n
n
n
第二行到第
n
+
1
n+1
n+1 行:第
i
+
1
i+1
i+1 行有两个整数
s
i
s_i
si 和
t
i
t_i
ti
输出格式
单个整数:表示最大可以录制的节目数量。
数据范围
对于
30
%
30%
30% 的数据,
n
≤
500
nleq 500
n≤500
对于
60
%
60%
60% 的数据,
n
≤
2000
nleq 2000
n≤2000
对于
100
%
100%
100% 的数据,
1
≤
n
≤
200
,
000
1leq nleq 200,000
1≤n≤200,000,
0
≤
s
i
,
t
i
≤
1
,
000
,
000
,
000
0leq s_i,t_ileq 1,000,000,000
0≤si,ti≤1,000,000,000
样例输入
5
1 5
2 6
8 10
3 9
5 10
样例输出
4
问题分析
类似 活动选择问题
的经典贪心问题。区别就是有两个录像机,算法稍调整一下就好了。
先将所有节目按结束时间排序,用两个变量 endt1, endt2 标记两个录像机录制节目的结束时间。设endt1 <= endt2,节目优先用endt2对应的录像机录制并维护 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 n n 匹马,田忌的马速度分别为 a 1 , a 2 , … , a n a_1,a_2,dots,a_n a1,a2,…,an ,而齐王的马速度分别为 b 1 , b 2 , … , b n b_1,b_2,dots,b_n b1,b2,…,bn 。
田忌与齐王比赛 n n n 轮,双方每轮挑出一匹新马,若田忌的马更快,田忌加一分,若齐王的马更快,田忌减一分,若双方速度一样,分数不变。
齐王永远按照固定的编号顺序挑马,田忌应该采取什么策略才能让自己的得分变得最大?
输入格式
第一行:单个整数
n
n
n
第二行:
n
n
n 个整数
a
1
,
a
2
,
…
,
a
n
a_1,a_2,dots,a_n
a1,a2,…,an
第三行:
n
n
n 个整数
b
1
,
b
2
,
…
,
b
n
b_1,b_2,dots,b_n
b1,b2,…,bn
输出格式
单个整数:表示田忌能够获得的最大分数
数据范围
对于
30
%
30%
30% 的数据,
n
≤
20
nleq 20
n≤20
对于
60
%
60%
60% 的数据,
n
≤
2000
nleq 2000
n≤2000
对于
100
%
100%
100% 的数据,
n
≤
200
,
000
nleq 200,000
n≤200,000
1
≤
a
i
,
b
i
≤
1
,
000
,
000
1leq a_i,b_ileq 1,000,000
1≤ai,bi≤1,000,000
样例输入
3
10 20 30
15 25 35
样例输出:
1
问题分析
贪心:显然最优应该是在 a 数组中选择最大的 k 匹马,与 b 数组中最小的 k 匹马比赛,放弃 n - k 轮比赛。可排序后枚举 k , 打擂台求解。时间复杂度:
O
(
n
log
n
)
O(nlog n)
O(nlogn),会超时。
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 中最慢的马,则用它与 b 中最快的马比。
- 如果 a 中最慢的马与 b 中最慢的马的速度相等,则比较两组中最快的马。如果 a 可以赢 b ,则比较下一组(赢一场),直到找到赢不了的一对快马,用 a 最慢的马与 b 中 最快的马比。
时间复杂度: O ( n log n ) O(n log n) O(nlogn)
#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 n n 个结点的树, 1 1 1 号点为根。每个点都有一个颜色,不同点的颜色可能不同,也可能相同。颜色总数不超过 n n n,编号在 1 1 1 到 n n n 之间。第 i i i 个点的颜色为 c i c_i ci 。请为每个点统计,它的子孙后代中(不包括其本身)有多少点的颜色与它相同。
输入格式
第一行:单个整数表示
n
n
n;
第二行:
n
−
1
n−1
n−1 个整数表示
p
2
p_2
p2 到
p
n
p_n
pn ,
p
i
p_i
pi 表示
i
i
i 号点父亲的编号,保证有
1
≤
p
i
<
i
1leq p_i<i
1≤pi<i
第三行:
n
n
n 个整数表示
c
1
c_1
c1 到
c
n
c_n
cn ,
c
i
c_i
ci 表示
i
i
i 号点的颜色,保证有
1
≤
c
i
≤
n
1leq c_ileq n
1≤ci≤n。
输出格式
共 1 1 1 行:表示第 i i i 个点的子孙后代中有多少点的颜色与它相同。
数据范围
对于
30
%
30%
30% 的数据,
n
≤
200
nleq 200
n≤200;
对于
60
%
60%
60% 的数据,
n
≤
5000
nleq 5000
n≤5000;
对于
100
%
100%
100% 的数据,
1
≤
n
≤
200
,
000
1leq nleq 200,000
1≤n≤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 点为根的子树上有多少与 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;
}
最后
以上就是妩媚棉花糖为你收集整理的上海市计算机学会2022年10月月赛乙组试题第1题 录制节目第2题 算式求值(二)第3题 田忌赛马第4题 树的颜色的全部内容,希望文章能够帮你解决上海市计算机学会2022年10月月赛乙组试题第1题 录制节目第2题 算式求值(二)第3题 田忌赛马第4题 树的颜色所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复