2020-CSP 模拟赛1 赛后题解

wen 2020-10-24 19:55:58 2020-10-24 19:58:16

很遗憾,本次比赛只有 dingmohan 一人参加 (有些人估计是英文看不懂),得分为200。本来打算Rated的,但由于人数过少就不计算积分了。这场比赛我觉得难度不算很大,除T1外其他题比去年的CSP略简单(2019年CSP第一题估计是历年来最水的一次),只要编程能力还可以,得到200分还是很容易的。为了起到提升同学们编程能力的效果,良心的出题人将每题的数据设成多组,防止无意义骗分。

T1: Contest Ranking (contest)

题目描述
John老师喜欢让学生考试,一共有 n 名学生,考试前每个人有一个分数 a_i 。John认为每个学生的排名值应该是 b_i =1+比他(她)分数高的学生数。由于学生较多,现在帮助John老师计算一下,考试后所有学生的排名值。

输入格式
第一行为正整数 t(≤10) ,表示数据组数;每组数据中,第一行为正整数 n(≤10000)
第二行为以空格隔开的 n 个分数 a_i(0<ai≤n)

输出格式
对于每组数据,输出这场考试之后的排名分值,仍然按照输入顺序。

分析
这题其实就一个模拟+结构体排序,需要注意的是这题 n 的数据范围 \leq 10000 ,所以 O(n^2) 会超时。
考虑到这是第一题,所以我给的数据 O(n^2) 还是可以得到70pts的。

下面是 O(n^2) 的代码 (70pts):

Time Limit Exceeded

result _58943.png

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[10005],b[10005];
int main() {
	freopen("contest.in","r",stdin);
	freopen("contest.out","w",stdout);
	int t;
	cin>>t;
	while(t--) {
		int n;
		cin>>n;
		for(int i=1; i<=n; i++) {
			cin>>a[i];
		}
		for(int i=1; i<=n; i++) {
			int score_up=0;
			for(int j=1; j<=n; j++) {
				if(a[j]>a[i]) {
					score_up++;
				}
			}
			b[i]=score_up+1;
		}
		for(int i=1; i<=n; i++) {
			cout<<b[i]<<" ";
		}
		cout<<endl;
	}
	return 0;
}

这是AC的代码 (100pts) :

Accepted

result _58946.png

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10005;
struct Node {
	int v, id, rk;
} a[N];
bool cmpv(Node x, Node y) {
	return x.v > y.v;
} //按分值降序排列
bool cmpid(Node x, Node y) {
	return x.id < y.id;
} //再按id升序排列
void in(int &x) {
	char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	for (x=0; c>='0' && c<='9'; c=getchar())
		x=x*10+c-'0';
}
int main() {
	freopen("contest.in", "r", stdin);
	freopen("contest.out", "w", stdout);
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (int i=0; i<n; i++) {
			in(a[i].v);//scanf("%d", &a[i].v);
			a[i].id=i;
		}
		sort(a, a+n, cmpv);
		int cnt=2;
		a[0].rk=1;
		for (int i=1; i<n; ++i) {
			if (a[i].v < a[i-1].v)
				a[i].rk=cnt++;
			else {
				a[i].rk=a[i-1].rk;
				cnt++;
			}
		}
		sort(a, a+n, cmpid);
		for (int i=0; i<n; ++i)
			printf("%d ", a[i].rk);
		printf("\n");
	}
	return 0;
}

T2: Lost number (wild)

题目描述
小强写了一个十进制数 X ,但有些字迹已经模糊不清(我们以 ? 代替),现在给定另一个相同位数的十进制数 Y ,他想知道有多少种可能使得 X>Y

输入格式
第一行为正整数 t(≤100) ,表示数据组数;每组数据中,第一行为一个16位以内的十进制数 X ,当中有若干个 ?
第二行为一个相同位数的十进制数 Y

输出格式
输出 X>Y 的可能数。

分析
这是一道模拟题,首先统计 A ? 的格式,之后对于 s_i (十进制数字 A 的第 i 位) 和 v_i (十进制数字 B 的第 i 位),我们分4种情况讨论,分别是:?,<,>,=

  • ?: 加上之前种数
  • <: 直接退出
  • >: 加上当前种数,退出
  • =: 继续

这是AC的代码 (100pts) :

Accepted

Result _58968.png

#include <cstdio>
#include <cstring>
typedef long long ll;
ll p10[18]= {1};
int main() {
	freopen("wild.in","r",stdin);
	freopen("wild.out","w",stdout);
	for (int i=1; i<18; i++)
		p10[i]=p10[i-1]*10;
	int t;
	scanf("%d", &t);
	while (t--) {
		char s[20], v[20];
		scanf("%s", s);
		scanf("%s", v);
		int n=strlen(s), w=0;
		for (int i=0; i<n; i++)
			if (s[i]=='?') w++;//统计?个数
		ll ans=0ll;
		for (int i=0; i<n; i++)//分四种情况:
			if (s[i]=='?')     //1、?
				ans+=('9'-v[i])*p10[--w];
			else if (s[i]<v[i])//2、<
				break;
			else if (s[i]>v[i]) { //3、>
				ans+=p10[w];
				break;
			}                   //4、相等,继续
		printf("%lld\n", ans);
	}
	return 0;
}

T3: Number of common subintervals (common)

题目描述
\text{[0,n]} 中给出区间集合 A B ,分别包含 x 个区间和 y 个区间,求出它们长度为 m 的公共子区间个数。注意,这里符合条件的公共子区间有 m 个点(包含起点和终点),其长度实际上是 m-1 ,且允许重叠,具体参看样例。

输入格式
第一行为正整数 t(≤10) ,表示数据组数;
每组数据中,第一行为正整数 n , m , x , y
接下来 x 行,每行两个正整数 s_i , e_i ,表示 x 个子区间的起点和终点;
接下来 y 行,每行两个正整数 s_j , e_j 表示 y 个子区间的起点和终点。其中, m≤n≤10^9 , x,y≤10000 , s_i≤e_i≤n , s_j≤e_j≤n
数据保证 x 个子区间互相不交叉, y 个子区间互相不交叉。

输出格式
对于每组数据,输出符合条件的公共子区间个数。

分析
先看样例解释:在样例1中,3个子区间为 \{1,3\} \{10,10\} \{5,8\} ,2个子区间为 \{10,10\} \{1,8\} ;它们长度为3的公共子区间分别是 \{1,3\} \{5,7\} \{6,8\} ,所以答案是3。
这是模拟题,先求出公共子区间,求长度为 m 的子区间个数即可。
像求公共子区间这类模板代码可以自行到OJ题库或Internet去找,这里不再阐述做法。

这是AC的代码 (100pts) :

Accepted

Result _58975.png

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10005;
struct Node {
	int st, ed;
} a[N], b[N];
bool cmp(Node p, Node q) {
	return p.st < q.st;
}
void in(int &x) {
	char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	for (x=0; c>='0' && c<='9'; c=getchar())
		x=x*10+c-'0';
}
int main() {
	freopen("common.in", "r", stdin);
	freopen("common.out", "w", stdout);
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, m, x, y;
		scanf("%d %d %d %d", &n, &m, &x, &y);
		m--;
		for (int i=0; i<x; i++)
			in(a[i].st), in(a[i].ed);
		for (int i=0; i<y; i++)
			in(b[i].st), in(b[i].ed);
		sort(a, a+x, cmp);
		sort(b, b+y, cmp);
		int ans=0, i=0, j=0;
		while (i<x && j<y) {
			if (b[j].st > a[i].ed) {
				i++;
				continue;
			}
			if (a[i].st > b[j].ed) {
				j++;
				continue;
			}
			int st=max(b[j].st, a[i].st);
			int ed=min(b[j].ed, a[i].ed); //求出公共子区间
			if (ed-st+1>m) ans+=ed-st+1-m;//再求长度为m的子区间个数
			if (a[i].ed < b[j].ed) i++;
			else if (a[i].ed == b[j].ed) i++, j++;
			else j++;
		}
		printf("%d\n", ans);
	}
	return 0;
}

T4: Maximum profit (profit)

题目描述
n 个火车站,某连锁饭店要在火车站开饭店,但政府不允许它同时开在两个相连接的火车站,任意两个火车站有且只有一条路径。现在已知在每个火车站开饭店的利润,求这个连锁饭店的最大利润。

输入格式
第一行为正整数 t(≤5) ,表示数据组数;
每组数据中,第一行为正整数 n(≤10^5) ,表示火车站个数,编号从1到 n
接下来 n-1 行,每行两个正整数 a , b ( a,b≤n ),分别表示 a b 火车站之间有一条直达路径,最后一行是 n 个正整数 w_i ( ≤10^4 ),分别表示在每个火车站开饭店的利润。

输出格式
输出最大利润。

分析
算法树形DP,参考做法:深度优先搜索+链式前向星,详细见代码。

知识点回顾:图论之链式前向星

struct Edge {
	int from,to,dis;//next下一条边的编号,to这条边到达的点,dis这条边的长度
} edge[maxm];
int head[maxm],num_edge,n,m,u,v,d;
void add_edge(int from,int to ,int dis) { //添加一条从from到to的距离为dis的单向边
	edge[++num_edge].from=head[from];
	edge[num_edge].to=to;
	edge[num_edge].dis=dis;
	head[from]=num_edge;
}
int main() {
	num_edge=0;
	cin>>n>>m;
	for(i=1--m) {
		cin>>u>>v>>d;
		add_edge(u,v,d);
	}
	for(int i=head[1]; i; i=edge[i].from) {
		u=edge[i].to;
	}
}

其他图论模板代码可参考我的这篇博客或自行上网搜索。

下面是本题的AC代码 (100pts) :

Accepted

Result _58975.png

#include <cstdio>
#include <cstring>
const int N=100010;
struct Edge {
	int v, next;
} edge[2*N]; //边集数组
struct Head {
	int first, w;
} head[N];
int pos, ans, n, f[N], g[N];
bool vis[N];
inline int mx(int a, int b) {
	return a>b ? a : b;
}
void in(int &s) {
	char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	for (s=0; c>='0' && c<='9'; c=getchar())
		s=s*10+c-'0';
}
void ins(int x, int y) {
	pos++;
	edge[pos].v=y;
	edge[pos].next=head[x].first;
	head[x].first=pos;
}
void dfs(int r) {
	vis[r]=1;
	f[r]=head[r].w, g[r]=0;
	for (int k=head[r].first; k; k=edge[k].next) {
		int v=edge[k].v;
		if (!vis[v]) {
			dfs(v);
			f[r]+=g[v];
			g[r]+=mx(f[v], g[v]);
		}
	}
	ans=mx(ans, mx(f[r], g[r]));
}
int main() {
	freopen("profit.in", "r", stdin);
	freopen("profit.out", "w", stdout);
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		memset(vis, 0, sizeof(vis));
		memset(head, 0, sizeof(head));
		pos=0;
		ans=-1;
		int x, y;
		for (int i=1; i<n; i++) {
			in(x), in(y); //scanf("%d %d", &x, &y);
			ins(x, y);
			ins(y, x);
		}
		for (int i=1; i<=n; i++)
			scanf("%d", &head[i].w);
		dfs(1);
		printf("%d\n", ans);
	}
	return 0;
}
  • Solution Created By: wen
  • Created Date:2020-10-24

共 3 条回复

wl

+1

wen

前排支持

cookiebus

前排支持