GESP-C++七级 题库
C++ 语言中,表达式 4 ^ 2 的结果类型为 int ,值为 6 。
C++ 中引用可以重新绑定。
在 C++ 中,若函数形参为引用类型,则在函数内部对该形参的修改会影响对应的实参。
如果一个最值问题可以用动态规划在多项式时间内求解,那么也一定存在一种贪心策略,可以在多项式时间 内求得最优解。
在无向连通图中删除一条边,该图就一定变成非连通图。
在一个无向图中,每个顶点有不同的编号,在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点,则从指定顶点开始的遍历序列是唯一的。
若所有字符出现频率相同,则哈夫曼编码一定会得到完全二叉树
使用 math.h 或 cmath 头文件中的函数,表达式 sin(90) 的结果为 1 。
在一个无向连通图中,从任意顶点开始进行深度优先遍历,最终得到的 DFS 生成树一定包含图中的所有顶 点。
城市规划
题目描述
A 国有n座城市,城市之间由m条双向道路连接,任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2....,n编号。第i(1≤i≤m)条双向道路连接城市ui与城市vi。
对于城市u和城市v而言,它们之间的连通度d(u,v)定义为从城市u出发到达城市 所需经过的双向道路的最少条数。由于道路是双向的,可以知道连通度满足d(u,v)=d(v,u),特殊地有d(u,u)=0。
现在 A 国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市,如果有多个满足条件的城市,则选取其中编号最小的城市。形式化地,你需要求出使得max1≤i≤nd(u,i)最小的u,若存在多个可能的u则选取其中最小的。
输入格式
第一行,两个正整数n,m,表示 A 国的城市数量与双向道路数量。
接下来m行,每行两个整数ui,vi,表示一条连接城市ui与城市vi的双向道路。
输出格式
输出一行,一个整数,表示建设难度最小的城市编号。如果有多个满足条件的城市,则选取其中编号最小的城市。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围
对于40的测试点,保证1≤n≤300 。
对于所有测试点,保证1≤n≤2000,1≤m≤2000,1≤ui,vi≤n。
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2005;
int n, m;
vector<int> e[N];
int d[N], mx[N], q[N];
void bfs(int u) {
for (int i = 1; i <= n; i++)
d[i] = n + 1;
d[u] = 0;
q[1] = u;
int ql = 1, qr = 1;
while (ql <= qr) {
int x = q[ql++];
for (auto y : e[x])
if (d[x] + 1 < d[y]) {
d[y] = d[x] + 1;
q[++qr] = y;
}
}
mx[u] = d[q[qr]];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
int ans = 1;
for (int i = 1; i <= n; i++) {
bfs(i);
if (mx[i] < mx[ans])
ans = i;
}
printf("%d\n", ans);
return 0;
}学习小组
时间限制:1.0 s
内存限制:512.0 MB

输入样例 1
输出样例 1
输入样例 2
输出样例 2

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 305;
int n;
int c[N], a[N];
int f[N][N];
int ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(c + 1, c + n + 1);
for (int i = n; i >= 1; i--)
for (int j = 1; j <= n; j++)
for (int k = i; k <= n; k++) {
int diff = 0;
if (i > 1)
diff = c[n - j + 1] - c[j];
f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff);
if (k == n)
ans = max(ans, f[j][k]);
}
printf("%d\n", ans);
return 0;
}连通图



#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 100005;
int n, m;
int f[N];
int ans;
// 带路径压缩的并查集查找
int getf(int u) {
if (!f[u])
return u;
return f[u] = getf(f[u]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
int fu = getf(u);
int fv = getf(v);
if (fu != fv) {
f[fu] = fv;
}
}
// 统计连通块数量:根节点数量
ans = 0;
for (int i = 1; i <= n; ++i) {
if (getf(i) == i)
ans++;
}
// 连通块数-1 = 最少需要添加的边(生成树边数)
printf("%d\n", ans - 1);
return 0;
}金币收集



#include <algorithm>
#include <cstdio>
using namespace std;
const int INF = 2e9;
const int N = 100005;
int n;
int x[N], t[N];
int p[N], f[N];
int mx;
// 排序规则:先按x升序,x相同则按t升序
bool cmp(int a, int b) {
if (x[a] != x[b])
return x[a] < x[b];
return t[a] < t[b];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x[i], &t[i]);
t[i] -= x[i]; // 转换为 t' = t - x
p[i] = i; // 下标数组,用于排序
f[i] = INF;
}
// 按x从小到大排序所有点
sort(p + 1, p + n + 1, cmp);
mx = 0;
f[0] = 0;
for (int i = 1; i <= n; ++i) {
int val = t[p[i]];
if (val < 0) continue; // 负数直接无法选取
// 二分查找最大长度r,满足 f[r] <= val
int l = 0, r = mx;
while (l < r) {
int mid = (l + r) / 2 + 1;
if (val < f[mid])
r = mid - 1;
else
l = mid;
}
// 可以拼出长度 r+1 的子序列
mx = max(mx, r + 1);
if (val < f[r + 1]) {
f[r + 1] = val;
}
}
printf("%d\n", mx);
return 0;
}线图
时间限制:1 s,内存限制:512 MB
【问题描述】
给定由 n 个结点与 m 条边构成的简单无向图 G,结点依次以 1、2、……、n 编号。简单无向图意味着 G 中不包含重边与自环。G 的线图 L(G) 通过以下方式构建:
(1)初始时线图 L(G) 为空。
(2)对于无向图 G 中的一条边,在线图 L(G) 中加入与之对应的一个结点。
(3)对于无向图 G 中两条不同的边 (u1, v1)、(u2, v2),若存在 G 中的结点同时连接这两条边(即 u1, v1之一与 u2, v2之一相同),则在线图 L(G) 中加入一条无向边,连接 (u1, v1)、(u2, v2) 在线图中对应的结点。
请你求出线图 L(G) 中所包含的无向边的数量。
【输入描述】
第一行,两个正整数 n、m,分别表示无向图 G 中的结点数与边数。
接下来 m 行,每行两个正整数 ui、vi,表示 G 中连接 ui、vi 的一条无向边。
【输出描述】
输出共一行,一个整数,表示线图 L(G) 中所包含的无向边的数量。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【样例解释1】

【数据范围】
对于60%测试点,保证 1 <= n、m <= 500。
对于所有测试点,保证 1 <= n、m <= 100000。
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int n, m, deg[N];
long long ans;
int main() {
cin >> n >> m;
while (m--) {
int u, v;
cin >> u >> v;
deg[u]++;
deg[v]++;
}
for (int i = 1; i <= n; i++)
ans += 1ll * deg[i] * (deg[i] - 1) / 2;
cout << ans;
return 0;
}调味平衡
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 准备了 n 种食材用来制作料理,这些食材依次以 1、2、……、n 编号,第 i 种食材的酸度为 ai,甜度为 bi。
对于每种食材,小 A 可以选择将其放入料理,或者不放入料理。料理的酸度 A 为放入食材的酸度之和,甜度 B 为放入食材的甜度之和。如果料理的酸度与甜度相等,那么料理的调味是平衡的。
过于清淡的料理并不好吃,因此小 A 想在满足料理调味平衡的前提下,合理选择食材,最大化料理的酸度与甜度之和。
你能帮他求出在调味平衡的前提下,料理酸度与甜度之和的最大值吗?
【输入描述】
第一行,一个正整数 n,表示食材种类数量。
接下来 n 行,每行两个正整数 ai、bi,表示食材的酸度与甜度。
【输出描述】
输出共一行,一个整数,表示在调味平衡的前提下,料理酸度与甜度之和的最大值。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于40%的测试点,保证 1 <= n <= 10,1 <= ai、bi <= 10。
对于另外20%的测试点,保证 1 <= n <= 50,1 <= ai、bi <= 10。
对于所有测试点,保证 1 <= n <= 100,1 <= ai、bi <= 500。
#include <iostream>
using namespace std;
const int N = 105;
const int C = 505;
const int D = N * C * 2;
int n, f[D];
int main() {
cin >> n;
for (int i = 0; i < D; i++)
f[i] = -1e9;
f[N * C] = 0;
while (n--) {
int a, b;
cin >> a >> b;
int x = a + b, y = a - b;
if (y <= 0) {
for (int i = -y; i < D; i++)
f[i + y] = max(f[i + y], f[i] + x);
} else {
for (int i = D - y - 1; i; i--)
f[i + y] = max(f[i + y], f[i] + x);
}
}
cout << f[N * C] << endl;
return 0;
}图上移动
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一张包含 个n 结点与 m 条边的无向图,结点以 1、2、……、n 标号。
小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。
对于每个结点 i(1<=i<=n),小 A 想知道从结点 i 出发恰好移动步1、2、……、k 之后,小 A 可能位于哪些结点。
由于满足条件的结点可能有很多,你只需要求出这些结点的数量。
【输入描述】
第一行,三个正整数 n、m、k,分别表示无向图的结点数与边数,最多移动的步数。
接下来 m 行,每行两个正整数 ui、vi,表示图中的一条连接结点 ui 与 vi 的无向边。
【输出描述】
共 n 行,第 i 行(1<=i<=n )包含 k 个整数,第 j 个整数( 1<=j<=k)表示从结点 i 出发恰好移动 j 步之后可能位于的结点数量。
【样例输入1】
【样例输出1】
【数据范围】
对于 20% 的测试点,保证 k=1。
对于另外 20% 的测试点,保证 1<=n<=50,1<=m<=50 。
对于所有测试点,保证 1<=n<=500,1<=m<=500 ,1<=k<=20 ,1<=ui、vi<=n 。
#include <cstdio>
using namespace std;
const int K = 25;
const int N = 505;
const int E = N << 1;
int n, m, k;
int h[N], to[E], nx[E], et;
int f[K][N][N];
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[u];
h[u] = et;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
ae(u, v);
ae(v, u);
}
for (int i = 1; i <= n; i++)
f[0][i][i] = 1;
for (int t = 1; t <= k; t++)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
if (f[t - 1][x][y])
for (int i = h[y]; i; i = nx[i])
f[t][x][to[i]] = 1;
for (int i = 1; i <= n; i++) {
for (int t = 1; t <= k; t++) {
int ans = 0;
for (int j = 1; j <= n; j++)
ans += f[t][i][j];
printf("%d%c", ans, " \n"[t == k]);
}
}
return 0;
}等价消除
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一个仅包含小写英文字母的字符串 。
对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。
小 A 想知道 S 有多少子串是可以被等价消除的。
一个字符串 S' 是 S 的子串,当且仅当删去 S 的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 S'。
【输入描述】
第一行,一个正整数 |S|,表示字符串 S 的长度。
第二行,一个仅包含小写英文字母的字符串 S。
【输出描述】
一行,一个整数,表示答案。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 S 中仅包含 a 和 b 两种字符。
对于另外 20% 的测试点,保证 1<=|S|<=2000。
对于所有测试点,保证 1<=|S|<=200000。
#include <cstdio>
#include <map>
using namespace std;
const int N = 2e5 + 5;
int n;
char s[N];
map <int, int> m;
long long ans;
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
int v = 0;
m[v]++;
for (int i = 1; i <= n; i++) {
v ^= 1 << (s[i] - 'a');
ans += m[v];
m[v]++;
}
printf("%lld\n", ans);
return 0;
}武器购买
时间限制:1.0 s
内存限制:512.0 MB
题面描述
商店里有 n 个武器,第 i 个武器的强度为 pi,花费为 ci。
小杨想要购买一些武器,满足这些武器的总强度不小于 P ,总花费不超过 Q ,小杨想知道是否存在满足条件的购买方案,如果有,最少花费又是多少。
输入格式
第一行包含一个正整数 t ,代表测试数据组数。
对于每组测试数据,第一行包含三个正整数 n,P,Q,含义如题面所示。
之后 n 行,每行包含两个正整数 pi,ci,代表武器的强度和花费。
输出格式
对于每组测试数据,如果存在满足条件的购买方案,输出最少花费,否则输出 -1。
输入样例
输出样例

对于全部数据,保证有 1≤t≤10,1≤n≤100,1≤pi,ci,P,Q≤5×104。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[50010];
ll solve(int n, int P, int Q, vector<pair<int, int>>& weapons) {
dp[0] = 0;
for (auto& weapon : weapons) {
int p = weapon.first;
int c = weapon.second;
for (int j = Q; j >= c; --j) {
if (dp[j - c]>=0) {
dp[j] = max(dp[j], dp[j - c] + p);
}
}
}
for (int j = 0; j <= Q; ++j) {
if (dp[j] >= P) {
return j;
}
}
return -1;
}
int main() {
int t;
cin>>t;
while(t--){
int n, P, Q;
cin >> n >> P >> Q;
memset(dp,-0x3f,sizeof dp);
vector<pair<int, int> > weapons(n);
for (int i = 0; i < n; ++i) {
cin >> weapons[i].first >> weapons[i].second;
}
cout << solve(n, P, Q, weapons) << "\n";
}
return 0;
}燃烧
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n 。节点 i 的权值为 ai。
小杨可以选择一个初始节点引燃,每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃,火焰会在节点间扩散直到不会有新的节点被引燃。
小杨想知道在合理选择初始节点的情况下,最多可以燃烧多少个节点。
输入格式
第一行包含一个正整数 n ,代表节点数量。
第二行包含 n 个正整数 a1,a2,...,an,代表节点权值。
之后 n−1 行,每行包含两个正整数 ui,vi,代表存在一条连接节点 ui和 vi的边。
输出格式
输出一个正整数,代表最多燃烧的节点个数。
输入样例
输出样例

对于全部数据,保证有 1≤n≤105,1≤ai≤106。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int sum[N];
int down[N];
vector<int> g[N];
void dfs_down(int x,int fa){
down[x]=1;
for(int i:g[x]){
if(i!=fa){
dfs_down(i,x);
if(a[x]>a[i]){
down[x]+=down[i];
}
}
}
}
void dfs_sum(int x,int fa){
if(a[x]>a[fa]){
sum[x]+=sum[fa]+down[fa];
}
for(int i:g[x]){
if(i!=fa){
dfs_sum(i,x);
}
}
}
int main(){
int n;
cin>>n;
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);
}
dfs_down(1,0);
dfs_sum(1,0);
int mx = 0;
for(int i=1;i<=n;i++){
mx = max(mx,sum[i]+down[i]);
}
cout<<mx<<"\n";
}