GESP认证C++编程真题解析 | 202509 六级

编程题

P14075 划分字符串

【题目来源】

洛谷：P14075 [GESP202509 六级] 划分字符串 - 洛谷

【题目描述】

小 A 有一个由 \(n\) 个小写字母组成的字符串 \(s\)。他希望将 \(s\) 划分为若干个子串，使得子串中每个字母至多出现一次。例如，对于字符串 street 来说，str + e + e + t 是满足条件的划分；而 s + tree + t 不是，因为子串 tree 中 e 出现了两次。

额外地，小 A 还给出了价值 \(a_1,a_2,…,a_n\)，表示划分后长度为 \(i\) 的子串价值为 \(a_i\)。小 A 希望最大化划分后得到的子串价值之和。你能帮他求出划分后子串价值之和的最大值吗？

【输入】

第一行，一个正整数 \(n\)，表示字符串的长度。

第二行，一个包含 \(n\) 个小写字母的字符串 \(s\)。

第三行，\(n\) 个正整数 \(a_1,a_2,…,a_n\)，表示不同长度的子串价值。

【输出】

一行，一个整数，表示划分后子串价值之和的最大值。

【输入样例】

6
street
2 1 7 4 3 3

【输出样例】

13

【算法标签】

《洛谷 P14075 划分字符串》 #线性DP# #GESP# #2025#

【代码详解】

#include <bits/stdc++.h>
using namespace std;#define int long long  // 使用长整型防止溢出
const int N = 100005;  // 定义最大数组长度int n;                  // 字符串长度
string s;               // 输入的字符串（处理后前面加空格）
string t[N];           // 未使用的字符串数组（保留原代码结构）
int a[N];               // 存储每个位置的分值
int dp[N];              // dp数组，dp[i]表示前i个字符的最大得分signed main()
{// 输入字符串长度和字符串cin >> n >> s;// 在字符串前添加空格，使索引从1开始s = " " + s;// 输入每个位置的分值for (int i = 1; i <= n; i++){cin >> a[i];}// 初始化dp数组dp[1] = a[1];  // 第一个字符的最大得分就是它本身的分值// 动态规划计算最大得分for (int i = 2; i <= n; i++){set<char> st;  // 用于记录当前子串中的字符// 初始值：将当前字符单独作为一个子串dp[i] = dp[i - 1] + a[1];// 将当前字符加入集合st.insert(s[i]);// 尝试将当前字符与前面的字符组成更长的子串for (int j = i - 1; j >= 1; j--){// 如果遇到重复字符，则终止循环if (st.count(s[j])){break;}// 将字符加入集合st.insert(s[j]);// 更新dp值：考虑从j到i的子串dp[i] = max(dp[i], dp[j - 1] + a[i - j + 1]);}}// 输出前n个字符的最大得分cout << dp[n] << endl;return 0;
}

【运行结果】

6
street
2 1 7 4 3 3
13

P14076 货物运输

【题目来源】

洛谷：P14076 [GESP202509 六级] 货物运输 - 洛谷

【题目描述】

A 国有 \(n\) 座城市，依次以 \(1,2,…,n\) 编号，其中 \(1\) 号城市为首都。这 \(n\) 座城市由 \(n−1\) 条双向道路连接，第 \(i\) 条道路（\(1≤i<n\)）连接编号为 \(u_i,v_i\) 的两座城市，道路长度为 \(l_i\)。任意两座城市间均可通过双向道路到达。

现在 A 国需要从首都向各个城市运送货物。具体来说，满载货物的车队会从首都开出，经过一座城市时将对应的货物送出，因此车队需要经过所有城市。A 国希望你设计一条路线，在从首都出发经过所有城市的前提下，最小化经过的道路长度总和。注意一座城市可以经过多次，车队最后可以不返回首都。

【输入】

第一行，一个正整数 \(n\)，表示 A 国的城市数量。

接下来 \(n−1\) 行，每行三个正整数 \(u_i,v_i,l_i\)，表示一条双向道路连接编号为 \(u_i,v_i\) 的两座城市，道路长度为 \(l_i\)。

【输出】

一行，一个整数，表示你设计的路线所经过的道路长度总和。

【输入样例】

4
1 2 6
1 3 1
3 4 5

【输出样例】

18

【算法标签】

《洛谷 P14076 货物运输》 #树的遍历# #GESP# #2025#

【代码详解】

#include <bits/stdc++.h>
using namespace std;#define int long long  // 使用长整型防止溢出
const int N = 100005;  // 定义最大节点数typedef pair<int, int> PII;  // 定义边类型，存储邻接节点和边权int n;                      // 树的节点数
int sum = 0;                // 存储所有边的总权值
int ans = 0;                // 存储树的直径（最长路径长度）
vector<PII> ve[N];          // 邻接表存储树结构/*** 深度优先搜索计算从节点u出发的最长路径* @param u 当前节点* @param fa 父节点（防止回退）* @return 从u出发的最长路径长度*/
int dfs(int u, int fa)
{int maxs = 0;  // 存储从u出发的最长路径长度// 遍历所有邻接节点for (int i = 0; i < ve[u].size(); i++){int v = ve[u][i].first;   // 邻接节点int l = ve[u][i].second;  // 边权// 跳过父节点if (v == fa)continue;// 递归计算子节点的最长路径，并更新当前最大值maxs = max(maxs, dfs(v, u) + l);}// 更新全局最长路径（树的直径）ans = max(maxs, ans);return maxs;
}signed main()
{// 输入节点数cin >> n;// 输入树的结构（n-1条边）for (int i = 1; i < n; i++){int u, v, l;cin >> u >> v >> l;// 添加到邻接表（无向图）ve[u].push_back({v, l});ve[v].push_back({u, l});// 累加所有边的权值sum += l;}// 计算树的直径（最长路径）int t = dfs(1, -1);/*** 输出结果：* 所有边权之和的两倍减去最长路径长度* 这是解决"邮差问题"（遍历所有边的最短路径）的经典公式*/cout << sum * 2 - t << endl;return 0;
}

【运行结果】

4
1 2 6
1 3 1
3 4 5
18