首页 › 题库 › GESP编程能力等级认证 › GESP-C++八级

GESP-C++八级 题库

共 270 道题 ,第 14 / 14 页 · 按题型筛选,点「查看答案」核对解析
261 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

手套配对

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有 n 对不同的手套,每对手套由左右各一只组成。

小杨想知道从中取出 m 只手套,m 只手套恰好包含 k 对手套的情况有多少种。

小杨认为两种取出的情况不同,当且仅当两种情况取出的手套中存在不同的手套(同一对手套的左右手也视为不同的手套)。

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,一共一行。

第一行包含三个正整数n,m,k,代表手套数量,取出的手套数和目标对数。

输出格式

对于每组测试数据,输出一个整数,代表可能的情况数量对109+7 取模的结果。

输入样例

2
5 6 2
5 1 5

输出样例

120
0

对于全部数据,保证有1≤t≤105,1≤n≤1000,1≤m≤2×n,1≤k≤n。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3+10;
const int p = 1e9+7;
#define ll long long
ll c[N][N];
ll pw[N];
int n,m,k;
void init(){
	pw[0]=1;
	for(int i=0;i<N;i++){
		if(i)pw[i]=pw[i-1]*2%p;
		for(int j=0;j<=i;j++){
			if(j==0)c[i][j]=1;
			else c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;
		}
	}
}
int main(){
	init();
	int t;
	cin>>t;
	while(t--){
		cin>>n>>m>>k;
		if(m<2*k||m-2*k>n-k){
			cout<<"0\n";
			continue;
		}
		ll ans=c[n][k]*c[n-k][m-2*k]%p;
		ans=ans*pw[m-2*k]%p;
		cout<<ans<<"\n";
	}
}
题目详情
262 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

试题名称:美丽路径

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,节点从 1 到 n 编号,并且每个节点要么是白色,要么是黑色。

对于树上的一条简单路径(不经过重复节点的路径),小杨认为它是美丽的当且仅当路径上相邻节点的颜色均不相同。例如下图,其中节点 1 和节点 4 是黑色,其余节点是白色,路径2−1−3−4 是美丽路径,而 路径2−1−3−5 不是美丽路径(相邻节点 3 和 5 颜色相同)。

对于树上的一条简单路径,小杨认为它的长度是路径包含节点的数量。小杨想知道最长的美丽路径的长度是多少。

输入格式

第一行包含一个正整数 n ,代表节点数量。

第二行包含 n 个整数c1,c2,...,cn,代表每个节点的颜色,如果 ci=0,代表节点 i 为白色,如果ci=1,代表节点 i 为黑色。

之后 n−1 行,每行包含两个正整数ui,vi,代表存在一条连接节点ui和节点vi的边。

输出格式

输出一个整数,代表最长美丽路径的长度。

输入样例1

5
1 0 0 1 0
1 2
3 5
4 3
1 3

输出样例1

4

输入样例2

5
0 0 0 0 0
1 2
2 3
3 4
4 5

输出样例

1

对于全部数据,保证有1≤n≤105,0≤ci≤1,同时保证给出的数据构成一棵树。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int dep[N],vis[N],c[N];
int n,ans;
int dfs(int x,int fa){
	vis[x]=1;
	dep[x]=dep[fa]+1;
	int mx = dep[x];
	vector<int> tmp;
	tmp.push_back(mx);
	for(auto i:g[x]){
		if(i==fa||c[i]==c[x])continue;
		int d = dfs(i,x);
		tmp.push_back(d);
		mx = max(d,mx);
	}
	sort(tmp.begin(),tmp.end());
	int m = tmp.size(),res=1;
	if(m>1){
		res = tmp[m - 1] + tmp[m - 2] - 2 * dep[x] + 1;
	}
	ans=max(ans,res);
	return mx;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>c[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
		dfs(i,0);
		}
	}
	cout<<ans<<"\n";
}

1.定义DP[x][0/1]:x以x为根的,x颜色为(0白1黑)的最长链路节点数量

初始化:DP[x][A[x]]=1 ,DP[x][1-A[x]]=0;

2.定义Fx:穿过x的满足题目要求的最长节点数量,则Fx由以x为端点的最长链和次长链组成。

状态转移方程:

对(父亲x->孩子y A[x]为x的节点颜色)

①若A[x]=0:DP[x][0]=max(DP[x][0],DP[y][1]+1);

②若A[x]=1:DP[x][1]=max(DP[x][1],DP[y][0]+1);

在此基础上,Fx因为由最长和次长组成,因此需要在DP[x]更新前完成更新,因此:

①若A[x]=0

Fx=max(Fx,DP[x][0]+DP[y][1]);

DP[x][0]=max(DP[x][0],DP[y][1]+1);

②若A[x]=1;

Fx=max(Fx,DP[x][1]+DP[y][0]);

DP[x][1]=max(DP[x][1],DP[y][0]+1);

目标状态:Fx

题目详情
263 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

最远点对

题面描述

小杨有一棵包含n个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。

小杨想知道相距最远的一对不同颜色节点的距离是多少。

输入格式

第一行包含一个正整数 n,代表树的节点数。

第二行包含n个非负整数a1,a2,...,an(对于所有的1≤i≤n,均有ai等于0或1),其中如果ai=0,则节点i的颜色为白色;如果ai=1,则节点i的颜色为黑色。

之后n-1行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。

保证输入的树中存在不同颜色的点。

输出格式

输出一个整数,代表相距最远的一对不同颜色节点的距离。


输入样例

5
0 1 0 1 0
1 2
1 3
3 4
3 5

输出样例

3

样例解释

相距最远的不同颜色的一对节点为节点 2 和 5。

数据范围

对于全部数据,保证有1≤n≤105,0≤ai≤1。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int col[N];
int n;
int dep[N],far[N][2];
int ans;
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	far[x][col[x]]=dep[x];
	for(int i:g[x]){
		if(i!=fa){
			dfs(i,x);
			for(int j=0;j<2;j++){
				if(far[x][j]!=-1&&far[i][j^1]!=-1){
					ans = max(ans,far[x][j]-dep[x]+far[i][j^1]-dep[x]);
				}
			}
			for(int j=0;j<2;j++){
				far[x][j]=max(far[x][j],far[i][j]);
			}
		}
	}
	ans = max(ans,far[x][col[x]^1]-dep[x]);
}
int main(){
	int n;
	cin>>n;
	memset(far,-1,sizeof far);
	for(int i=1;i<=n;i++){
		cin>>col[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	cout<<ans<<"\n";
}

每个结点要么黑色要么白色,需要保存结点的颜色信息。选2个颜色不同的点,可以先枚举第1个点和第2个点,求他们的距离,再求最大值。任意2点都是连通的,能够相互访问,能求出最大值。根据数据范围,能得到部分分。另一种思路就是根据树的性质,答案的2个点假设是a和b,路径会经过他们的公共祖先,距离=公共祖先到a的距离+公共祖先到b的距离。每个点视为公共祖先的话,有可能是左孩子的黑色和右孩子的白色组合,也可能是左孩子的白色和右孩子的黑色组成,也可能只在左孩子或者右孩子中。所以,每个结点应该保留2种颜色的最远值。一次深搜即可。每个点访问1次,时间复杂度是O(n)。

题目详情
264 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

空间跳跃

题面描述

小杨在二维空间中有n个水平挡板,并且挡板之间彼此不重叠,其中第i个挡板处于水平高度hi,左右端点分别位于li 与 ri。

小杨可以在挡板上左右移动,当小杨移动到右端点时,如果再向右移动会竖直掉落,从而落到下方第一个挡板上,移动到左端点时同理。小杨在挡板上每移动1个单位长度会耗费 1个单位时间,掉落时每掉落1 个单位高度也会耗费 1个单位时间。

小杨想知道,从第 s个挡板上的左端点出发到第t个挡板需要耗费的最少时间是多少?

注意:可能无法从第 s个挡板到达到第 t个挡板。

输入格式

第一行包含一个正整数n ,代表挡板数量。

第二行包含两个正整数s,t ,含义如题面所示。

之后 n行,每行包含三个正整数li,ri,hi ,代表第 i个挡板的左右端点位置与高度。

输出格式

输出一个整数代表需要耗费的最少时间,如果无法到达则输出 -1。


输入样例

3
3 1
5 6 3
3 5 6
1 4 100000

输出样例

100001

样例范围

耗费时间最少的移动方案为,从第3个挡板左端点移动到右端点,耗费3个单位时间,然后向右移动掉落到第 2个挡板上,耗费 100000-6=99994个单位时间,之后再向右移动1个单位长度,耗费1个单位时间,最后向右移动掉落到第1个挡板上,耗费3个单位时间。共耗费 3+99994+1+3=100001个单位时间。

数据范围

对于全部数据,保证有1≤n≤1000,1≤li≤ri≤105,1≤hi≤105。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4+10;

struct edge {
	int v, w;
	edge() {
	}
	edge(int vv,int ww) {
		v=vv;
		w=ww;
	}
};

struct node {
	int dis, u;
	node () {
	}
	node (int diss,int uu) {
		dis=diss;
		u=uu;
	}
	bool operator>(const node& a) const {
		return dis > a.dis;
	}
};

vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node> > q;
int cnt;
void dijkstra(int s) {
	for (int i=1;i<=cnt;i++)dis[i]=INT_MAX;
	dis[s] = 0;
	q.push(node(0, s));
	while (!q.empty()) {
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto ed : e[u]) {
			int v = ed.v, w = ed.w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push(node(dis[v], v));
			}
		}
	}
}

map<pair<int,int>,int> mp;
vector<int> es[2010];
int l[maxn],r[maxn],h[maxn];
int main() {
	int n;
	cin>>n;
	int s,t;
	cin>>s>>t;
	for (int i=1;i<=n;i++) {
		cin>>l[i]>>r[i]>>h[i];
		mp[make_pair(l[i],h[i])]=i;
		mp[make_pair(r[i],h[i])]=n+i;
		es[i].push_back(i);
		es[i].push_back(n+i);
		e[i].push_back(edge(n+i,r[i]-l[i]));
		e[n+i].push_back(edge(i,r[i]-l[i]));
	}
	cnt=2*n+1;
	for (int i=1;i<=n;i++) {
		int hh = -1,idx = i;
		for (int j=1;j<=n;j++) {
			if(i==j)continue;
			if(l[j]<=l[i]&&l[i]<=r[j]&&h[j]<=h[i]) {
				if(h[j]>hh) {
					hh=h[j];
					idx=j;
				}
			}
		}
		if(hh!=-1) {
			if(!mp[make_pair(l[i],hh)]) {
				mp[make_pair(l[i],hh)]=cnt++;
			}
			int v = mp[make_pair(l[i],hh)];
			e[i].push_back(edge(v,h[i]-hh));
			e[idx].push_back(edge(v,abs(l[i]-l[idx])));
			e[n+idx].push_back(edge(v,abs(l[i]-r[idx])));
			e[v].push_back(edge(idx,abs(l[i]-l[idx])));
			e[v].push_back(edge(n+idx,abs(l[i]-r[idx])));
			es[idx].push_back(v);
		}
		hh = -1,idx = i;
		for (int j=1;j<=n;j++) {
			if(i==j)continue;
			if(l[j]<=r[i]&&r[i]<=r[j]&&h[j]<=h[i]) {
				if(h[j]>hh) {
					hh=h[j];
					idx=j;
				}
			}
		}
		if(hh!=-1) {
			if(!mp[make_pair(r[i],hh)]) {
				mp[make_pair(r[i],hh)]=cnt++;
			}
			int v = mp[make_pair(r[i],hh)];
			e[n+i].push_back(edge(v,h[i]-hh));
			e[idx].push_back(edge(v,abs(r[i]-l[idx])));
			e[n+idx].push_back(edge(v,abs(r[i]-r[idx])));
			e[v].push_back(edge(idx,abs(r[i]-l[idx])));
			e[v].push_back(edge(n+idx,abs(r[i]-r[idx])));
			es[idx].push_back(v);
		}
	}
	dijkstra(s);
	int ans = INT_MAX;
	for (auto i:es[t]) {
		ans=min(ans,dis[i]);
	}
	if(ans!=INT_MAX)cout<<ans<<"\n"; else cout<<"-1\n";
}

发现n的数据范围是1000,求的是从1个挡板到另外1个挡板。注意,掉到目标挡板中的某个位置即可。同时1个挡板左端到右端或者右端到左端算距离,其他挡板的2个端点只要能垂直相交到下一个挡板(中间没有其他挡板阻碍),也算相连。将这些端点和相交点看成结点,相连看成边,整个结构就成为一张图的结构。起点是固定的,终点也是固定的(只要是目标挡板的某个点即可),求的就是最短路径。数据都是正整数,可以用dijkstra算法实现。

难点1在于建图。一个挡板左右算2个结点,要连边;一个挡板的左右两端能够垂直到其他挡板,中间不能有间隔,要连边。

难度2就是dijkstra算法的完成。按照优先队列的模板完成即可。

题目详情
265 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

公倍数问题

问题描述

小 A 写了一个N×M的矩阵A,我们看不到这个矩阵,但我们可以知道,其中第i行第j列的元素Aij是i和j的公倍数(i=1,...,N,j=1,...,M)。现在有K个小朋友,其中第k个小朋友想知道,矩阵A中最多有多少个元素可以是k(k=1,2,...,K)。请你帮助这些小朋友求解。

注意:每位小朋友的答案互不相关,例如,有些位置既可能是x,又可能是y,则它同可以时满足x,y两名小朋友的要求。

方便起见,你只需要输出即可,其中ansk表示第k名小朋友感兴趣的答案。

输入描述

第一行三个正整数N,M,K。

输出描述

输出一行,即。

请注意,这个数可能很大,使用 C++ 语言的选手请酌情使用 long long 等数据类型存储答案。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

2 5 2

样例输出 1

9

样例解释 1

只有A1,1可以是1,其余都不行。

A1,1,A1,2,A2,1,A2,2都可以是2,而其余不行。

因此答案是1×1+2×4=9。

样例输入 2

100 100 100

样例输出 2

185233

数据规模

对于30的测试点,保证N,M,K≤10;

对于60的测试点,保证N,M,K≤500;

对于100的测试点,保证N,M≤105,K≤106。

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;
vector<int> count_divisors(int limit, int num) {
	vector<int> s(num + 1, 0);
	for (int i = 1; i <= limit; ++i) {
		for (int j = i; j <= num; j += i) {
			s[j] += 1;
		}
	}
	return s;
}
int main() {
	int N, M, K;
	cin >> N >> M >> K;
	vector<int> s_N = count_divisors(N, 1000000);
	vector<int> s_M = count_divisors(M, 1000000);
	long long result = 0;
	for (int k = 1; k <= K; ++k) {
		result += (long long)k * s_N[k] * s_M[k];
	}
	cout << result << endl;
	return 0;
}
题目详情
266 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

接竹竿

题面描述

小杨同学想用卡牌玩一种叫做“接竹竿”的游戏。

游戏规则是:每张牌上有一个点数v,将给定的牌依次放入一列牌的末端。若放入之前这列牌中已有与这张牌点数相同的牌,则小杨同学会将这张牌和点数相同的牌之间的所有牌全部取出队列(包括这两张牌本身)。

小杨同学现在有一个长度为n的卡牌序列A,其中每张牌的点数为Ai(1≤i≤n)。小杨同学有q次询问。第i次(1≤i≤q)询问时,小杨同学会给出li,ri,小杨同学想知道如果用下标在[li,ri]的所有卡牌按照下标顺序玩“接竹竿”的游戏,最后队列中剩余的牌数。

输入格式

第一行包含一个正整数T,表示测试数据组数。

对于每组测试数据,第一行包含一个正整数n,表示卡牌序列A的长度。

第二行包含n个正整数A1,A2,...An,,表示卡牌的点数A。

第三行包含一个正整数q,表示询问次数。

接下来q行,每行两个正整数li,ri,表示一组询问。

输出格式

对于每组数据,输出q行。第i行(1≤i≤q)输出一个非负整数,表示第i次询问的答案。


样例输入

1
6
1 2 2 3 1 3
4
1 3
1 6
1 5
5 6


样例输入

1
1
0
2

样例解释

对于第一次询问,小杨同学会按照1,2,2的顺序放置卡牌,在放置最后一张卡牌时,两张点数为2的卡牌会被收走,因此最后队列中只剩余一张点数为1的卡牌。

对于第二次询问,队列变化情况为:

{}→{1}→{1,2}→{1,2,2}→{1}→{1,3}→{1,3,1}→{}→{3}。因此最后队列中只剩余一张点数为3的卡牌。

数据范围

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int a[N];
int nxt[N][30],pos[20];
int main(){
	int t;
	cin>>t;
	while(t--){
	int n;
	cin>>n;
	memset(pos,0,sizeof pos);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		for(int j=0;j<=20;j++)nxt[i][j]=n+1;
	}
	for(int i=n;i>=1;i--){
		if(!pos[a[i]]){
			nxt[a[i]][0]=n+1;
			pos[a[i]]=i;
		}else{
			nxt[i][0]=pos[a[i]];
			pos[a[i]]=i;
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=1;j<=20;j++){
			if(nxt[i][j-1]+1<=n)
			nxt[i][j]=nxt[nxt[i][j-1]+1][j-1];
		}
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		int ii=l;
		int ans=0;
		while(ii<=r){
			while(ii<=r&&nxt[ii][0]>r){
				ii++;
				ans++;
			}
			if(ii>r)break;
			for(int j=20;j>=0;j--){
				if(nxt[ii][j]<=r){
					ii=nxt[ii][j];
					break;
				}
			}
			ii++;
		}
		cout<<ans<<"\n";
	}
	}
}
题目详情
267 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

奖品分配

时间限制:1.0 s

内存限制:128.0 MB

问题描述

班上有N名同学,学号从0到N-1。有 种奖品要分给这些同学,其中,第M种奖品总共有ai个(i=0,1,…,M-1)。巧合的是,奖品的数量不多不少,每位同学都可以恰好分到一个奖品,且最后剩余的奖品不超过1个(即:N≤a0+a1+…+aM-1≤N+1)。

现在,请你求出每个班级礼物分配的方案数,所谓方案,指的是为每位同学都分配一个种类的奖品。只要有一位同学获得了不同种类的奖品,即视为不同的方案。方便起见,你只需要输出方案数对109+7取模后的结果即可。

共有T个班级都面临着奖品分配的问题,你需要依次为他们解答。

输入描述

第一行一个整数T,表示班级数量。

接下来 行,每行若干用单个空格隔开的正整数。首先是两个正整数N,M,接着是M个正整数a0,a1,…,aM-1。

保证N≤a0+a1+…+aM-1≤N+1。

输出描述

输出T行,每行一个整数,表示该班级分配奖品的方案数对109+7取模的结果。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

3
3 2 1 2
3 2 1 3
5 3 3 1 1

样例输出 1

3
4
20

样例解释 1

对于第 1 个班级,学号为0,1,2的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,因此共有3种方案。

对于第 2 个班级,学号为0,1,2的同学可以依次分别获得奖品0,1,1,也可以依次分别获得奖品1,0,1,也可以依次分别获得奖品1,1,0,也可以依次分别获得奖品1,1,1,因此共有4种方案。

对于第 3 个班级,可以把编号为1的奖品分配给5名同学中的任意一名,共有5种方案;再把编号为2的奖品分配给剩余4名同学中的任意一名,共有4种方案;最后给剩余3名同学自然获得0号奖品。因此,方案数为5×4=20。


样例输入 2

5
100 1 100
100 1 101
20 2 12 8
123 4 80 20 21 3
999 5 101 234 499 66 99

样例输出 2

1
1
125970
895031741
307187590

数据规模

对于30%的测试点,保证N≤10。

对于另外30%的测试点,保证M=2。

对于所有测试点,保证N≤1000;保证T≤1000;保证M≤1000。

答案与解析
参考答案
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;
const int N = 1005;
const int mod = 1e9 + 7;
int C[N + 5][N + 5], a[N + 5];
void add(int &a, int b) {
  a += b;
  if (a >= mod)
    a -= mod;
}
void init() {
  C[0][0] = 1;
  for (int i = 1; i <= N; i++) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; j++)
      C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);
  }
}
int main() {
  // freopen("data/10.in", "r", stdin);
  init();
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m, sum = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
      scanf("%d", &a[i]), sum += a[i];

    int ans = 1;
    for (int i = 1; i <= m; i++) {
      ans = 1ll * ans * C[sum][a[i]] % mod;
      sum -= a[i];
    }
    cout << ans << endl;
  }
  return 0;
}
题目详情
268 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

大量的工作沟通

时间限制:2.0 s

内存限制:128.0 MB

问题描述

某公司有N名员工,编号从0至N-1。其中,除了0号员工是老板,其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。

该公司有严格的管理制度,每位员工只能受到本人或直接领导或间接领导的管理。具体来说,规定员工x可以管理员工y,当且仅当x=y,或f=fy,或x可以管理fy。特别地,0号员工老板只能自我管理,无法由其他任何员工管理。

现在,有一些同事要开展合作,他们希望找到一位同事来主持这场合作,这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工,他们希望找到编号最大的员工。你能帮帮他们吗?

输入描述

第一行一个整数N,表示员工的数量。

第二行N-1个用空格隔开的正整数,依次为f1,f2…,fN-1。

第三行一个整数Q,表示共有Q场合作需要安排。

接下来Q行,每行描述一场合作:开头是一个整数m(2≤m≤N),表示参与本次合作的员工数量;接着是m个整数,依次表示参与本次合作的员工编号(保证编号合法且不重复)。

保证公司结构合法,即不存在任意一名员工,其本人是自己的直接或间接领导。

输出描述

输出Q行,每行一个整数,依次为每场合作的主持人选。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

5
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4

样例输出 1

2
2
0

样例解释 1

对于第一场合作,员工3,4有共同领导2,可以主持合作。

对于第二场合作,员工2本人即可以管理所有参与者。

对于第三场合作,只有0号老板才能管理所有员工。


样例输入 2

7
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4

样例输出 2

2
1
1
1
0

数据规模

对于25%的测试点,保证N≤50。

对于50%的测试点,保证N≤300。

对于所有测试点,保证3≤N≤105;保证Q≤100,保证m≤104。

答案与解析
参考答案
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>

using namespace std;
const int N = 100005;
int fa[N], sz[N], dep[N], son[N], tp[N], mxId[N];
int cnt, fir[N], tar[N], nxt[N];
void link(int a, int b) { tar[++cnt] = b, nxt[cnt] = fir[a], fir[a] = cnt; }
void dfs(int x, int mxid) {
  int Mx = 0;
  sz[x] = 1;
  mxId[x] = max(x, mxid);
  for (int i = fir[x]; i; i = nxt[i]) {
    dep[tar[i]] = dep[x] + 1;
    dfs(tar[i], mxId[x]);
    sz[x] += sz[tar[i]];
    if (Mx < sz[tar[i]])
      Mx = sz[son[x] = tar[i]];
  }
}
void gettp(int x) {
  tp[x] = x;
  if (son[fa[x]] == x)
    tp[x] = tp[fa[x]];
  for (int i = fir[x]; i; i = nxt[i])
    gettp(tar[i]);
}
int lca(int x, int y) {
  while (tp[x] != tp[y])
    dep[tp[x]] > dep[tp[y]] ? x = fa[tp[x]] : y = fa[tp[y]];
  return dep[x] < dep[y] ? x : y;
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 2; i <= n; i++)
    scanf("%d", &fa[i]), link(++fa[i], i);
  dfs(1, 1), gettp(1);
  int q;
  scanf("%d", &q);
  while (q--) {
    int m, x, y;
    scanf("%d%d", &m, &x), x++;
    for (int i = 2; i <= m; i++)
      scanf("%d", &y), x = lca(x, ++y);
    cout << mxId[x] - 1 << endl;
  }
  return 0;
}
题目详情
269 简答题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

消息查找

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;
const int C = 2e3 + 5;
const int oo = 1e9;

int n, q;
int r[N], mark[N], pos[N];
int p[C], cnt;
int d[C][C];
int pre[N], suf[N];

int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &r[i]);
        if (r[i])
            mark[i] = mark[r[i]] = 1;
    }

    for (int i = 1; i <= n; i++)
    {
        if (mark[i])
        {
            p[++cnt] = i;
            pos[i] = cnt;
        }
    }

    for (int i = 1; i <= cnt; i++)
    {
        for (int j = 1; j <= i; j++)
            d[i][j] = oo;
        d[i][i] = 0;
        for (int j = i; j > 1; j--)
        {
            d[i][j - 1] = min(d[i][j - 1], d[i][j] + p[j] - p[j - 1]);
            if (r[p[j]])
            {
                int k = pos[r[p[j]]];
                d[i][k] = min(d[i][k], d[i][j] + 1);
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        pre[i] = pre[i - 1];
        if (mark[i])
            pre[i] = i;
    }

    suf[n + 1] = n + 1;
    for (int i = n; i; i--)
    {
        suf[i] = suf[i + 1];
        if (mark[i])
            suf[i] = i;
    }

    while (q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (pre[x] < suf[y])
        {
            printf("%d\n", x - y);
        }
        else
        {
            printf("%d\n", x - pre[x] + d[pos[pre[x]]][pos[suf[y]]] + suf[y] - y);
        }
    }

    return 0;
}
题目详情
270 简答题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

子图最短路

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 105;
const int mod = 1e9;

int n, m;
int f[N][N];
int g[N][N];
int ans;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            f[i][j] = mod;
        f[i][i] = 0;
    }

    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        f[u][v] = min(f[u][v], w);
        f[v][u] = min(f[v][u], w);
    }

    for (int l = 1; l <= n; l++)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                g[i][j] = f[i][j];

        for (int r = l; r <= n; r++)
        {
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    g[i][j] = min(g[i][j], g[i][r] + g[r][j]);

            for (int i = l; i <= r; i++)
                for (int j = i; j <= r; j++)
                    ans = (ans + g[i][j]) % mod;
        }
    }

    printf("%d\n", ans);
    return 0;
}
题目详情