首页 › 题库 › GESP编程能力等级认证 › 综合练习

GESP-C++八级 题库

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

遍历计数

时间限制:1 s,内存限制:512 MB

【问题描述】

给定一棵有 n 个结点的树 T,结点依次以 1、2、……、n 标号。树 T 的深度优先遍历序可由以下过程得到:

(1)选定深度优先遍历的起点 s(1<=s<=n ),当前所在结点即是起点。

(2)若当前结点存在未被遍历的相邻结点 u 则遍历 u,也即令当前所在结点为 u 并重复这一步;否则回溯。

(3)按照遍历结点的顺序依次写下结点编号,即可得到一组深度优先遍历序。

第一步中起点的选择是任意的,并且第二步中遍历相邻结点的顺序是任意的,因此对于同一棵树 T 可能有多组不同的深度优先遍历序。

请你求出树 T 有多少组不同的深度优先遍历序。由于答案可能很大,你只需要求出答案对 10^9 取模之后的结果。

【输入描述】

第一行,一个整数 n,表示树 T 的结点数。

接下来 n - 1 行,每行两个正整数 ui、vi,表示树 T 中的一条连接结点 ui、vi 的边。

【输出描述】

输出一行,一个整数,表示树 的不同的深度优先遍历序数量对 10^9 取模的结果。

【样例输入1】

4
1 2
2 3
3 4

【样例输出1】

6

【样例输入2】

8
1 2
1 3
1 4
2 5
2 6
3 7
3 8

【样例输出2】

112

【数据范围】

对于40%的测试点,保证 1 <= n <= 8。

对于另外20%的测试点,保证给定的树是一条链。

对于所有测试点,保证 1 <= n <= 100000。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9;
int n, deg[N], fac[N];
int pre[N], suf[N], ans;
int main() {
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
    }
    pre[0] = 1;
    for (int i = 1; i <= n; i++)
        pre[i] = 1ll * pre[i - 1] * fac[deg[i] - 1] % mod;
    suf[n + 1] = 1;
    for (int i = n; i; i--)
        suf[i] = 1ll * suf[i + 1] * fac[deg[i] - 1] % mod;
    for (int i = 1; i <= n; i++)
        ans = (ans + 1ll * pre[i - 1] * fac[deg[i]] % mod * suf[i + 1]) % mod;
    cout << ans << endl;
    return 0;
}
题目详情
122 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

上学

时间限制:1 s,内存限制:512 MB

【问题描述】

C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1、2、……、n 标号,边依次以 1、2、……、m 标号。

第 i 条边(1<=i<=m)连接编号为 ui 与 vi 的结点,长度为 li 米。

小 A 的学校坐落在 C 城中编号为 s 的结点。小 A 的同学们共有 q 位,他们想在保证不迟到的前提下,每天尽可能晚地出门上学。但同学们并不会计算从家需要多久才能到学校,于是找到了聪明的小 A。

第 i 位同学(1<=i<=q )告诉小 A,他的家位于编号为 hi 的结点,并且他每秒能行走 1 米。请你帮小 A 计算,每位同学从家出发需要多少秒才能到达学校呢?

【输入描述】

第一行,四个正整数 n、m、s、q,分别表示 C 城的结点数与边数,学校所在的结点编号,以及小 A 同学们的数量。

接下来 m 行,每行三个正整数 ui、vi、li,表示 C 城中的一条无向边。

接下来 q 行,每行一个正整数 hi,表示一位同学的情况。

【输出描述】

共 q 行,对于每位同学,输出一个整数,表示从家出发到学校的最短时间。

【样例输入1】

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

【样例输出1】

4
3
1

【数据范围】

对于 20% 的测试点,保证 q=1。

对于另外 20% 的测试点,保证 1<=n<=500,1<=m<=500  。

对于所有测试点,保证 1<=n<=2×10^5,1<=m<=2×10^5 ,1<=q<=2×10^5 ,1<=ui、vi、hi<=n ,1<=li<=10^6 。

保证给定的图联通。

答案与解析
参考答案
#include <cstdio>
#include <queue>
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
const long long oo = 1e18;
int n, m, s, q;
int h[N], to[E], nx[E], wt[E], et;
int vis[N];
long long d[N];
priority_queue <pair<long long, int>> pq;
void ae(int u, int v, int w) {
    et++;
    to[et] = v;
    nx[et] = h[u];
    wt[et] = w;
    h[u] = et;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &q);
    for (int i = 1; i <= m; i++) {
        int u, v, l;
        scanf("%d%d%d", &u, &v, &l);
        ae(u, v, l);
        ae(v, u, l);
    }
    for (int i = 1; i <= n; i++)
        d[i] = oo;
    d[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        int u = p.second;
        if (vis[u])
            continue;
        vis[u] = 1;
        for (int i = h[u]; i; i = nx[i])
            if (d[u] + wt[i] < d[to[i]]) {
                d[to[i]] = d[u] + wt[i];
                pq.push({-d[to[i]], to[i]});
            }
    }
    while (q--) {
        int p;
        scanf("%d", &p);
        printf("%lld\n", d[p]);
    }
    return 0;
}
题目详情
123 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

割裂

时间限制:1 s,内存限制:512 MB

【问题描述】

小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n。

小杨设置了 a 个好点对 {<u1,v1>、<u2,v2>、……、<ua,va>} 和 1 个坏点对 {<bu,bv>}。一个节点能够被删除,当且仅当:

◆ 删除该节点后对于所有的 i(1<=i<=a),好点对 ui 和 vi 仍然连通;

◆ 删除该节点后坏点对 bu 和 bv 不连通。

如果点对中的任意一个节点被删除,其视为不连通。

小杨想知道,有多少个节点能够被删除。

【输入描述】

第一行包含两个正整数 n、a,含义如题面所示。

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

之后 a 行,每行包含两个正整数 ui、vi,代表一个好点对 <ui,vi>。

最后一行包含两个正整数 bu、bv,代表坏点对 <bu,bv>。

【输出描述】

输出一个正整数,代表能够删除的节点个数。

【样例输入】

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

【样例输出】

2

【数据范围】

对于全部数据,保证有 。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, k;
vector<int> e[N];
int f[N][25], dep[N], g[N], h[N];
void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for(int i = 1; i <= 20; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }
    for(auto v: e[u]) {
        if(v == fa) continue;
        dfs(v, u);
    }
}
int lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    int t = dep[u] - dep[v];
    for(int i = 0; i <= 20; i++) {
        if(t & (1 << i)) u = f[u][i];
    }
    for(int i = 20; i >= 0; i--) {
        if(f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];
    }
    if(u == v) return u;
    return f[u][0];
}
int ans;
void dfs2(int u, int fa) {
    for(auto v: e[u]) {
        if(v == fa) continue;
        dfs2(v, u);
        g[u] += g[v];
        h[u] += h[v];
    }
    if(!g[u] && h[u]) {
        ans++;
    }
}
void solve() {
    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= k; i++) {
        int u, v;
        cin >> u >> v;
        int lc = lca(u, v);
        g[u]++, g[v]++, g[lc]--, g[f[lc][0]]--;
    }
    int u, v;
    cin >> u >> v;
    int lc = lca(u, v);
    h[u]++, h[v]++, h[lc]--, h[f[lc][0]]--;
    dfs2(1, 0);
    cout << ans << '\n';
}
int main() {
    solve();
}
题目详情
124 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

树上移动

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n ,每个节点的颜色要么是白色要么是黑色。小杨可以任意选择节点 s 和节点 t 并从节点 s 出发移动到节点 t ,移动过程中小杨不能够经过重复节点。

小杨希望自己在至多经过 k 个黑色节点的前提下,经过的总节点数尽可能多,请你帮小杨选择经过最多的节点数是多少。

输入格式

第一行包含两个正整数 n,k,代表节点数量和至多经过的黑色节点数。

第二行包含 n 个正整数 a1,a2,...,an,代表节点颜色,如果 ai=0,代表节点颜色为白色,如果 ai=1,代表节点颜色为黑色。

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

输出格式

输出一个正整数,代表最多经过的节点数。

输入样例

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

输入样例

3

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

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
vector<int> g[N];
int a[N];
int n,k;
int ans;
void dfs(int x,int fa,int tot,int le){
	tot+=a[x];
	if(tot>k){
		ans = max(ans,le);
		return;
	}
	le++;
	ans = max(ans,le);
	for(int i:g[x]){
		if(i!=fa){
			dfs(i,x,tot,le);
		}
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[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++){
		dfs(i,0,0,0);
	}
	cout<<ans<<"\n";
}
题目详情
125 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

排队

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小杨所在班级共有 n 位同学,依次以 1,2,...,n 标号。这 n 位同学想排成一行队伍,其中有些同学之间关系非常好,在队伍里需要排在相邻的位置。具体来说,有 m 对这样的关系( m 是一个非负整数)。当 m≥1 时,第 i 对关系 (1≤i≤m) 给出 ai,bi,表示排队时编号为 ai的同学需要排在编号为 bi的同学前面,并且两人在队伍中相邻。

现在小杨想知道总共有多少种排队方式。由于答案可能很大,你只需要求出答案对 109+7 取模的结果。

输入格式

第一行,两个整数 n,m,分别表示同学们的数量与关系数量。

接下来 m 行,每行两个整数 ai,bi,表示一对关系。

输出格式

一行,一个整数,表示答案对 109+7 取模的结果。

输入样例 1

4 2
1 3
2 4

输出样例 1

2

输入样例 2

3 0

输出样例 2

6

输入样例 3

3 2
1 2
2 1

输出样例 3

0

数据范围

对于 20% 的测试数据点,保证 1≤n≤8,0≤m≤10 。

对于另外 20% 的测试数据点,保证 1≤n≤103,0≤m≤1 。

对于所有测试数据点,保证 1≤n≤2×105,0≤m≤2×105。

答案与解析
参考答案
#include <cstdio>

using namespace std;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int n, m;
int pre[N], suf[N];
int vis[N];
int cnt;
int ans;

int main() {
	scanf("%d%d", &n, &m);
	ans = 1;
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		if (pre[b] == a && suf[a] == b)
			continue;
		if (pre[b] || suf[a])
			ans = 0;
		pre[b] = a;
		suf[a] = b;
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i])
			continue;
		int j = i;
		while (j) {
			if (vis[j] == i)
				ans = 0;
			if (vis[j])
				break;
			vis[j] = i;
			j = suf[j];
		}
	}
	for (int i = 1; i <= n; i++)
		cnt += !pre[i];
	for (int i = 1; i <= cnt; i++)
		ans = 1ll * ans * i % mod;
	printf("%d\n", ans);
	return 0;
}
题目详情
126 简答题 偏难 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";
	}
}
题目详情
127 简答题 偏难 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

题目详情
128 简答题 偏难 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)。

题目详情
129 简答题 偏难 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算法的完成。按照优先队列的模板完成即可。

题目详情
130 简答题 偏难 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;
}
题目详情
131 简答题 偏难 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";
	}
	}
}
题目详情
132 简答题 偏难 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;
}
题目详情
133 简答题 偏难 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;
}
题目详情