GESP-C++六级 题库
5G网络中,5G中的G表示Gigabytes/s,其中 1 GB = 1024 MB。(2023.9C++六级)
有些算法或数据结构在C/C++语言中使用指针实现,一个典型的例子就是链表。因此,链表这一数据结构在C/C++语言中只能使用指针来实现。
路径覆盖
题目描述
给定一棵有 n 个结点的有根树 T ,结点依次以 1,2, …, n 编号,根结点编号为1。初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结点。将结点 i 染为黑色需要代价 ci ,你需要在满足以上条件的情况下,最小化染色代价之和。 叶子是指 T 中没有子结点的结点。
输入格式
第一行,一个正整数 n ,表示结点数量。 第二行, n−1 个正整数 f2, f3, …, fn ,其中 fi 表示结点 i 的父结点的编号,保证 fi<i 第三行, n 个正整数 c1, c2, …, cn,其中 ci 表示将结点 i 染为黑色所需的代价。
输出格式
一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。
样例
输入样例1
输出样例1
输入样例2
输出样例2
数据范围
对于 40% 的测试点,保证 2 ≤n ≤16
对于另外 20% 的测试点,保证 fi=i-1 对于所有测试点,保证 2 ≤n ≤10^5, 1 ≤ci ≤10^9
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n;
int f[N], c[N], cnt[N];
long long ans[N];
vector<int> son[N];
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
scanf("%d", &f[i]);
son[f[i]].push_back(i);
cnt[f[i]]++;
}
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = n; i >= 1; i--) {
ans[i] = c[i];
long long sum = 0;
for (int v : son[i]) {
sum += ans[v];
}
ans[i] = min(ans[i], sum);
}
printf("%lld\n", ans[1]);
return 0;
}道具商店
题目描述
道具商店里有 n 件道具可供挑选。第 i 件道具可为玩家提升ai点攻击力,需要 ci 枚金币才能购买,每件道具只能购买一次。现在你有 k 枚金币,请问你最多可以提升多少点攻击力?
输入格式
第一行,两个正整数 n k ,表示道具数量以及你所拥有的金币数量。 接下来 n 行,每行两个正整数ai , ci ,表示道具所提升的攻击力点数,以及购买所需的金币数量。
输出格式
输出一行,一个整数,表示最多可以提升的攻击力点数。
样例
输入样例1
3 11 99 1 33 2 11 3
输出样例1
132
输入样例2
4 100 10 1 20 11 100 99 40 33
输出样例2
110
数据范围
对于部分测试点,保证 1 ≤k ≤500, 1 ≤ ci ≤500
对于所有测试点,保证 1 ≤n ≤500 , 1 ≤k ≤10^9 , 1 ≤ ai ≤500 , 1 ≤ ci ≤10^9
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 505;
const int oo = 1e9 + 10;
int n, k;
int f[N * N];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i < N * N; i++)
f[i] = oo;
f[0] = 0;
int s = 0;
for (int i = 1; i <= n; i++) {
int a, c;
scanf("%d%d", &a, &c);
s += a;
for (int j = s; j >= a; j--)
f[j] = min(f[j], f[j - a] + c);
}
int ans = 0;
for (int i = 0; i < N * N; i++)
if (f[i] <= k)
ans = i;
printf("%d\n", ans);
return 0;
}划分字符串


#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
int n;
char s[N];
int a[N];
long long f[N];
int main() {
scanf("%d", &n);
scanf("%s", s + 1); // 字符串下标从1开始
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
// DP:f[i] = 前i个字符分割后的最大收益
for (int i = 1; i <= n; ++i) {
int mask = 0; // 位掩码,记录当前分段出现过的字符
// j向左枚举分段起点,区间 [j, i]
for (int j = i; j >= 1; --j) {
int cur_bit = 1 << (s[j] - 'a');
// 当前字符已在分段内,无法继续向左拓展
if (mask & cur_bit) break;
mask |= cur_bit;
// 分段长度 len = i - j + 1
int seg_len = i - j + 1;
f[i] = max(f[i], f[j - 1] + a[seg_len]);
}
}
printf("%lld\n", f[n]);
return 0;
}货物运输



#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
int n;
vector<vector<pair<int, int>>> e;
long long total_sum, max_dist;
// u当前节点 fa父节点 d从起点1走到u的距离
void dfs(int u, int fa, long long d) {
max_dist = max(d, max_dist);
for (auto edge : e[u]) {
int v = edge.first;
int w = edge.second;
if (v != fa) {
dfs(v, u, d + w);
}
}
}
int main() {
scanf("%d", &n);
e.resize(n + 1);
for (int i = 1; i < n; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
total_sum += w;
}
dfs(1, 0, 0);
// 总往返路程 - 最长单条路径(不用折返)
long long ans = total_sum * 2 - max_dist;
printf("%lld\n", ans);
return 0;
}学习小组
时间限制:1 s,内存限制:512 MB
【问题描述】
班主任计划将班级里的 n 名同学划分为若干个学习小组,每名同学都需要分入某一个学习小组中。观察发现,如果一个学习小组中恰好包含 k 名同学,则该学习小组的讨论积极度为 ak。
给定讨论积极度 a1、a2、……、an,请你计算将这 n 名同学划分为学习小组的所有可能方案中,讨论积极度之和的最大值。
【输入描述】
第一行,一个正整数 n,表示班级人数。
第二行,n 个非负整数 a1、a2、……、an,表示不同人数学习小组的讨论积极度。
【输出描述】
输出共一行,一个整数,表示所有划分方案中,学习小组讨论积极度之和的最大值。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于40%测试点,保证 1 <= n <= 10。
对于所有测试点,保证 1 <= n <= 1000,0 <= ai <= 10000。
#include <iostream>
using namespace std;
const int N = 1005;
int n, a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
for (int j = 1; j < i; j++)
a[i] = max(a[i], a[j] + a[i - j]);
}
cout << a[n] << endl;
return 0;
}最大因数
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 10^9 个结点的有根树,这些结点依次以 1、2、……、10^9编号,根结点的编号为 1。
对于编号为 k(2 <= k <= 10^9)的结点,其父结点的编号为 k 的因数中除 k 以外最大的因数。
现在有 q 组询问,第 i(1<= i <= q)组询问给定 xi、yi,请你求出编号分别为 xi、yi 的两个结点在这棵树上的距离。
两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
【输入描述】
第一行,一个正整数 q,表示询问组数。
接下来 q 行,每行两个正整数 xi、yi,表示询问结点的编号。
【输出描述】
输出共 q 行,每行一个整数,表示结点 xi、yi 之间的距离。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%的测试点,保证 1 <= xi、yi <= 1000。
对于所有测试点,保证 1 <= q <= 1000,1 <= xi、yi <= 10^9。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50;
int a[N], cnta, b[N], cntb;
int f[N], t, q;
void factorize(int x, int a[], int &cnt) {
a[0] = x;
t = 0;
for (int i = 2; i * i <= x; i++)
while (x % i == 0) {
f[++t] = i;
x /= i;
}
if (x > 1)
f[++t] = x;
for (int i = 1; i <= t; i++)
a[i] = a[i - 1] / f[i];
cnt = t;
}
int main() {
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
factorize(x, a, cnta);
factorize(y, b, cntb);
int px = 0, py = 0;
while (a[px] != b[py]) {
if (a[px] > b[py])
px++;
else
py++;
}
cout << px + py << endl;
}
return 0;
}树上漫步
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一棵 n 个结点的树,这些结点依次以 1、2、……、n标号。
小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。
现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。
【输入描述】
第一行,一个正整数 n。
接下来 n - 1 行,每行两个整数 ui、vi,表示树上有一条连接结点 ui 和结点 vi 的边。
【输出描述】
一行, n 个整数,第 i 个整数表示从结点 i 出发开始漫步,能结束漫步的结点数量。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 1<=n<=1000。
对于所有测试点,保证 1<=n<=200000。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
int n;
int h[N], to[E], nx[E], et;
int cnt[N], bel[N];
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[u];
h[u] = et;
}
void dfs(int u, int c, int f) {
bel[u] = c;
cnt[c]++;
for (int i = h[u]; i; i = nx[i])
if (to[i] != f)
dfs(to[i], c ^ 1, u);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
ae(u, v);
ae(v, u);
}
dfs(1, 0, 0);
for (int i = 1; i <= n; i++)
printf("%d%c", cnt[bel[i]], " \n"[i == n]);
return 0;
}环线
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 喜欢坐地铁。地铁环线有 n 个车站,依次以 1、2、……、n标号。车站 i(1<=i<n )的下一个车站是车站 i+1。
特殊地,车站 n 的下一个车站是车站 1。
小 A 会从某个车站出发,乘坐地铁环线到某个车站结束行程,这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。
当小 A 乘坐地铁环线经过车站 i 时,小 A 会获得 ai 点快乐值。请你安排小 A 的行程,选择出发车站与结束车站,使得获得的快乐值总和最大。
【输入描述】
第一行,一个正整数 n,表示车站的数量。
第二行, n 个整数 a1、a2、……、an,分别表示经过每个车站时获得的快乐值。
【输出描述】
一行,一个整数,表示小 A 能获得的最大快乐值。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 1<=n<=200。
对于 40% 的测试点,保证 1<=n<=2000。
对于所有测试点,保证 1<=n<=200000, -10^9<=ai<=10^9。
正确答案: 暂无(答题 0次,答对 0次,正确率:0%)
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 4e5 + 5;
int n;
long long a[N], pre[N];
int q[N], ql, qr;
long long ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
a[n + i] = a[i];
}
for (int i = 1; i <= 2 * n; i++)
pre[i] = pre[i - 1] + a[i];
ql = qr = 1;
ans = -1e18;
for (int i = 1; i <= 2 * n; i++) {
while (ql <= qr && q[ql] < i - n)
ql++;
ans = max(ans, pre[i] - pre[q[ql]]);
while (ql <= qr && pre[i] < pre[q[qr]])
qr--;
q[++qr] = i;
}
printf("%lld\n", ans);
return 0;
}树上游走
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含无穷节点的二叉树(即每个节点都有左儿子节点和右儿子节点;除根节点外,每个节点都有父节点),其中根节点的编号为 1,对于节点 i ,其左儿子的编号为 2×i,右儿子的编号为 2×i+1。
小杨会从节点 s 开始在二叉树上移动,每次移动为以下三种移动方式的任意一种:
第1种移动方式: 如果当前节点存在父亲节点,向上移动到当前节点的父亲节点,否则不移动;
第2种移动方式: 移动到当前节点的左儿子;
第3种移动方式: 移动到当前节点的右儿子。
小杨想知道移动 n 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过 1012。
输入格式
第一行包含一个正整数 n,s,代表移动次数和初始节点编号。
第二行包含一个长度为 n 且仅包含大写字母 U,L,R 的字符串,代表每次移动的方式,其中 U 代表第1种移动方式,L 代表第2种移动方式,R代表第3种移动方式。
输出格式
输出一个正整数,代表最后所处的节点编号。
输入样例
输出样例
样例解释
小杨的移动路线为 2-1-3-7。

对于全部数据,保证有 1≤n≤106,1≤s≤1012。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e12;
int n;
stack<char> st;
string c;
ll s;
int main(){
cin >> n >> s >> c;
for(int i = 0; i < n; i ++){
if(c[i] == 'U'){
if(s == 1) continue;
if(st.size()){
st.pop();
continue;
}
s >>= 1;
}else if(c[i] == 'L'){
if((s << 1) > INF){
st.push('L');
continue;
}
s = s << 1;
}else{
if((s << 1 | 1) > INF){
st.push('R');
continue;
}
s = s << 1 | 1;
}
}
cout << s << "\n";
return 0;
}运送物资
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨管理着 m 辆货车,每辆货车每天需要向 A 市和 B 市运送若干次物资。小杨同时拥有 n 个运输站点,这些站点位于 A 市和 B 市之间。
每次运送物资时,货车从初始运输站点出发,前往 A 市或 B 市,之后返回初始运输站点。A 市、B 市和运输站点的位置可以视作数轴上的三个点,其中 A 市的坐标为 0,B 市的坐标为 x ,运输站点的坐标为 p 且有 0<p<x,货车每次去 A 市运送物资的总行驶路程为 2p,去 B 市运送物资的总行驶路程为 2(x−p)。
对于第 i 个运输站点,其位置为 pi且至多作为 ci辆车的初始运输站点。小杨想知道,在最优分配每辆货车的初始运输站点的情况下,所有货车每天的最短总行驶路程是多少。
输入格式
第一行包含三个正整数 n,m,x,代表运输站点数量,货车数量和两市距离。
之后 n 行,每行包含两个正整数 pi,ci,代表第 i 个运输站点的位置和最多容纳车辆数。
之后 m 行,每行包含两个正整数 ai,bi,代表第 i 辆货车每天需要向 A 市运送 ai次物资,向 B 市运送 bi次物资。
输出格式
输出一个正整数,代表所有货车每天的最短总行驶路程。
输入样例
输出样例
样例解释
第 1 辆车的初始运输站点为站点 3,第 2 辆车的初始运输站点为站点 2。第 3 辆车的初始运输站点为站点 1,第 4 辆车的初始运输站点为站点 3。此时总行驶路程最短,为 40186。

对于全部数据,保证有 1≤n,m≤105,2≤x≤108,0<pi<x,1≤ci≤105,0≤ai,bi≤105。数据保证∑ci≥m。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
int n,m;
ll x;
vector<pair<int,int> > st;
int a[N],b[N];
int main(){
cin>>n>>m>>x;
for(int i=1;i<=n;i++){
int p,c;
cin>>p>>c;
st.push_back(make_pair(p,c));
}
sort(st.begin(),st.end());
for(int i=1;i<=m;i++){
cin>>a[i]>>b[i];
}
vector<pair<int,int> > neg,pos;
ll res=0;
for(int i=1;i<=m;i++){
if(a[i]>=b[i])
pos.push_back(make_pair(a[i]-b[i],i));
else{
neg.push_back(make_pair(a[i]-b[i],i));
}
res+=1ll*b[i]*x;
}
sort(neg.begin(),neg.end());
sort(pos.begin(),pos.end());
reverse(pos.begin(),pos.end());
int l=0,r=n-1;
for(auto i:neg){
while(r>=1&&st[r].second==0)r--;
res+=1ll*(a[i.second]-b[i.second])*st[r].first;
st[r].second-=1;
}
for(auto i:pos){
while(l<=n&&st[l].second==0)l++;
res+=1ll*(a[i.second]-b[i.second])*st[l].first;
st[l].second-=1;
}
cout<<res*2<<"\n";
}