第14届蓝桥杯(2023)C/C++大学B组省赛题解

一.填空题

A.日期统计

​ 这题大概问的就是这些数组构成多少个是\(2023\) 的子序列。

​ 这题千万不要一个一个找。我赛时想到了一个很绝妙的方法：直接反过来考虑，枚举\(2023\) 每一天的日期，看看在这个数组能不能找到对应的子序列，这样编码复杂度直接降了一半，并且不会有重复！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
using namespace std;
string s="5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533";

int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
//反过来考虑的一种想法 
int check(string date){ //检查日期是否在s中(子序列） 
	int last=-1;
	for(int i=0;i<date.size();i++){
		int pos=s.find(date[i],last+1);
		if(pos==-1)return false;
		last=pos;//更新last 
	}
	return true;
}
int main(){
	int ans=0;
	for(int i=1;i<=12;i++){
		for(int j=1;j<=month[i];j++){
			string m=i<10?"0"+to_string(i):to_string(i);
			string d=j<10?"0"+to_string(j):to_string(j);
			string now="2023"+m+d;
			if(check(now))ans++;
		}
	}
	cout<<ans; //235
	return 0;
}

B.01串的熵

​ 由于\(1\) 比\(0\) 多，所以\(0\) 的取值在\([0,n/2)\) 之间，枚举每一个取值。

​ 这里注意精度问题，精度可以控制在\(1e-4\) ，然后只关注大于\(H(s)\) 的值，所以要保证大于\(0\) ，打印就可以得到结果，当然如果不会精度控制的话，直接将\(11625907\sim11625908\) 之间的所有有效解打印出来，一个一个找也可以。

​ 这里比较考察推式子的能力

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <iostream>
#include <math.h>
using namespace std;
double eps=0.0001;
//log()->ln()
//log2()->log_2
int main(){
	int n= 23333333;
	for(int i=0;i<n/2;i++){
		double x=i;
		double y=n-i;
		double s=-1*((x*x)/n*log2(x/n)+(y*y)/n*log2(y/n));
		if(s-11625907.5798<=eps&&s-11625907.5798>=0){
			printf("%.4lf %.4lf\n",x,s);//11027421
		}
	}
}

二.程序题

C. 冶炼金属

方法一：二分搜索

​ 这是我赛时用的方法，首先明白一个概念：最小的\(V\) 代表最大的转换效率，最大的\(V\) 代表最差的转换效率，首先先推一下\(V_{max}\) ，不妨设\(V1=max(\frac{a[i]}{b[i]})\) ，假设这个值并不是最大值，也就是存在一个\(V_1’>V_1\) ，那对于取到最大值的那一对\(a[i],b[i]\) ，\(\frac{a[i]}{(V_1')} ，所以这个值一定是\(V_{max}\)

​ 而\(V_{min}\) 就不能是最小的了，\(V_{min}\) 就是满足\(a[i]/V=b[i]\) 中最小的那个\(V\) ，显然需要用到二分搜索，而且是往小了搜，判断函数是是否满足每一个\(a[i]/V\) 后都可以得到\(b[i]\) 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <iostream>
using namespace std;
const int N=1e4+7;
int a[N],b[N];
int n;
int k=1e9;

int check(int mid){
	for(int i=1;i<=n;i++)if(a[i]/mid>b[i])return false;
	return true;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		k=min(k,a[i]/b[i]);
	}
	int l=1,r=1e9;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	cout<<l<<" "<<k;
	return 0;
}

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

方法二：数学知识

​ \(V_{max}\) 已经推过了，现在推一下另一个，假设最小的\(V\) 是\(V_{min}\) ，小到什么程度呢，小到\(a[i]/(v-1)=b[i]+1\) ，反过来得到：\(v=(\frac{a[i]}{b[i]+1})+1\) ，然后多组数据取一个交集即可，这个\(v\) 在其他组数据可能是小了点，所以要取最大的那个然后加\(1\) 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>
using namespace std;
int n;
int minv=0;
int maxv=1e9;
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        minv=max(minv,(a/(b+1))+1);
        maxv=min(maxv,(a/b));
    }
    cout<<minv<<" "<<maxv;
}

D.飞机降落 tag:搜索

方法一.暴力搜索

​ 可以看成一个排列题，然后对于第\(i\) 个位置安排的航班\(j\) ，他应该在满足不与上一架飞机冲突的情况下尽可能早的飞，即他的飞行时间是\(max(上一架结束的时间,开始时间)\) ，其中\(dfs\) 的签名第一个函数代表位置，第二个函数代表上一架飞机飞行结束的时间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include <iostream>
#include <cstring>
using namespace std;
const int N=20;
struct node{
	int st,ed,len;
}a[N];
int n;
int use[N];
int dfs(int u,int last){
	if(u>n)return true;
	for(int i=1;i<=n;i++){
		if(!use[i]&&last<=a[i].ed){
			use[i]=true;
			bool tmp=dfs(u+1,max(a[i].st,last)+a[i].len);
			use[i]=false;
			if(tmp)return true;//如果这次安排i成功了 
		} 
	}	
	return false;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].st>>a[i].ed>>a[i].len;
		a[i].ed+=a[i].st;
	}
	memset(use,false,sizeof use);
	int res=dfs(1,0);
	if(res)cout<<"YES\n";
	else cout<<"NO\n";
}
int main(){
	int tt;
	cin>>tt;
	while(tt--)solve();
	return 0;
}

时间复杂度：\(O(n!)\)

空间复杂度：\(O(n)\)

方法二.状压DP

​ 考虑\(f[S]\) 代表选择了\(S\) 子集的最早结束时间。\(f[S]=max(f[S],max(f[S-k],start[k])+end[k])\) ，即代表从中任意去除一个点，如果这个点的开始时间比决策过来的时间还早，那就选决策时间（否则会冲突），反之选开始时间（即体现出\(max()\) ），答案为\(f[2^{n}-1]\) ，初始化\(f[0]=0\) ，其他的为\(inf\)

​ 其实从状态转移方程来看，\(f[S]\) 的演变其实就是谁安排在最后一位最优而已。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <cstring>
using namespace std;
const int N=1<<13;
const int inf=0x3f3f3f3f;

void solve(){
	int f[N]; 
	int n;
	cin>>n;
	int start[17],end[17],last[17];
	memset(f,inf,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;i++)cin>>start[i]>>end[i]>>last[i];
	for(int i=1;i<(1<<n);i++){
		for(int k=1;k<=n;k++){
			if((i>>(k-1))&1){
				int pre=f[i-(1<<(k-1))];//去掉k最早的完成时间
				if(start[k]+end[k]<pre)continue;//如果最早时间都不能避免冲突就下一个
				f[i]=min(f[i],max(pre,start[k])+last[k]);
			}		
		}
	}
	if(f[(1<<n)-1]<inf)cout<<"YES\n";
	else cout<<"NO\n";
	return; 
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int tt;
	cin>>tt;
	while(tt--)solve();
	return 0;
}

时间复杂度：\(O(2^nn)\)

空间复杂度：\(O(2^n)\)

E. 接龙序列 tag:动态规划

​ 定义\(f[i][j]\) 为前\(i\) 位中，以数字\(j\) 为结尾的接龙最大长度，答案就是\(n-f[n][?]\) ，问号处是最优解的数字。

​ 设\(head[i]\) 是第\(i\) 位数字的首位，\(tail[i]\) 是第\(i\) 位数字的末位，根据题目所述，数字\(a[i-1]\) 和\(a[i]\) 能形成接龙的条件就是：\(tail[i-1]=head[i]\) 。

​ \(f[i][j]\) 可以由\(f[i-1][j]\) （不选这个第\(i\) 个数字）或\(f[i-1][head[i]]\) （仅当\(j=head[i]\) ），然后预处理一下每一个位置上数字的\(head,tail\) 即可，时间复杂度是\(O(n+n)=O(2n)=O(n)\)

​ 注意到状态转移方程只关注上层和本层，所以可以优化成

\[f[tail]=max(f[tail],f[head]+1) \]

​ 这里不需要再判断\(j=head[i]\) 了，因为实际上我们不需要枚举每一个数字，因为不需要做拷贝。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
using namespace std;
const int N=1e5+7;
int f[N];
int n;
string a;
int res=-1;
int main() {
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		int head=a[0]-'0';//首位 
		int tail=a[a.size()-1]-'0';//末位 
		f[tail]=max(f[tail],f[head]+1);
	} 
	for(int i=0;i<=9;i++){
		res=max(res,f[i]);
	}
	cout<<n-res;
	return 0;
}

F. 岛屿个数 tag:搜索 FloodFill

​ 参见这个，也是我写的

G.子串简写 tag:双指针/二分/前缀和

方法一：二分搜索

​ 题意：字符串中有多少个长度大于等于\(k\) 的，且首字符为\(c1\) ，尾字符为\(c2\) 的子串？字符串长度为\(5e5\) ，盲猜时间复杂度是\(O(nlogn)\) 或者\(O(n)\) （注意这里没说一定满足\(c1≠c2\) ）

​ 令\(a[i]\) 为首字符出现位置的数组，例如\(a[1]=2\) 代表第\(1\) 个\(c1\) 字符出现的位置是\(2\) ，同理再令\(b[i]\) 保存尾字符出现位置，然后\(lena\) 代表记录了多少个\(c_1\) ，\(lenb\)同理 。

​ 我们每遍历一个\(a[i]\) ，然后寻找第一个下标位置大于等于\(a[i]+k\) 的\(b[j]\) ，然后说明从\(j\) 开始，\(b[j],b[j+1]\) 以及\(b[lenb]\) 都能与其组成一个长度一定不小于\(k\)的合法子串，这样以来时间复杂度是\(O(nlogn)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <iostream>
using namespace std;
const int N=5e5+7;
string s;
int a[N],b[N];
int k,lena,lenb;
char c1,c2;

int bs(int x){
	int l=0,r=lenb;
	while(l<r){
		int mid=(l+r)>>1;
		if(b[mid]>=x)r=mid;
		else l=mid+1;
	}
	return l;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>k>>s>>c1>>c2;
	for(int i=0;i<s.size();i++){
		if(s[i]==c1)a[lena++]=i;
		if(s[i]==c2)b[lenb++]=i;
	}
	long long res=0;
	for(int i=0;i<lena;i++){
		res+=lenb-bs(a[i]+k-1);//找到第一个大于等于k的 
	}
	cout<<res;
	return 0;
}

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

方法二：双指针

​ 我们不妨设\(p1\) 为记录\(a\) 数组的指针，\(p2\) 同理。

​ 当\(a[p1]\) 与\(b[p2]\) 的长度足够\(k\) 了，说明有\(lenb-p2\) 个尾字符可以与\(p1\) 匹配，此时\(p2\) 无需回退，因为\(p1\) 增长后，只会对\(b\) 的要求更严格，\(p1\) 还比较小的时候，\(p2\) 前面的下标都不够了，更不可能增大后还够，所以两个指针都是单调递增移动的，所以是双指针解法，时间复杂度是\(O(n)\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
using namespace std;
const int N=5e5+7;
string s;
int a[N],b[N];
int k,lena,lenb;
char c1,c2;

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>k>>s>>c1>>c2;
	for(int i=0;i<s.size();i++){
		if(s[i]==c1)a[lena++]=i;
		if(s[i]==c2)b[lenb++]=i;
	}
	long long res=0;
	int p1=0,p2=0;
	while(p1<lena&&p2<lenb){
		int len=b[p2]-a[p1]+1;//形成的子串长度 
		if(len>=k){
			res+=lenb-p2;
			p1++;
		}
		else p2++;
	}
	cout<<res;
	return 0;
}

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

方法三：前缀和

​ 写到这里其实明白了：这道题的瓶颈就在于怎么寻找当前尾字符能与之构成长度大于等于k的首字符个数 ，不难想到区间个数询问，也就是前缀和维护。

​ 记\(pre[i]\) 为前\(i\) 个字符中首字符出现的次数，每遍历一个尾字符，有效的首字符个数就是\(pre[i-k+1]\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <cstring>
using namespace std;
const int N=5e5+7;
int pre[N];
char s[N];
int k;
char c1,c2;

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>k>>s+1>>c1>>c2;
	int n=strlen(s+1);
	long long res=0;
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1];
		if(s[i]==c1)pre[i]++;
		if(i>=k&&s[i]==c2){
			res+=pre[i-k+1];
		}
	}
	cout<<res;
}

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

H. 整除删除 tag:优先队列 STL 双链表

​ 题目规模是\(5e5\) ，而每次要找到最小值，根据时间复杂度也可以推出必须要用优先队列，而要做大量删除操作，且删除时需要用到前驱后继，所以就得用到双链表，是一道很考数据结构的题。

​ 首先优先队列维护一个二元组，第一维是这个元素的值，第二维是元素下标，由于有\(k\) 次操作，所以最终元素一定会减到\(n-k\) 个，我们用优先队列每次取出最小值，然后利用双链表左右加权后即可，但这样面临一个问题：优先队列里的优先级是动态的，我们用优先队列拿到的最小值不一定是真的最小值，所以我们额外开设一个数组\(sum[i]\) 代表下标\(i\) 的加权，当拿到一个最小值时，如果加权不为\(0\) ，那就加上后再插入回去，如果加权为\(0\) ，说明他现在就是这个值，拼接一下双链表即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#pragma GCC optimize(2)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=5e5+7;
typedef long long ll;
typedef pair<ll,int> pii;
int n,k;
int pre[N];
int ne[N];
ll sum[N];
ll a[N];
void solve(){
	cin>>n>>k;
	priority_queue<pii,vector<pii>,greater<pii>> q;
	for(int i=1;i<=n;i++){
		ll val;
		cin>>val;
		q.push({val,i});
		pre[i]=i-1;
		ne[i]=i+1;
	}
	int g=n-k;
	while(q.size()>g){
		pii p=q.top();
		q.pop();
		ll val=p.first,idx=p.second;
		if(sum[idx]){
			q.push({val+sum[idx],idx});
			sum[idx]=0;
		}
		else{
			int l=pre[idx],r=ne[idx];
			sum[l]+=val;
			sum[r]+=val;
			pre[r]=l;
			ne[l]=r;
		}
	}
	while(q.size()){
		pii p=q.top();
		q.pop();
		a[p.second]=p.first+sum[p.second];
	}
	for(int i=1;i<=n;i++){
		if(a[i])cout<<a[i]<<" "; 
	} 
	cout<<"\n";
	return;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int tt=1;
	while(tt--)solve();
	return 0; 
}

时间复杂度：\(O(klogn)\)

空间复杂度：\(O(nlogn)\)

I. 景区导游 tag:LCA 枚举 树上距离

​ 注意是树形结构，所以肯定是图论问题或者树形\(dp\)

​ 首先考虑不跳过景点的总耗费怎么求？题目已经给出了\(A_1,A_2,..,A_k\) 的观光序列，这就涉及到LCA求任意两点的树上距离 ，由于第一个景点的距离不算，所以直接考虑\(A_1→A_2,A_2→A_3,..\) ，只需要不断累加当前景点和上一个景点的树上距离，然后累加得到一个\(sum\) 即可

​ 枚举每一个要被删除的点，删除这个点，等价于删除\(dist(A_{i-1}→A_i)+dist(A_i→A_i+1)(如果存在)\) 然后加上\(dist(A_{i-1}→A_{i+1})\)，然后计算\(dist\)的方法已经说过了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
using namespace std;
#define int long long
const int N=3e5+7;
struct node{
	int to,next,c;
}edge[N];
int head[N],cnt;

void add(int x,int y,int z){
	edge[++cnt].to=y;
	edge[cnt].c=z;
	edge[cnt].next=head[x];
	head[x]=cnt;
} 

int dep[N];
int fa[N][22];
int dist[N];//带权距离 
void dfs(int u,int v){
	dep[u]=dep[v]+1;
	fa[u][0]=v;
	for(int i=1;(1<<i)<=dep[u];i++){
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=edge[i].next){
		int y=edge[i].to;
		if(y==v)continue;
		dist[y]=dist[u]+edge[i].c;//距离 
		dfs(y,u);
	}
	return;
}

int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);//保证x是较深的 
	for(int i=20;i>=0;i--){
		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	}
	if(x==y)return x;
	for(int i=20;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int cal(int x,int y){
	return dist[x]+dist[y]-2*dist[lca(x,y)];
}
int n,k,sum;
int q[N];
int d[N];
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);//读入优化要开启
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	dfs(1,0);
	for(int i=1;i<=k;i++)cin>>q[i];
	for(int i=1;i<k;i++){
		sum+=cal(q[i],q[i+1]);
	}
	for(int i=1;i<=k;i++){
		if(i==1){ //首节点
			cout<<sum-cal(q[i],q[i+1])<<" ";
		}
		else if(i==k){ //尾节点
			cout<<sum-cal(q[i-1],q[i]);
		}//中间节点
		else cout<<sum-cal(q[i-1],q[i])-cal(q[i],q[i+1])+cal(q[i-1],q[i+1])<<" ";
	}
}

​ 一个小\(tips\) ：最开始提交的时候发现虽然AC了但耗时\(1980ms\) ，后面检查发现是读入优化没开启，开启重测后直接降到\(890ms\) ，本题没有影响，但对时限\(1s\) 的题目来说，这很有可能就是过与不过的分界线。

J. 砍树 tag:LCA 树上边差分

​ 一个容易想到的办法：枚举每一条边，然后用并查集合并节点判断连通性（合并过程中忽略枚举的这条边），看看合并后无序对\((a_i,a_j)\) 均不连通，如果是的话，就输出这条边，又因为输出字典序较大的那条，所以逆序遍历即可，这样做的时间复杂度是\(O(nmlogm)\) ，据说能拿一半分。

​ 正解是：我们令从\(a_i\) 走到\(a_j\) 的边全部加\(1\) ，然后和为\(m\) 的边就是所求（因为被所有对加了一次），这样的时间复杂度仍然是\(O(nm)\) ，然后发现刚刚全部加1 的操作很像差分数组区间加，这样以来我们就容易想到在树上差分。

​ 所以，我们要做的操作是，每遍历一个无序对，都将这个无序对路径上的边都加\(1\) ，最后遍历所有的边得到他们的和，如果找得到一个和为\(m\) 的边那就是，找不到就输出\(-1\)

​ 有个小难点：我们只知道\(d[i]\) 是节点\(i\) 到他父亲的边，但并不知道这条边是在原输入中的第几条，于是我有了一个很巧妙的办法：边的权重就是输入的顺序，这样省取了遍历的时间，速度也非常快，能跑到\(500ms\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+7; 
struct node{
	int to,next,c;
}edge[2*N];
int head[N],cnt;
void add(int x,int y,int z){
	edge[++cnt].to=y;
	edge[cnt].next=head[x];
	edge[cnt].c=z;
	head[x]=cnt;
}
int dep[N];
int fa[N][22];
void dfs(int u,int v){
	dep[u]=dep[v]+1;
	fa[u][0]=v;
	for(int i=1;(1<<i)<=dep[u];i++)fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=edge[i].next){
		int y=edge[i].to;
		if(y==v)continue;
		dfs(y,u);
	}
	return;
}

int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=20;i>=0;i--){
		if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
	}
	if(x==y)return x;
	for(int i=20;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
int d[2*N];
int ans=-1;
int n,k;
void dfs2(int u,int v){
	for(int i=head[u];i;i=edge[i].next){
		int y=edge[i].to;
		if(y==v)continue;
		dfs2(y,u);
		if(d[y]==k){
			ans=max(ans,edge[i].c);
		}
		d[u]+=d[y]; //添加子树 
	}
} 

int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		add(a,b,i);
		add(b,a,i);
	} 
	dfs(1,0);
	for(int i=1;i<=k;i++){
		int a,b;
		cin>>a>>b;
		int r=lca(a,b);
		d[a]++,d[b]++,d[r]-=2;
	}
	dfs2(1,0);
	cout<<ans;
}

时间复杂度：\(O(mlogn)\)

空间复杂度：\(O(n)\)

总结

​ 这次蓝桥杯考点还算常规，只不过有些考点做法有点偏（例如整除性质，双链表），填空题明显的变难了，第一题需要动动脑子或者动动手速才能做出来，子序列 对于一些裸考或者没碰过字符串/数组的选手来说会陌生。

​ 程序题对思维的要求能力高了不少，不过\(GHJ\) 还是可以通过暴力骗点分的，最后两题考了图论，还好考前背了下\(LCA\) 板子。

​ 总的来说题目还是很锻炼的，希望国赛能拿个奖项

​ upd(2023.6.16)喜提打铁国优，下一年再接再厉。

comments powered by Disqus
© 2022 - 2023 羽肿的个人博客
Built with Hugo
主题 Stack 由 Jimmy 设计