第1题 录制节目

题目描述

电视里将要播放 $n$ 个节目，第 $i$ 个节目从时刻 $s_i$ 开始，到 $t_i$ 结束，没有回放。小爱有两台录像机，利用这两台录像机，小爱最多可以录下多少完整的节目呢？

如果某节目的结束时间等于另一个节目的开始时间，那么这两个节目是可以用一台录像机的。

输入格式

第一行：单个整数 $n$
第二行到第 $n+1$ 行：第 $i+1$ 行有两个整数 $s_i$ 和 $t_i$

输出格式

单个整数：表示最大可以录制的节目数量。

数据范围

对于 $30\%$ 的数据，$n\le 500$
对于 $60\%$ 的数据，$n\le 2000$
对于 $100\%$ 的数据，$1\le n\le 200,000$,$0\le s_i,t_i\le 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$ 匹马，田忌的马速度分别为 $a_1,a_2,\dots ,a_n$ ，而齐王的马速度分别为 $b_1,b_2,\dots ,b_n$ 。

田忌与齐王比赛 $n$ 轮，双方每轮挑出一匹新马，若田忌的马更快，田忌加一分，若齐王的马更快，田忌减一分，若双方速度一样，分数不变。

齐王永远按照固定的编号顺序挑马，田忌应该采取什么策略才能让自己的得分变得最大？

输入格式

第一行：单个整数 $n$
第二行：$n$ 个整数 $a_1,a_2,\dots ,a_n$
第三行：$n$ 个整数 $b_1,b_2,\dots ,b_n$

输出格式

单个整数：表示田忌能够获得的最大分数

数据范围

对于 $30\%$ 的数据，$n\le 20$
对于 $60\%$ 的数据，$n\le 2000$
对于 $100\%$ 的数据，$n\le 200,000$
$1\le a_i,b_i\le 1,000,000$

样例输入

3
10 20 30
15 25 35

样例输出:

1

问题分析

贪心：显然最优应该是在 a 数组中选择最大的 k 匹马，与 b 数组中最小的 k 匹马比赛，放弃 n - k 轮比赛。可排序后枚举 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 中最慢的马，则用它与 b 中最快的马比。
• 如果 a 中最慢的马与 b 中最慢的马的速度相等，则比较两组中最快的马。如果 a 可以赢 b ,则比较下一组（赢一场），直到找到赢不了的一对快马，用 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$；
第二行：$n-1$ 个整数表示 $p_2$ 到 $p_n$ ，$p_i$ 表示 $i$ 号点父亲的编号，保证有 $1\le p_i<i$
第三行：$n$ 个整数表示 $c_1$ 到 $c_n$ ，$c_i$ 表示 $i$ 号点的颜色，保证有 $1\le c_i\le n$。

输出格式

共 $1$ 行：表示第 $i$ 个点的子孙后代中有多少点的颜色与它相同。

数据范围

对于 $30\%$ 的数据， $n\le 200$；
对于 $60\%$ 的数据， $n\le 5000$；
对于 $100\%$ 的数据， $1\le n\le 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题 树的颜色所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。