我是靠谱客的博主 妩媚棉花糖,最近开发中收集的这篇文章主要介绍上海市计算机学会2022年10月月赛乙组试题第1题 录制节目第2题 算式求值(二)第3题 田忌赛马第4题 树的颜色,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

第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 n500
对于 60 % 60% 60% 的数据, n ≤ 2000 nleq 2000 n2000
对于 100 % 100% 100% 的数据, 1 ≤ n ≤ 200 , 000 1leq nleq 200,000 1n200,000, 0 ≤ s i , t i ≤ 1 , 000 , 000 , 000 0leq s_i,t_ileq 1,000,000,000 0si,ti1,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 n20
对于 60 % 60% 60% 的数据, n ≤ 2000 nleq 2000 n2000
对于 100 % 100% 100% 的数据, n ≤ 200 , 000 nleq 200,000 n200,000
1 ≤ a i , b i ≤ 1 , 000 , 000 1leq a_i,b_ileq 1,000,000 1ai,bi1,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 n1 个整数表示 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 1pi<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 1cin

输出格式

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

数据范围

对于 30 % 30% 30% 的数据, n ≤ 200 nleq 200 n200
对于 60 % 60% 60% 的数据, n ≤ 5000 nleq 5000 n5000
对于 100 % 100% 100% 的数据, 1 ≤ n ≤ 200 , 000 1leq nleq 200,000 1n200,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题 树的颜色所遇到的程序开发问题。

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(66)

评论列表共有 0 条评论

立即
投稿
返回
顶部