跳到主要内容
第十四届蓝桥杯 C/C++ 省赛 B 组题解 | 极客日志
C++ 算法
第十四届蓝桥杯 C/C++ 省赛 B 组题解 综述由AI生成 第十四届蓝桥杯 C/C++ 省赛 B 组包含十道题目,涵盖日期统计、信息熵计算、冶炼金属转换率、飞机降落调度、接龙数列动态规划、岛屿连通性判断、字串简写前缀和优化、整数删除堆与链表优化、景区导游树上前缀和与 LCA 倍增、砍树树上差分等知识点。文章提供了从暴力枚举到优化的多种代码实现,涉及搜索、DP、前缀和、链表、堆、树结构等算法基础,适合准备竞赛的开发者参考。
GitMaster 发布于 2026/3/16 更新于 2026/5/19 29 浏览第十四届蓝桥杯 C/C++ 省赛 B 组题解
一共两道填空题,八道程序设计题。
A:日期统计(5 分)
题意:
小蓝现在有一个长度为 100 的数组,数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示:
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
现在他想要从这个数组中寻找一些满足以下条件的子序列:
子序列的长度为 8;
这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期,并且要求这个日期是 2023 年中的某一天的日期,例如 20230902,20231223。yyyy 表示年份,mm 表示月份,dd 表示天数,当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。
解法:
先按照题目要求找到第一个 2023 的位置:
5 6 8 6 9 1 6 1 -2- 4 9 1 9 8 2 3 6 4 7 7 5 9 5 -0- 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 -2- 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 -3- 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
删去这个位置之前的所有数
3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
在剩余的数上枚举月份和日期。
注意到剩余的数不会产生 30 日和 31 日,也不会产生 2 月 29 日。所以不需要特判。
#include <bits/stdc++.h>
using namespace std;
int a[50 ];
bool f[2 ][10 ][3 ][10 ];
int main () {
int n=0 ;
int x=0 ;
while (x!=-1 ){ cin>>x; a[++n]=x;}
--n;
int ans=0 ;
for (int i=1 ;i<=n;i++){
(a[i]> ) ;
( j=i ;j<=n;j++){
(a[i]== &&a[j]== ) ;
(a[i]== &&a[j]> ) ;
( k=j ;k<=n;k++){
(a[k]> ) ;
( m=k ;m<=n;m++){
(a[k]== &&a[m]== ) ;
(f[a[i]][a[j]][a[k]][a[m]]) ;
++ans; f[a[i]][a[j]][a[k]][a[m]]= ;
}
}
}
}
cout<<ans;
;
}
if
1
continue
for
int
+1
if
0
0
continue
if
1
2
continue
for
int
+1
if
2
continue
for
int
+1
if
0
0
continue
if
continue
1
return
0
B:01 串的熵(5 分)
题意: 信息熵是信息论中的一个重要概念,用来量化信息的不确定性。在 01 串中,信息熵可以用来衡量 0 和 1 出现的概率分布。对于一个长度为 n 的 01 串,其信息熵 H(S) 的计算公式为:
H(S) = -\sum p(x_i) \log_2(p(x_i))
其中,p(0) 和 p(1) 分别表示 0 和 1 在串中出现的概率。
H(S) = -\frac{1}{3}\log_2(\frac{1}{3}) - \frac{2}{3}\log_2(\frac{2}{3}) - \frac{2}{3}\log_2(\frac{2}{3}) = 1.3083
假设我们有一个长度为 23333333 的 01 串,其信息熵为 11625907.5798,并且 0 的出现次数比 1 少。我们需要计算这个 01 串中 0 出现的次数。
解法: 令 n = 23333333
假设 0 出现的次数是 a
那么 1 出现的次数 b = n - a
H(S) = -a * (a/n) * log2(a/n) - b * (b/n) * log2(b/n)
枚举 a 使得 H(S) = 11625907.5798 即可
#include <bits/stdc++.h>
using namespace std;
int main () {
double n=23333333 ;
double ans=11625907.5798 ;
double mn=ans,mi=-1 ;
for (int i=1 ;i<n;i++){
double a=i;
double b=n-a;
double anss=-(a*(a/n)*log2 (a/n)+b*(b/n)*log2 (b/n));
anss-=ans;
if (anss<0 ) anss=-anss;
if (anss<mn){ mn=anss; mi=i;}
}
printf ("%.8lf %.0lf" ,mn,mi);
return 0 ;
}
C:冶炼金属(10 分)
题目描述 小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V,V 是一个正整数,这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X,当普通金属 O 的数目不足 V 时,无法继续冶炼。
现在给出了 N 条冶炼记录,每条记录中包含两个整数 A 和 B,这表示本次投入了 A 个普通金属 O,最终冶炼出了 B 个特殊金属 X。每条记录都是独立的,这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
根据这 N 条冶炼记录,请你推测出转换率 V 的最小值和最大值分别可能是多少,题目保证评测数据不存在无解的情况。
输入格式 接下来输入 N 行,每行两个整数 A,B,含义如题目所述。
输出格式 输出两个整数,分别表示 V 可能的最小值和最大值,中间用空格分开。
输入输出样例 #1
输入 #1
输出 #1
说明/提示 当 V=20 时,有:⌊75/20⌋=3, ⌊53/20⌋=2, ⌊59/20⌋=2,可以看到符合所有冶炼记录。
当 V=25 时,有:⌊75/25⌋=3, ⌊53/25⌋=2, ⌊59/25⌋=2,可以看到符合所有冶炼记录。
且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。
对于 100% 的评测用例,1≤N≤10^4,1≤B≤A≤10^9。
解法: #include <bits/stdc++.h>
using namespace std;
int main () {
int n; cin>>n;
vector<int >a (n+1 ),b (n+1 );
for (int i=1 ;i<=n;i++){ cin>>a[i]>>b[i];}
int l=-1 ,r=-1 ;
for (int v=1 ;;v++){
bool f=0 ;
for (int i=1 ;i<=n;i++){
if (a[i]/v==b[i])continue ; f=1 ;break ;
}
if (f){if (l!=-1 )break ;continue ;}
if (l==-1 ) l=v; r=v;
}
cout<<l<<' ' <<r<<'\n' ;
return 0 ;
}
不过还是考虑如何优化,经过分析可以发现:对于给出的每组 A 和 B,Vmax=⌊A/B⌋,Vmin=⌊A/(B+1)⌋+1。
如果求出每组 Vmax 的最小值,和每组 Vmin 的最大值,就是最终答案。
#include <bits/stdc++.h>
using namespace std;
int main () {
int n; cin>>n;
int l=-1 ,r=1000000000 ;
for (int i=1 ;i<=n;i++){
int a,b; cin>>a>>b;
l=max (l,a/(b+1 )+1 ); r=min (r,a/b);
}
cout<<l<<' ' <<r<<'\n' ;
return 0 ;
}
另外本题还有通过两次二分 V,分别求出 V 的最小值和最大值的写法。可以自己尝试,此处不再赘述。
D:飞机降落(10 分)
题目描述 N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 Di 个单位时间,即它最早可以于 Ti 时刻开始降落,最晩可以于 Ti+Di 时刻开始降落。降落过程需要 Li 个单位时间。
一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
输入格式 以下 N 行,每行包含三个整数 Ti,Di,Li。
输出格式 对于每组数据,输出 YES 或者 NO,代表是否可以全部安全降落。
输入输出样例 #1
输入 #1 2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
输出 #1
说明/提示 对于第一组数据,可以安排第 3 架飞机于 0 时刻开始降落,20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落,30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落,40 时刻完成降落。
对于第二组数据,无论如何安排,都会有飞机不能及时降落。
对于 100% 的数据,1≤T≤10,1≤N≤10,0≤Ti,Di,Li≤10^5。
解法: #include <bits/stdc++.h>
using namespace std;
int n;
int t[11 ],d[11 ],l[11 ];
bool f;
bool v[11 ];
void dfs (int ti,int k) {
if (k==n){ f=1 ;return ;}
for (int i=1 ;i<=n;i++){
if (v[i])continue ;
if (t[i]+d[i]<ti)return ;
v[i]=1 ;
dfs (max (ti,t[i])+l[i],k+1 );
v[i]=0 ;
if (f)break ;
}
}
int main () {
int m; cin>>m;
while (m--){
f=0 ; cin>>n;
for (int i=1 ;i<=n;i++){ cin>>t[i]>>d[i]>>l[i];}
dfs (-1 ,0 );
if (f)puts ("YES" );else puts ("NO" );
}
return 0 ;
}
E:接龙数列(15 分)
题目描述 对于一个长度为 K 的整数数列:A1,A2,…,AK,我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字(2≤i≤K)。
例如 12,23,35,56,61,11 是接龙数列;12,23,34,56 不是接龙数列,因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1,A2,…,AN,请你计算最少从中删除多少个数,可以使剩下的序列是接龙序列?
输入格式
输出格式
输入输出样例 #1
输入 #1
输出 #1
说明/提示 删除 22,剩余 11,121,12,2023 是接龙数列。
对于 100% 的数据,1≤N≤10^5,1≤Ai≤10^9。所有 Ai 保证不包含前导 0。
解法: 首先可以发现对于每个 Ai 只有最左和最右两个数字有用,所以输入时可以直接把中间的去掉。
又因为删去最少的数字,和保留最多的数字是一样的,所以可以转化为求最长的接龙数列。
#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011 ],r[100011 ];
void f (int i,int x) { r[i]=x%10 ;while (x>9 ){ x/=10 ;} l[i]=x;}
int ans=0 ;
void dfs (int x,int k) { ans=max (ans,k);for (int i=x+1 ;i<=n;i++){if (x==0 ||l[i]==r[x]){dfs (i,k+1 );}}}
int main () { cin>>n;for (int i=1 ;i<=n;i++){int x; cin>>x;f (i,x);}dfs (0 ,0 ); cout<<n-ans;return 0 ;}
时间复杂度:O(2^n)
可以通过 20% 的数据。
重新思考这道题,用 s(x) 表示 n=x 时最长接龙序列长度。
从 n=1 时开始考虑,此时最长接龙序列长度显然为 1。即 s(1)=1
接下来考虑 n 增加 1 时,最长接龙序列的变化。
如果增加的数不能和前面的数接龙,那么答案显然不变,即 s(n+1)=s(n)。
如果可以和前面的某个数假设为 Ai 接龙,那答案应该取 s(n) 和 s(i)+1 中的最大值。
即 s(n+1)=max(s(n),s(i)+1)
#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011 ],r[100011 ];
void f (int i,int x) { r[i]=x%10 ;while (x>9 ){ x/=10 ;} l[i]=x;}
int s[100011 ];
int ans;
int main () { cin>>n;for (int i=1 ;i<=n;i++){int x; cin>>x;f (i,x); s[i]=1 ;}
for (int i=1 ;i<=n;i++){
for (int j=1 ;j<i;j++){
if (l[i]==r[j]){ s[i]=max (s[i],s[j]+1 );}
}
} ans=0 ;
for (int i=1 ;i<=n;i++){ ans=max (ans,s[i]);}
cout<<n-ans;return 0 ;}
时间复杂度:O(n^2)
可以通过 50% 的数据。
用 l[i] 表示 Ai 最左边的数,用 r[i] 表示 Ai 最右边的数。
那么 Ai 能更新接龙序列一定以 l[i] 结尾。
更新完序列变成以 r[i] 结尾。
所以如果用 s[k] 表示以数字 k 结尾的最长序列长度。
枚举到 Ai 时,s[r[i]]=max(s[r[i]],s[l[i]]+1)
#include <bits/stdc++.h>
using namespace std;
int n;
int l[100011 ],r[100011 ];
void f (int i,int x) { r[i]=x%10 ;while (x>9 ){ x/=10 ;} l[i]=x;}
int s[100011 ];
int ans;
int main () { cin>>n;for (int i=1 ;i<=n;i++){int x; cin>>x;f (i,x);}
for (int i=1 ;i<=n;i++){ s[r[i]]=max (s[r[i]],s[l[i]]+1 );}
for (int i=0 ;i<=9 ;i++){ ans=max (ans,s[i]);}
cout<<n-ans;return 0 ;}
F:岛屿个数(15 分)
题目描述 小蓝得到了一副大小为 M×N 的格子地图,可以将其视作一个只包含字符 0(代表海水)和 1(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。
在岛屿 AAA 所占据的格子中,如果可以从中选出 k 个不同的格子,使得他们的坐标能够组成一个这样的排列:(x0,y0),(x1,y1),…,(xk−1,yk−1),其中 (x(i+1) mod k,y(i+1) mod k) 是由 (xi,yi) 通过上/下/左/右移动一次得来的(0≤i≤k−1),此时这 k 个格子就构成了一个「环」。如果另一个岛屿 BBB 所占据的格子全部位于这个「环」内部,此时我们将岛屿 BBB 视作是岛屿 AAA 的子岛屿。若 BBB 是 AAA 的子岛屿,CCC 又是 BBB 的子岛屿,那 CCC 也是 AAA 的子岛屿。
请问这个地图上共有多少个岛屿?在进行统计时不需要统计子岛屿的数目。
输入格式 接下来输入 T 组数据。对于每组数据,第一行包含两个用空格分隔的整数 M,N 表示地图大小;接下来输入 M 行,每行包含 N 个字符,字符只可能是 0 或 1。
输出格式
输入输出样例 #1
输入 #1 2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
输出 #1
说明/提示 对于第一组数据,包含两个岛屿,下面用不同的数字进行了区分:
01111
11001
10201
10001
11111
岛屿 2 在岛屿 1 的「环」内部,所以岛屿 2 是岛屿 1 的子岛屿,答案为 1。
对于第二组数据,包含三个岛屿,下面用不同的数字进行了区分:
111111
100001
020301
100001
111111
注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿,因为岛屿 1 和岛屿 2 中均没有「环」。
对于 100% 的评测用例,1≤T≤10,1≤M,N≤50。
解法: 本题可以分为两部分解决:1:判断岛屿个数,2:判断一个岛屿是否为子岛屿。
观察题目描述,如果一个岛屿不是子岛屿,那么一定和地图最边界的 0 相接。
#include <bits/stdc++.h>
using namespace std;
int n,m;
int s[55 ][55 ];
int dx1[8 ]={-1 ,-1 ,-1 ,0 ,+1 ,+1 ,+1 ,0 };
int dy1[8 ]={-1 ,0 ,+1 ,+1 ,+1 ,0 ,-1 ,-1 };
bool ck1 (int x,int y) {if (x<0 ||y<0 ||x>n+1 ||y>m+1 ||s[x][y]==-1 )return 0 ;return 1 ;}
bool v[5005 ];
void dfs1 (int x,int y) { s[x][y]=-1 ;int nx,ny;for (int i=0 ;i<8 ;i++){ nx=x+dx1[i]; ny=y+dy1[i];if (ck1 (nx,ny)){int a=s[nx][ny];if (a!=0 ){ v[a]=1 ;}else {dfs1 (nx,ny);}}}}
int k;
int dx2[4 ]={-1 ,0 ,+1 ,0 };
int dy2[4 ]={0 ,+1 ,0 ,-1 };
bool ck2 (int x,int y) {if (x<1 ||y<1 ||x>n||y>m||s[x][y]!=1 )return 0 ;return 1 ;}
void dfs2 (int x,int y) { s[x][y]=k;int nx,ny;for (int i=0 ;i<4 ;i++){ nx=x+dx2[i]; ny=y+dy2[i];if (ck2 (nx,ny)){dfs2 (nx,ny);}}}
int main () {
int t; cin>>t;
while (t--){
cin>>n>>m;
for (int i=1 ;i<=n;i++){
for (int j=1 ;j<=m;j++){
char ch; cin>>ch; s[i][j]=ch-'0' ;
}
}
k=2 ;
int ans=0 ;
for (int i=1 ;i<=n;i++){
for (int j=1 ;j<=m;j++){
if (s[i][j]==1 ){dfs2 (i,j);++k;}
}
}
dfs1 (0 ,0 );
for (int i=2 ;i<k;i++){ ans+=v[i];}
cout<<ans<<'\n' ;
memset (s,0 ,sizeof (s));memset (v,0 ,sizeof (v));
}
return 0 ;
}
G:字串简写(20 分)
题目描述 程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如 internationalization 简写成 i18n,Kubernetes(注意连字符不是字符串的一部分)简写成 K8s,Lanqiao 简写成 L5o 等。
在本题中,我们规定长度大于等于 K 的字符串都可以采用这种简写方法 (长度小于 K 的字符串不配使用这种简写)。
给定一个字符串 S 和两个字符 c1 和 c2,请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写?
输入格式 第二行包含一个字符串 S 和两个字符 c1 和 c2。
输出格式
输入输出样例 #1
输入 #1
输出 #1
说明/提示 [abab] abdb [ababab] db [abababdb] ab[abab] db ab[ababdb] abab[abdb]
对于 100% 的数据,2≤K≤|S|≤5×10^5。S 只包含小写字母。c1 和 c2 都是小写字母。
|S| 代表字符串 S 的长度。
解法: 直接对于每个 c1,枚举整个数组找到符合条件的 c2 并计数。
#include <bits/stdc++.h>
using namespace std;
int main () {
int k; cin>>k; string s; cin>>s;
char c1,c2; cin>>c1>>c2;
int n=s.size ();
long long ans=0 ;
for (int i=0 ;i<n;i++){
if (s[i]==c1){
for (int j=i+k-1 ;j<n;j++){
if (s[j]==c2){++ans;}
}
}
}
cout<<ans<<'\n' ;
return 0 ;
}
使用前缀和优化,用一个数组记录 c1 的前缀数量。
#include <bits/stdc++.h>
using namespace std;
int main () {
int k; cin>>k; string s; cin>>s;
char c1,c2; cin>>c1>>c2;
int n=s.size ();
vector<int >a (n);
long long ans=0 ;
for (int i=0 ;i<n;i++){
if (s[i]==c1){ a[i]++;}
if (i) a[i]+=a[i-1 ];
if (s[i]==c2){
int l=i-k+1 ;
if (l>=0 ){ ans+=a[l];}
}
}
cout<<ans<<'\n' ;
return 0 ;
}
需要注意,本题答案可能非常大超过 int 范围,所以要使用 long long 型存答案。
H:整数删除(20 分)
题目描述 给定一个长度为 N 的整数数列:A1,A2,…,AN。你要重复以下操作 K 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。并把与它相邻的整数加上被删除的数值。
输入格式 第二行包含 N 个整数,A1,A2,A3,…,AN。
输出格式 输出 N-K 个整数,中间用一个空格隔开,代表 K 次操作后的序列。
输入输出样例 #1
输入 #1
输出 #1
说明/提示 数列变化如下,中括号里的数是当此操作中被选择的数:
[1] 4 2 8 7
5 [2] 8 7
7 [10] 7
17 7
对于 100% 的数据,1≤K<N≤5×10^5,0≤Ai≤10^8。
解法: #include <bits/stdc++.h>
using namespace std;
int main () {
int n,k; cin>>n>>k;
vector<long long >s (n+1 );
for (int i=1 ;i<=n;i++){ cin>>s[i];}
while (k--){
long long mn=-1 ;int p=-1 ;
for (int i=1 ;i<=n;i++){
if (s[i]==-1 )continue ;
if (p==-1 || s[i]<mn){ p=i; mn=s[i];}
}
s[p]=-1 ;
for (int i=p-1 ;i>=1 ;i--){if (s[i]!=-1 ){ s[i]+=mn;break ;}}
for (int i=p+1 ;i<=n;i++){if (s[i]!=-1 ){ s[i]+=mn;break ;}}
}
for (int i=1 ;i<=n;i++){
if (s[i]==-1 )continue ; cout<<s[i]<<' ' ;
}
return 0 ;
}
尝试优化,每次操作由三部分组成,一是找到最小值,二是删除最小值,三是最小值两侧数据增加。
改变最小值两侧数据,在链表中很好处理,在堆中处理起来很麻烦。
所以在堆中改变数据这个操作可以在找最小值这一步完成。
如果和链表中的数据不同再进行处理,否则不需要处理。
#include <bits/stdc++.h>
using namespace std;
struct lb {int l,r;long long x;}s[500005 ];
#define pl pair<long long,int>
#define xx first
#define yy second
priority_queue<pl,vector<pl>,greater<pl>> q;
int main () {
int n,k; cin>>n>>k;
s[0 ].l=-1 ; s[0 ].r=1 ; s[0 ].x=-1 ;
for (int i=1 ;i<=n;i++){
cin>>s[i].x; s[i].l=i-1 ; s[i].r=i+1 ; q.push ({s[i].x,i});
}
s[n].r=-1 ;
for (int i=1 ;i<=k;i++){
long long x=q.top ().xx;int p=q.top ().yy;
while (s[p].x!=x){ x=s[p].x; q.pop (); q.push ({x,p}); x=q.top ().xx; p=q.top ().yy;}
q.pop ();
s[s[p].l].x+=x; s[s[p].r].x+=x;
s[s[p].l].r=s[p].r; s[s[p].r].l=s[p].l;
s[p].l=-1 ; s[p].r=-1 ;
}
int p=0 ;
while (s[p].r!=-1 ){ p=s[p].r; cout<<s[p].x<<' ' ;
}
return 0 ;
}
I:景区导游(25 分)
题目描述 某景区一共有 N 个景点,编号 1 到 N。景点之间共有 N−1 条双向的摆渡车线路相连,形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行,需要花费一定的时间。
小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 K 个景点:A1,A2,…,AK。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K−1 个景点。具体来说,如果小明选择跳过 Ai,那么他会按顺序带游客游览 A1,A2,…,Ai−1,Ai+1,…,AK(1≤i≤K)。
请你对任意一个 Ai,计算如果跳过这个景点,小明需要花费多少时间在景点之间的摆渡车上?
输入格式 以下 N−1 行,每行包含 3 个整数 u,v,t,代表景点 u 和 v 之间有摆渡车线路,花费 t 个单位时间。
最后一行包含 K 个整数 A1,A2,…,AK 代表原定游览线路。
输出格式 输出 K 个整数,其中第 i 个代表跳过 Ai 之后,花费在摆渡车上的时间。
输入输出样例 #1
输入 #1 6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1
输出 #1
说明/提示 当跳过 2 时,路线是 6→5→1,其中 6→5 花费时间 3+2+2=7,5→1 花费时间 2+1=3,总时间花费 10。
当跳过 6 时,路线是 2→5→1,其中 2→5 花费时间 1+1+2=4,5→1 花费时间 2+1=3,总时间花费 7。
当跳过 5 时,路线是 2→6→1,其中 2→6 花费时间 1+1+2+3=7,6→1 花费时间 3+2+1=6 ,总时间花费 13。
当跳过 1 时,路线时 2→6→5,其中 2→6 花费时间 1+1+2+3=7,6→5 花费时间 3+2+2=7 ,总时间花费 14。
对于 100% 的数据,2≤K≤N≤10^5,1≤u,v,Ai≤N,1≤t≤10^5。保证 Ai 两两不同。
解法: 首先题目中没有规定树的根结点,而且根结点不影响答案,所以可以任意选择一个点作为根结点,这里选择 1 号结点。
接下来分析,要求出答案需要完成什么操作,可以发现只需要实现一个函数,来求出两个结点之间的最短距离。
根据树的结构,x 到 y 的距离,可以分解成,x 到根结点的距离加上 y 到根节点的距离,减去二倍的 x 和 y 到根结点的公共距离。
x 和 y 到根结点的公共距离,和某个点到根结点的距离是相同的,这个点叫做 x 和 y 的最近公共祖先(LCA)。
为了方便理解,这里用自然语言阐述一下最近公共祖先怎么求。
假设要求 x 和 y 的最近公共祖先,因为 x 和 y 的顺序不影响结果,为了方便说明不妨令 x 的深度小于等于 y 的深度。也就是在树的结构中,x 不在 y 的下方。
首先,不断找 y 的父结点作为新的 y 直到 y 和 x 深度一样。这一步是因为,x 和 y 的最近公共祖先,深度一定不大于 x。
如果此时 x 和 y 相等,说明 x 和 y 的最近公共祖先就是 x,即 y 在 x 的子树里。
如果此时 x 和 y 不相等,那么就同时找 x,y 两个结点的父结点作为新的,x 和 y,直到两点相等,此时就找到了,x 和 y 的最近公共祖先。
理解了如何求 x 和 y 的最近公共祖先,按照题意依次求出答案即可。
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long ,int >>s[100005 ];
#define xx first
#define ww second
int h[100005 ];
long long d[100005 ];
int f[100005 ];
void dfs (int u) {
for (auto v:s[u]){
if (h[v.xx])continue ; h[v.xx]=h[u]+1 ; f[v.xx]=u; d[v.xx]=d[u]+v.ww;
dfs (v.xx);
}
}
int lca (int x,int y) {
if (h[x]>h[y])swap (x,y);
while (h[x]!=h[y]){ y=f[y];}
if (x==y){return x;}
while (x!=y){ x=f[x]; y=f[y];}
return x;
}
long long dist (int x,int y) {
if (x==0 ||y==0 )return 0 ;
int m=lca (x,y);
long long sum=d[x]+d[y]-2 *d[m];
return sum;
}
int main () {
int n,k; cin>>n>>k;
for (int i=1 ;i<n;i++){
int u,v,w; cin>>u>>v>>w; s[u].push_back ({v,w}); s[v].push_back ({u,w});
}
h[1 ]=1 ;dfs (1 );
vector<int >p (k+1 );
for (int i=1 ;i<=k;i++){ cin>>p[i];}
long long ans=0 ;
for (int i=1 ;i<=k;i++){
ans=0 ;int l=0 ;
for (int j=1 ;j<=k;j++){
if (i==j)continue ; ans+=dist (l,p[j]); l=p[j];
}
cout<<ans<<' ' ;
}
return 0 ;
}
思考如何优化,注意到跳过 Ai 后的距离,可以根据不跳过的原始总距离更改得到。
假如原始总距离为 ans,那么跳过 Ai 后的距离,就是 ans 减去 Ai−1 到 Ai 的距离 和 Ai 到 Ai+1 的距离,加上 Ai−1 到 Ai+1 的距离。
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long ,int >>s[100005 ];
#define xx first
#define ww second
int h[100005 ];
long long d[100005 ];
int f[100005 ];
void dfs (int u) {
for (auto v:s[u]){
if (h[v.xx])continue ; h[v.xx]=h[u]+1 ; f[v.xx]=u; d[v.xx]=d[u]+v.ww;
dfs (v.xx);
}
}
int lca (int x,int y) {
if (h[x]>h[y])swap (x,y);
while (h[x]!=h[y]){ y=f[y];}
if (x==y){return x;}
while (x!=y){ x=f[x]; y=f[y];}
return x;
}
long long dist (int x,int y) {
if (x==0 ||y==0 )return 0 ;
int m=lca (x,y);
long long sum=d[x]+d[y]-2 *d[m];
return sum;
}
int main () {
int n,k; cin>>n>>k;
for (int i=1 ;i<n;i++){
int u,v,w; cin>>u>>v>>w; s[u].push_back ({v,w}); s[v].push_back ({u,w});
}
h[1 ]=1 ;dfs (1 );
vector<int >p (k+1 );
for (int i=1 ;i<=k;i++){ cin>>p[i];}
long long ans=0 ;
for (int i=1 ;i<k;i++){ ans+=dist (p[i],p[i+1 ]);}
for (int i=1 ;i<=k;i++){
long long sum=ans; sum-=dist (p[i-1 ],p[i]); sum-=dist (p[i],p[i+1 ]); sum+=dist (p[i-1 ],p[i+1 ]);
cout<<sum<<' ' ;
}
return 0 ;
}
接下来,优化 LCA(最近公共祖先)的求法,这里给出最容易理解的倍增法。
倍增法和直接求的区别是,不是只记录每个结点的父结点,而是用 fi,j 记录,从 i 结点向上找 2^j 次父结点后的结点。
同时根据 f 数组的含义也很容易推出 f 数组的求法:
显然 fi,0 代表 i 的父结点,之后,fi,j=ff_{i,j-1},j-1,这很好理解,因为 2^j=2^{j-1}+2^{j-1},所以从 i 向上找 2^j 次父结点的结果和从 i 向上找 2^{j-1} 次之后再找 2^{j-1} 次父结点的结果一致。
在预处理完 f 数组之后,把求 LCA 过程中,找父结点的操作改为使用 f 数组找,可以将原本 O(n) 的时间复杂度降低至 O(log n)
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long ,int >>s[100005 ];
#define xx first
#define ww second
int h[100005 ];
long long d[100005 ];
int f[100005 ][25 ];
void dfs (int u) {
for (int i=1 ;i<=24 ;i++){ f[u][i]=f[f[u][i-1 ]][i-1 ];}
for (auto v:s[u]){
if (h[v.xx])continue ; h[v.xx]=h[u]+1 ; f[v.xx][0 ]=u; d[v.xx]=d[u]+v.ww;
dfs (v.xx);
}
}
int lca (int x,int y) {
if (h[x]>h[y])swap (x,y);
for (int i=24 ;i>=0 ;i--){if (h[f[y][i]]>=h[x]){ y=f[y][i];}}
if (x==y){return x;}
for (int i=24 ;i>=0 ;i--){if (f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i];}}
return f[x][0 ];
}
long long dist (int x,int y) {
if (x==0 ||y==0 )return 0 ;
int m=lca (x,y);
long long sum=d[x]+d[y]-2 *d[m];
return sum;
}
int main () {
int n,k; cin>>n>>k;
for (int i=1 ;i<n;i++){
int u,v,w; cin>>u>>v>>w; s[u].push_back ({v,w}); s[v].push_back ({u,w});
}
h[1 ]=1 ;dfs (1 );
vector<int >p (k+1 );
for (int i=1 ;i<=k;i++){ cin>>p[i];}
long long ans=0 ;
for (int i=1 ;i<k;i++){ ans+=dist (p[i],p[i+1 ]);}
for (int i=1 ;i<=k;i++){
long long sum=ans; sum-=dist (p[i-1 ],p[i]); sum-=dist (p[i],p[i+1 ]); sum+=dist (p[i-1 ],p[i+1 ]);
cout<<sum<<' ' ;
}
return 0 ;
}
J:砍树(25 分)
题目描述 给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1,b1),(a2,b2),…,(am,bm),其中 ai 互不相同,bi 互不相同,ai≠bj(1≤i,j≤m)。
小明想知道是否能够选择一条树上的边砍断,使得对于每个 (ai,bi) 满足 ai 和 bi 不连通,如果可以则输出应该断掉的边的编号 (编号按输入顺序从 1 开始),否则输出 -1。
输入格式 后面 n−1 行,每行两个正整数 xi,yi 表示第 i 条边的两个端点。
输出格式 一行一个整数,表示答案,如有多个答案,输出编号最大的一个。
输入输出样例 #1
输入 #1 6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
输出 #1
说明/提示 断开第 2 条边后形成两个连通块:{3,4},{1,2,5,6},满足 3 和 6 不连通,4 和 5 不连通。
断开第 4 条边后形成两个连通块:{1,2,3,4},{5,6},同样满足 3 和 6 不连通,4 和 5 不连通。
对于 100% 的数据,保证 1<n≤10^5,1≤m≤n/2。
解法: 思考在树上如果一条边去掉以后可以使得 a 和 b 不连通这条边应该有什么特点,显然这条边一定在 a 和 b 的最短路径上。
根据这点,如果存在某个边被 m 组数对代表的路径经过 m 次,那么这个边就是符合题意的答案。
#include <bits/stdc++.h>
using namespace std;
vector<pair<int ,int >>s[100005 ];
#define xx first
#define ii second
int id[100005 ];
int f[100005 ];
int h[100005 ];
int cnt[100005 ];
void dfs (int u) {
for (auto v:s[u]){
if (h[v.xx])continue ; h[v.xx]=h[u]+1 ; f[v.xx]=u; id[v.xx]=v.ii;
dfs (v.xx);
}
}
void sol (int x,int y) {
if (h[x]>h[y])swap (x,y);
while (h[x]!=h[y]){ cnt[id[y]]++; y=f[y];}
if (x==y)return ;
while (x!=y){ cnt[id[x]]++; cnt[id[y]]++; x=f[x]; y=f[y];}
}
int main () {
int n,k; cin>>n>>k;
for (int i=1 ;i<n;i++){
int u,v; cin>>u>>v; s[u].push_back ({v,i}); s[v].push_back ({u,i});
}
h[1 ]=1 ;dfs (1 );
for (int i=1 ;i<=k;i++){
int x,y; cin>>x>>y;sol (x,y);
}
for (int i=n-1 ;i>=1 ;i--){
if (cnt[i]==k){ cout<<i;return 0 ;}
}
cout<<-1 ;return 0 ;
}
这个复杂度理论上应该是只能通过 30% 的数据,但本题数据较弱,这种写法可以通过 100% 的数据。
接下来思考如何优化,可以注意到,对 x 和 y 经过的路径计数,和求 x 和 y 的最近公共祖先的暴力写法是基本一致的。那么能不能根据这点优化呢?
显然是可以的,x 和 y 的最近公共祖先相当于一个终点,而 x 和 y 是两个起点,有起点和终点要对之间的所有数加 1,很容易想到差分。
#include <bits/stdc++.h>
using namespace std;
vector<pair<int ,int >>s[100005 ];
#define xx first
#define ii second
int id[100005 ];
int f[100005 ][25 ];
int h[100005 ];
int cnt[100005 ];
void dfs (int u) {
for (int i=1 ;i<=24 ;i++){ f[u][i]=f[f[u][i-1 ]][i-1 ];}
for (auto v:s[u]){
if (h[v.xx])continue ; h[v.xx]=h[u]+1 ; f[v.xx][0 ]=u; id[v.xx]=v.ii;
dfs (v.xx);
}
}
int lca (int x,int y) {
if (h[x]>h[y])swap (x,y);
for (int i=24 ;i>=0 ;i--){if (h[f[y][i]]>=h[x]){ y=f[y][i];}}
if (x==y)return x;
for (int i=24 ;i>=0 ;i--){if (f[x][i]!=f[y][i]){ x=f[x][i]; y=f[y][i];}}
return f[x][0 ];
}
void sol (int x,int y) {
int m=lca (x,y); cnt[id[x]]++; cnt[id[y]]++; cnt[id[m]]-=2 ;
}
void dfs2 (int u,int fa) {
for (auto v:s[u]){
if (v.xx==fa)continue ;
dfs2 (v.xx,u); cnt[id[u]]+=cnt[id[v.xx]];
}
}
int main () {
int n,k; cin>>n>>k;
for (int i=1 ;i<n;i++){
int u,v; cin>>u>>v; s[u].push_back ({v,i}); s[v].push_back ({u,i});
}
h[1 ]=1 ;dfs (1 );
for (int i=1 ;i<=k;i++){
int x,y; cin>>x>>y;sol (x,y);
}
dfs2 (1 ,0 );
for (int i=n-1 ;i>=1 ;i--){
if (cnt[i]==k){ cout<<i;return 0 ;}
}
cout<<-1 ;return 0 ;
}
回头重新看题目,题目要求找到一个条边把所有的 ai,bi 分开,那么分开后产生的两个子树里一定一个只包含 ai,一个只包含 bi。
根据这点,把 ai 点权设为 1,bi 点权设为 -1,之后对每个结点求子树和,如果一个点的点权的绝对值为 m,那么这个点与父结点之间的边就是符合题意的边。
#include <bits/stdc++.h>
using namespace std;
vector<pair<int ,int >>s[100005 ];
#define xx first
#define ii second
int cnt[100005 ];
int ans=-1 ;
int n,k;
void dfs (int u,int fa) {
for (auto v:s[u]){
if (v.xx==fa)continue ;
dfs (v.xx,u); cnt[u]+=cnt[v.xx];
}
if (abs (cnt[u])==k){
for (auto v:s[u]){
if (v.xx==fa){ ans=max (ans,v.ii);}
}
}
}
int main () {
cin>>n>>k;
for (int i=1 ;i<n;i++){
int u,v; cin>>u>>v; s[u].push_back ({v,i}); s[v].push_back ({u,i});
}
for (int i=1 ;i<=k;i++){
int x,y; cin>>x>>y; cnt[x]=1 ; cnt[y]=-1 ;
}
dfs (1 ,0 );
cout<<ans;return 0 ;
}
总结: 这一届题目难度明显比上一届高很多,涉及的知识点也更复杂。不过如果基本的知识掌握的足够好,就算没学过复杂的知识,也是足够获奖的。
涉及知识点: 搜索,简单动态规划,前缀和,链表,堆,树(最近公共祖先,树上差分)
相关免费在线工具 加密/解密文本 使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
Gemini 图片去水印 基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印,支持批量处理与下载。 在线工具,Gemini 图片去水印在线工具,online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
Markdown转HTML 将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online