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

GESP-C++八级 题库

共 270 道题 ,第 13 / 14 页 · 按题型筛选,点「查看答案」核对解析
241 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

在C++中,若结构体中包含一个 static 成员变量,则该变量的存储空间属于结构体对象的一部分。( )

A
正确
B
错误
答案与解析
正确答案:错
结构体中的 static 成员变量属于类类型本身而非结构体对象实例;其存储空间由程序数据区分配,不随结构体对象的创建而分配在对象内存中;该变量被所有结构体实例共享,生命周期与程序运行期一致;结构体定义仅声明 static 成员变量,定义需在结构体外单独进行;sizeof 运算符计算结构体大小时不包含 static 成员变量所占空间。
题目详情
242 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

在C++中,若函数参数类型为 const int & ,则该参数既可以绑定左值,也可以绑定右值。( )

A
正确
B
错误
答案与解析
正确答案:对
在C++中,const引用(const T&)具有延长临时对象生命周期的能力。当函数参数为const int&时,该参数可绑定到左值,因为左值具有明确的内存地址和持久性;同时也能绑定到右值,包括字面量和临时对象,原因是编译器会为右值创建临时变量,并将const引用绑定到该临时变量上,且该临时变量的生命周期被扩展至引用本身的生命周期。此行为由语言标准规定,适用于所有符合标准的实现。
题目详情
243 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

若一个无向图的最小生成树唯一,则图中所有边权必定各不相同。( )

A
正确
B
错误
答案与解析
正确答案:错
分析无向图最小生成树唯一性与边权关系时,需考察最小生成树构造过程中边的选择机制。当存在多条边具有相同权重时,在满足不形成环的前提下,这些边可能互为替代地被选入生成树。若某时刻可选择的边中存在权值相等的不同边,且各自参与构成不同生成树,则最小生成树不唯一。但即使存在权值相同的边,若其在图中的位置导致仅有一种方式能将其纳入生成树而不形成环,此时仍可能产生唯一最小生成树。因此,边权是否互异并非决定最小生成树唯一性的充分或必要条件,应通过图结构与边权分布共同确定生成树的唯一性。
题目详情
244 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

若一个图中所有顶点的度数为偶数,则一定存在欧拉回路。( )

A
正确
B
错误
答案与解析
正确答案:错
分析图中每个顶点的度数是否均为偶数;根据欧拉回路存在的充要条件,判断该图是否连通且所有顶点度数为偶数;若图不连通,则即使所有顶点度数为偶数,也无法形成单一欧拉回路;检查图的连通性与顶点度数之间的关系,确认两者同时满足时才能保证欧拉回路存在;仅凭所有顶点度数为偶数这一条件,无法单独推出欧拉回路必然存在。
题目详情
245 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

如果将一个连通无向图中所有边的权值都统一增加同一个正整数常数C,形成图。则的最小生成树中每条边在中对应的边组成的树,一定是的最小生成树。( )

A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
246 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

在图论算法中,Kruskal算法和Prim算法都可以用来求解最小生成树,且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。( )

A
正确
B
错误
答案与解析
正确答案:对
Kruskal算法通过按边权递增顺序依次选择不构成环的边,逐步连接所有顶点;Prim算法从任意起始顶点出发,每次选择与当前生成树相连且权值最小的边扩展树结构。两种算法均基于贪心策略,每次决策仅依赖当前可选边的最小权值。在任意连通无向图中,若边权唯一确定,则所有最小生成树的总边权和由图的拓扑结构和边权分布共同决定。无论采用何种贪心路径构建,最终生成树的边集可能不同,但其总边权和始终等于该图最小生成树的数学定义所规定的值。算法过程不引入额外约束,故二者求得的总边权和必然一致。
题目详情
247 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

在动态规划问题中,“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式,它们的时间复杂度总是相同的。( )

A
正确
B
错误
答案与解析
正确答案:错
分析动态规划中状态转移方程与递推的实现机制,明确其通过迭代方式按序计算各状态值的过程;分析递归与记忆化搜索的实现机制,明确其以递归调用为基础,在搜索路径中存储已计算状态值的方式;比较两者在处理相同状态空间时的计算次数与访问频率;考察时间复杂度是否由状态总数和每个状态的计算耗时共同决定;确认两种方法在状态计算次数和重复子问题处理上的一致性。
题目详情
248 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

对于任意正整数 ,二项式(a+b)n展开式中各项的二项式系数之和等于2n。

A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
249 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

使用快速排序对n个元素进行排序时,无论最好、最坏还是平均情况,时间复杂度为O(nlogn)。( )

A
正确
B
错误
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
250 判断题 适中 GESP编程能力等级认证 ·GESP-C++八级 · 未分类

使用倍增法预处理区间最值问题时,预处理的时间复杂度为O(nlogn),查询的时间复杂度为O(1)。( )

A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
251 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

猫和老鼠

时间限制:1.0 s

内存限制:512.0 MB

题目描述

猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2,...,n编号,结点i(1≤i≤n)有价值为ci的奶酪。在m条带权无向边中,第i(1≤i≤m)条无向边连接结点ui与结点vi,边权wi表示猫和老鼠通过这条边所需的时间。

猫窝位于结点a,老鼠洞位于结点b。对于老鼠而言,结点u是安全的当且仅当:

老鼠能规划一条从结点u出发逃往老鼠洞的路径,使得对于路径上任意结点x(包括结点u与老鼠洞)都有:

猫从猫窝出发到结点x的最短时间严格大于老鼠从结点u沿这条路径前往结点x所需的时间。

老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能,但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失,老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。

输入格式

第一行,两个正整数n,m,分别表示图的结点数与边数。

第二行,两个正整数a,b,分别表示猫窝的结点编号,以及老鼠洞的结点编号。

第三行,n个正整数c1,c2,...,cn,表示各个结点的奶酪价值。

接下来 行中的第i行(1≤x≤m)包含三个正整数ui,vi,wi,表示图中连接结点ui与结点vi的边,边权为wi。

输出格式

输出一行,一个整数,表示老鼠所能拿到的奶酪价值之和。

输入样例 1

5 5
1 2
1 2 4 8 16
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8

输出样例 1

22

输入样例 2

6 10
3 4
1 1 1 1 1 1
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6

输出样例 2

3

数据范围

对于40的测试点,保证1≤n≤500,1≤m≤500。

对于所有测试点,保证1≤n≤105,1≤m≤105,1≤a,b≤n且a≠b,1≤ui,vi≤n,1≤wi≤109。

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

const int N = 1e5 + 5;
const long long oo = 1e18;
int n, m;
int a, b;
int c[N];
vector<pair<int, int>> e[N];
long long dis[N];
priority_queue<pair<long long, int>> q;
long long ans;

int main() {
    scanf("%d%d", &n, &m);
    scanf("%d%d", &a, &b);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u].emplace_back(make_pair(v, w));
        e[v].emplace_back(make_pair(u, w));
    }
    for (int i = 1; i <= n; i++)
        dis[i] = oo;
    dis[b] = 0;
    q.push(make_pair(-dis[b], b));
    while (!q.empty()) {
        auto p = q.top();
        q.pop();
        if (dis[p.second] != -p.first)
            continue;
        int u = p.second;
        for (auto r : e[u]) {
            int v = r.first, w = r.second;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
    for (int i = 1; i <= n; i++)
        if (dis[i] < dis[a])
            ans += c[i];
    printf("%lld\n", ans);
    return 0;
}
题目详情
252 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

宝石项链

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小 A 有一串包含n枚宝石的宝石项链,这些宝石按照在项链中的顺序依次以1,2,...,n编号,第n枚宝石与第1枚宝石相邻。项链由m种宝石组成,其中第i枚宝石种类为ti。

小 A 想将宝石项链分给他的好朋友们。具体而言,小 A 会将项链划分为若干连续段,并且需要保证每段都包含全部种宝石。请帮小 A 计算在满足条件的前提下,宝石项链最多可以划分为多少段。

输入格式

第一行,两个正整数n,m,分别表示宝石项链中的宝石的数量与种类数。

第二行,n个正整数ti,t2,...,tn,表示每枚宝石的种类。

输出格式

输出一行,一个整数,表示宝石项链最多可以划分的段数。

输入样例 1

6 2
1 2 1 2 1 2

输出样例 1

3

输入样例 2

7 3
3 1 3 1 2 1 2

输出样例 2

2

数据范围

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

const int L = 20;
const int N = 2e5 + 5;
const int oo = 1e9;
int n, m;
int t[N], jump[L][N];
int cnt[N], tot;
int ans;

int go(int u) {
    int cnt = 0, ans = 0;
    for (int i = L - 1; i >= 0; i--)
        if (cnt + jump[i][u] <= n) {
            cnt += jump[i][u];
            ans += 1 << i;
            u = (u + jump[i][u] - 1) % n + 1;
        }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t[i]);
        t[i + n] = t[i];
    }
    for (int i = 1, r = 0; i <= n; i++) {
        while (tot < m) {
            r++;
            if (!cnt[t[r]]++)
                tot++;
        }
        jump[0][i] = r - i + 1;
        if (!--cnt[t[i]])
            tot--;
    }
    for (int i = 1; i < L; i++)
        for (int j = 1; j <= n; j++) {
            int tar = (j + jump[i - 1][j] - 1) % n + 1;
            jump[i][j] = min(jump[i - 1][j] + jump[i - 1][tar], oo);
        }
    for (int i = 1; i <= n; i++)
        ans = max(ans, go(i));
    printf("%d\n", ans);
    return 0;
}
题目详情
253 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

最短距离

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

const int N = 100005;
int n, p, q;
int a, b;
int ans;

// 欧几里得求最大公约数
int gcd(int a, int b) {
    if (!a || !b) 
        return a + b;
    return gcd(b, a % b);
}

int main() {
    scanf("%d%d%d", &n, &p, &q);
    while (n--) {
        scanf("%d%d", &a, &b);
        if (a == b) {
            ans = 0;
        } else if (a == 1 || b == 1) {
            ans = p;
        } else {
            // 两种拆分方案:各自单独处理
            ans = min(p + p, q + q);
            if (gcd(a, b) == 1) {
                // 互质,可以合并处理花费p
                ans = min(ans, p);
            } else {
                // 不互质,合并处理花费q
                ans = min(ans, q);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
题目详情
254 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 6.1 最小生成树

最小生成树

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

const int N = 100005;
const int M = 200005;
const long long INF = 1e18;

int n, m;
// 存每条边两端点、权值、边编号数组
int u[M], v[M], w[M], p[M];
// 链式前向星:h表头,id存边编号,nx下一条边,et边计数
int h[N], id[M], nx[M], et;
// 并查集父数组f,mark标记是否是最小生成树树边
int f[N], mark[M];
long long sum_mst, ans[M];
// dep深度,pid记录到达该点的树边编号
int dep[N], pid[N];

// 按边权从小到大排序
bool cmp(int x, int y) {
    return w[x] < w[y];
}

// 带路径压缩并查集查找,0代表根节点
int getf(int u) {
    if (!f[u]) return u;
    return f[u] = getf(f[u]);
}

// 链式前向星加边:x连接编号为p的边
void link(int x, int edge_id) {
    id[++et] = edge_id;
    nx[et] = h[x];
    h[x] = et;
}

// DFS遍历最小生成树,求每个点深度、记录到达当前点的树边pid[x]
void dfs(int x, int fa = 0, int edge_id = 0) {
    dep[x] = dep[fa] + 1;
    pid[x] = edge_id;
    for (int i = h[x]; i; i = nx[i]) {
        // 异或快速求对端:u^v^x 得到另一个端点
        int to = u[id[i]] ^ v[id[i]] ^ x;
        if (to != fa) {
            dfs(to, x, id[i]);
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    // 读入所有边
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &u[i], &v[i], &w[i]);
        p[i] = i;
    }
    // Kruskal:边按权升序
    sort(p + 1, p + m + 1, cmp);

    // 1. Kruskal构建最小生成树
    for (int i = 1; i <= m; ++i) {
        int eid = p[i];
        int x = u[eid], y = v[eid];
        int fx = getf(x), fy = getf(y);
        if (fx == fy) continue;
        // 选为树边,标记并累加MST总权值
        mark[eid] = 1;
        f[fx] = fy;
        sum_mst += w[eid];
        // 加入MST链式前向星
        link(x, eid);
        link(y, eid);
    }

    // 初始化答案:树边暂设无穷INF,非树边初始答案就是MST总和sum_mst
    for (int i = 1; i <= m; ++i) {
        ans[i] = mark[i] ? INF : sum_mst;
    }

    // DFS求MST上每个点深度、对应树边pid
    dfs(1);

    // 重置并查集,用于按非树边更新树边答案
    for (int i = 1; i <= n; ++i) f[i] = 0;

    // 2. 遍历所有非树边,更新路径上树边的替换答案
    for (int i = 1; i <= m; ++i) {
        int eid = p[i];
        if (mark[eid]) continue; // 跳过树边,只处理非树边
        int x = getf(u[eid]), y = getf(v[eid]);
        // 向上爬LCA路径,统一路径上所有树边的答案
        while (x != y) {
            // 保证x更深
            if (dep[x] < dep[y]) swap(x, y);
            // pid[x]是连接x与父节点的树边
            int tree_edge = pid[x];
            // 替换这条树边后的新MST权值
            ans[tree_edge] = sum_mst - w[tree_edge] + w[eid];
            // 并查集向上合并,下次不再处理这条边
            int to = u[tree_edge] ^ v[tree_edge] ^ x;
            f[x] = to;
            x = getf(x);
        }
    }

    // 输出每条边答案:INF代表无法替换,输出-1;否则输出替换后最小生成树权值
    for (int i = 1; i <= m; ++i) {
        if (ans[i] < INF) printf("%lld\n", ans[i]);
        else printf("-1\n");
    }
    return 0;
}
题目详情
255 简答题 偏难 GESP编程能力等级认证 ·GESP-C++八级 · 综合练习

树上旅行

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

【问题描述】

给定一棵有 n 个结点的有根树,结点依次以 1、2、……、n 编号,其中根结点的编号为 1。

小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先会选定结点 si 作为起点,并移动若干次。移动分为以下两种:

(1)移动至当前结点的父结点。特殊地,如果当前位于根结点,则不进行移动。

(2)移动至当前结点的所有子结点中编号最小的结点。特殊地,如果当前位于叶子结点,则不进行移动。

由于移动次数可能很大,对于第 i 次旅行,旅行中的移动将以 ki 个不为零的整数构成的序列 ai,1、ai,2、……、ai,k 表示。

对于 ai,j,若 ai,j > 0 则代表进行 ai,j 次第一种移动;若 ai,j < 0 则代表进行 ai,j 次第二种移动。根据给出的序列从左至右完成所有移动后,小 A 所在的结点即是旅行的终点。

给定每次旅行的起点与移动序列,请你求出旅行终点的结点编号。

【输入描述】

第一行,两个正整数 n、q,分别表示有根树的结点数量,以及旅行次数。

第二行,n -1 个整数 p2、p3、……、pn,其中 pi 表示结点 i 的父结点编号。

接下来 2q 行中的第 2i - 1行(1<=i<=q )包含两个正整数 si、ki,分别表示第 i 次旅行的起点编号,以及移动序列的长度。

第 2i 行包含 k 个整数 ai,1、ai,2、……、ai,k,表示移动序列。

【输出描述】

输出共 q 行,第 i 行包含一个整数,表示第 i 次旅行终点的结点编号。

【样例输入1】

5 4
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1

【样例输出1】

4
1
4
2

【样例输入2】

8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8

【样例输出2】

1
7
1

【数据范围】

对于所有测试点,保证 1 <= n <= 10^5,1 <= q <= 2×10^4,1 <= pi、si <= n,ki >= 1,且Σki <= 10^5,1<=|ai,j|<=n。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
const int L = 18;
int n, q;
int h[N], nx[N];
int par[L][N], son[L][N];
void dfs(int u) {
    for (int i = 1; i < L; i++)
        par[i][u] = par[i - 1][par[i - 1][u]];
    son[0][u] = u;
    for (int i = h[u]; i; i = nx[i]) {
        dfs(i);
        if (son[0][u] == u || i < son[0][u])
            son[0][u] = i;
    }
    for (int i = 1; i < L; i++)
        son[i][u] = son[i - 1][son[i - 1][u]];
}
int move(int go[L][N], int u, int step) {
    for (int i = 0; i < L; i++)
        if ((step >> i) & 1)
            u = go[i][u];
    return u;
}
int main() {
    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        cin >> par[0][i];
        nx[i] = h[par[0][i]];
        h[par[0][i]] = i;
    }
    par[0][1] = 1;
    dfs(1);
    while (q--) {
        int s, k;
        cin >> s >> k;
        while (k--) {
            int a;
            cin >> a;
            if (a < 0)
                s = move(son, s, -a);
            else
                s = move(par, s, a);
        }
        cout << s << endl;
    }
    return 0;
}
题目详情
256 简答题 偏难 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;
}
题目详情
257 简答题 偏难 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;
}
题目详情
258 简答题 偏难 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();
}
题目详情
259 简答题 偏难 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";
}
题目详情
260 简答题 偏难 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;
}
题目详情