1. Toy模板网首页
  2. > Toy博客

十四届蓝桥杯省赛CB

7月前 作者：Selvaggia 分类：Toy博客 阅读(29) 违法举报

这篇具有很好参考价值的文章主要介绍了十四届蓝桥杯省赛CB。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A 日期统计

十四届蓝桥杯省赛CB

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=105;
const int M=2e4+5;
int n;
int a[N];
int res=0;
int mon[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool judge(int x){
	int y=x/10000;
	int m=(x%10000)/100;
	int d=x%100;
	if(y!=2023||m<1||m>12||d<1||d>mon[m])return false;
	else return true;
//	if(y==2023&&m>=1&&m<=12&&d>=1&&d<=mon[m])return true;
//	else return false;
}
map<int,int> mp;
void dfs(int u,int len,int sum){
//	cout<<sum<<"hhh"<<endl;
	if(len==8){
		if(!mp[sum]){
			if(judge(sum))res++;
			mp[sum]=1;
		}
		
		return ;
	}
	if(u>=100)return ;
	if(len==4&&sum!=2023)return ;
	dfs(u+1,len+1,sum*10+a[u]);
	dfs(u+1,len,sum);
}//6:03 21:33
signed main(){
	for(int i=0;i<100;i++){
		cin>>a[i];
	}
	dfs(0,0,0);
	cout<<res;
    return 0;
}


#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=105;
const int M=2e4+5;
int n;
int a[N];
int res=0;
int mon[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool judge(int x){
	int y=x/10000;
	int m=(x%10000)/100;
	int d=x%100;
	if(y!=2023||m<1||m>12||d<1||d>mon[m])return false;
	else return true;
//	if(y==2023&&m>=1&&m<=12&&d>=1&&d<=mon[m])return true;
//	else return false;
}
map<int,int> mp;
void dfs(int u,int s,int sum){
//	cout<<"hhh"<<endl;
	if(u==8){
		if(!mp[sum]){
			if(judge(sum))res++;
			mp[sum]=1;
		}
		
		return ;
	}
	if(u==4&&sum!=2023)return ;40
	for(int i=s;i<100;i++){
		dfs(u+1,i+1,sum*10+a[i]);
	}
}
signed main(){
	for(int i=0;i<100;i++){
		cin>>a[i];
	}
	dfs(0,0,0);
	cout<<res;
    return 0;
}

B 01 串的熵

十四届蓝桥杯省赛CB

#include <bits/stdc++.h>
#define int long long int
using namespace std;
signed main(){
	int n=23333333;
	for(int i=0;i<=n/2;i++){
		int j=n-i;
//		cout<<"h";
		double x=-1.0*(i*i)/n*log2(1.0*i/n)-1.0*(j*j)/n*log2(1.0*j/n);
		if(abs(x-11625907.5798)<=0.0001){
			cout<<i<<endl;
//			break;
		}
		
	}
    return 0;
}

写的时候没跑出来，仅仅是因为给(i*i)加了括号，爆了int！！！
双精度浮点的表示范围：-1.79E+308 ~ +1.79E+308

基本类型：int 二进制位数：32（4字节）
最小值：Integer.MIN_VALUE= -2147483648 （-2的31次方）
最大值：Integer.MAX_VALUE= 2147483647 （2的31次方-1
double范围很大，基本不可能爆，不放心用long double

C语言int/double数据类型的范围

#include <stdio.h>
#include <limits.h>
# include <float.h>

int main()
{
	printf("int类型数据所占空间=%d\n", sizeof(int));
	//  int类型数据范围
	// 方法1
	printf("int最小值=%d, int最大值=%d\n", INT_MIN, INT_MAX);	// 使用limits.h里的宏

	//方法2
	signed int max = (1 << (sizeof(int) * 8 - 1)) - 1;	// 自己计算
	signed int min = -(1 << (sizeof(int) * 8 - 1));
	printf("int最小值=%d, int最大值=%d\n", min, max);

	// 方法3
	printf("int最小值=%d, int最大值=%d\n", max+1, min-1);

	// double数据类型精度及范围--数据很大
	printf("float类型数据所占空间:%d\n", sizeof(float));
	printf("double类型数据所占空间:%d\n", sizeof(double));
	printf("double精度：%lf\n");	//有警告，不过可以运行
	printf("double最小值=%lf\n, double最大值=%lf\n", -DBL_MAX, DBL_MAX);	//使用float.h的宏
	return 0;
}

C 冶炼金属

十四届蓝桥杯省赛CB
十四届蓝桥杯省赛CB

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
//const int N=105;
const int N=1e4+5;
int n;
//struct node{
//	int x,y;
//}a[N];
int res=0;
int x,y;
signed main(){
	scanf("%d",&n);
	int minx=0x3f3f3f3f;
	int maxx=0;
	for(int i=0;i<n;i++){
		scanf("%d %d",&x,&y);
		minx=min(minx,x/y);
		maxx=max(maxx,x/(y+1));
	}
	
	cout<<maxx+1<<" "<<minx;
    return 0;
}

D: 飞机降落

十四届蓝桥杯省赛CB

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

十四届蓝桥杯省赛CB

暴力枚举序列
先看给定范围，范围小直接暴力，不要想任何关于逻辑关于贪心

#include <bits/stdc++.h>

//#define int long long int
#define pii pair<int,int>
using namespace std;
const int N=15;
int T,m,n;

struct node{
	int t,d,l,late;//到达，盘旋，降落过程
}v[N];
int s[N];
int vis[N];
int fg=0;
void dfs(int u){
	if(u==n+1){
//		for(int i=1;i<=n;i++)cout<<s[i]<<" ";
//		cout<<endl;
			int t=v[s[1]].t;
			int d=v[s[1]].d;
			int l=v[s[1]].l;
		int now=t+l;//前一架落地了，不怕来的晚，就怕来得早 
		for(int i=2;i<=n;i++){
			if(now>v[s[i]].late)return ;
			if(now<v[s[i]].t)now=v[s[i]].t;
			now+=v[s[i]].l;
		}
		fg=1;
		return ;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			if(fg)return ;
			s[u]=i,vis[i]=1,dfs(u+1),vis[i]=0;
		}	
	}
}
signed main(){//54
	scanf("%d",&T);
	while(T--){
		fg=0;
		memset(vis,0,sizeof(vis));
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d %d %d",&v[i].t,&v[i].d,&v[i].l);
			v[i].late=v[i].t+v[i].d;//最晚这个点一定要开始降
		}
		dfs(1);
		if(fg)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}

    return 0;
}
//2
//3
//0 100 10
//10 10 10
//0 2 20
//3
//0 10 20
//10 10 20
//20 10 20

E: 接龙数列

十四届蓝桥杯省赛CB
十四届蓝桥杯省赛CB

先来个暴力
十四届蓝桥杯省赛CB
中了这段代码的毒了

  for(int i=start;i+sum<=m;i++){
        // int tmp=rd+(1<<i);
        dfs(u+1,sum+i,i);
    }

最本质的暴力搜索是，已知一个具体的序列，选出一个子序列（注意了隐含的条件是选取元素的顺序和原序列顺序一致），满足某种条件，爆搜的方式是对于1~n每个元素，走取或者不取两个分支
这道题的暴力就是最原本的形式，u是指向原数组的指针，通过偏移将路径像远处延伸
从1~n依次考虑某个元素取或者不取自然可以保证顺序

至于1~n打乱顺序，u是指向目标数组的指针，代表这个位置该放哪个元素，通过数组长度的增长将路径像远处延伸，分支的可能是各个元素，需要遍历原数组

至于上面这段，
怎么说呢，就是具体知道原来的顺序，不需要通过start控制选取元素的顺序，start是控制大小的，

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=1e5+5;
int n;
int res=0;

int head(int u){
	int x=0;
	while(u){
		x=u%10;
		u/=10;	
	}
	return x;
}
int tail(int u){
	return u%10;
}
int a[N];
void dfs(int u,int len,int t){
//	cout<<len<<endl;
	if(u==n+1){
		res=max(res,len);
		return ;
	}
	if(t==-1||t==head(a[u]))dfs(u+1,len+1,tail(a[u]));
	dfs(u+1,len,t);
	
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		
	}
	dfs(1,0,-1);
	cout<<n-res;
    return 0;
}

开始dp
I idiot

	for(int i=1;i<=n;i++){
		if(t==-1||t==head(a[i]))
		dp[i]=dp[i-1]+1,t=tail(a[i]);
		else dp[i]=dp[i-1];//首先这个最基本的递推式逻辑就不对
//按这样的话，dp[i]的含义不是以a[i]结尾的最长接龙序列长度(但是求法是这样)，
//而是前i个里出现的最长子序列的长度，那么这个最长子序列就不一定以a[i]结尾
//如果dp[i]代表前i个里出现的最长子序列的长度，那么dp[i]可能由若干状态递推而来
//所以还是稳妥的，让dp[i]代表以a[i]结尾的最长接龙序列长度
//那么res=max(res,dp[i])
	}

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=1e5+5;
int n;
int res=0;

int head(int u){
	int x=0;
	while(u){
		x=u%10;
		u/=10;	
	}
	return x;
}
int tail(int u){
	return u%10;
}
int a[N];
int dp[N];//以a[i]结尾的最长合格长度
int num[N];//以数字num[i](1~9)结尾的最长合格长度
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);	
	}
	for(int i=1;i<=n;i++){
		int h=head(a[i]);
		int t=tail(a[i]);
		dp[i]=num[h]+1;
		//一定要以a[i]结尾，就要找到tail(a[?])==head[a[i]]
		num[t]=max(dp[i],num[t]);
		res=max(res,dp[i]);
	}
	cout<<n-res;
	
    return 0;
}


	int f;
	for(int i=1;i<=n;i++){
		int h=head(a[i]);
		int t=tail(a[i]);
		f=num[h]+1;
		//一定要以a[i]结尾，就要找tail(a[?])==head[a[i]]
		num[t]=max(f,num[t]);
		res=max(res,f);
	}
	cout<<n-res;

	for(int i=1;i<=n;i++){
		int h=head(a[i]);
		int t=tail(a[i]);
		num[t]=max(num[h]+1,num[t]);
		res=max(res,num[t]);
	}
	cout<<n-res;

F: 岛屿个数

十四届蓝桥杯省赛CB

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

十四届蓝桥杯省赛CB
十四届蓝桥杯省赛CB

十四届蓝桥杯省赛CB

#include <bits/stdc++.h>

//#define int long long int
#define pii pair<int,int>
using namespace std;
const int N=55;
int T,m,n;
string str[N];
int vis[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool inside(int cx,int cy){
	return cx>=0&&cx<m&&cy>=0&&cy<n;
}
int num;
void dfs(int x,int y){
	
	for(int i=0;i<4;i++){
		int cx=x+dx[i];
		int cy=y+dy[i];
		if(inside(cx,cy)&&str[cx][cy]-'0'==1&&!vis[cx][cy]){
			vis[cx][cy]=num;
			dfs(cx,cy);
		}
	}
}
map<int,bool> mp;//岛屿编号 是否冲出去
//void dfs1(int x,int y,int sg){
//		
//		for(int i=0;i<4;i++){
//			int cx=x+dx[i];
//			int cy=y+dy[i];
//			if(inside(cx,cy)&&str[cx][cy]-'0'==1&&!vis[cx][cy]){
//			vis[i][j]=num;
//			dfs(cx,cy);
			走到0也走，只要能走出去
//		}
//	}
//}
int viss[N][N];
queue<pii> Q;
int forbid;
bool bfs(int sg){
	int x, y;
//	cout<<sg<<endl<<endl;
	while(!Q.empty()){
		pii t=Q.front();Q.pop();
		x=t.first,y=t.second;
		if(x==0||x==m-1||y==0||y==n-1){
			if(str[x][y]!=forbid){
//				Q.clear();
				
				return true;
			}
		}
//		cout<<x<<" "<<y<<endl;
		for(int i=0;i<4;i++){
			int cx=x+dx[i];
			int cy=y+dy[i];
			
			if(inside(cx,cy)&&!viss[cx][cy]&&(vis[cx][cy]!=forbid)){
			viss[cx][cy]=1;
//			cout<<cx<<" "<<cy<<"dvwierl"<<endl;
			Q.push({cx,cy});
//			走到0也走，只要能走出去
		}
	}
	
	}
return false;
}
signed main(){
	scanf("%d",&T);
	while(T--){
		memset(vis,0,sizeof(vis));
		mp.clear();
		scanf("%d %d",&m,&n);
		for(int i=0;i<m;i++)cin>>str[i];
//		dfs();
		num=1;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if(str[i][j]-'0'==1&&!vis[i][j])vis[i][j]=num,dfs(i,j),num++;
			}
		}
//		for(int i=0;i<m;i++){
//			for(int j=0;j<n;j++){
//				cout<<vis[i][j]<<" ";
//			}
//			cout<<endl;
//		}
		int cnt=0;
		
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				
					if(str[i][j]-'0'==1&&!mp[vis[i][j]]){
						for(forbid=1;forbid<num;forbid++){
						if(forbid==vis[i][j])continue;
	//					cout<<"hhh"<<endl;
						mp[vis[i][j]]=1;
						while(!Q.empty()){
							Q.pop();
						}
						memset(viss,0,sizeof(viss));
						Q.push({i,j});
						viss[i][j]=1;
						bool f=bfs(vis[i][j]);
	//					bool f=dfs1(i,j,vis[i][j]);
						if(!f){
							cnt++;break;//被包围了，不再看下去
						}
					
					}
				}
				
			}
		}
		cout<<num-1-cnt<<endl;
	}
    return 0;
}
//错在，子岛的定义是，不被一个道阻拦，而被多个岛屿阻拦不算自岛
//2
//5 5
//01111
//11001
//10101
//10001
//11111
//5 6
//111111
//100001
//010101
//100001
//111111

斜对角也可以逃出，但超时了
对于每一个岛屿，枚举别的所有岛屿，看看是否被别的岛屿包围，不能被任何岛屿包围
由于是八角包围，包围别人的母岛一定是一个岛，连起来的嘛
十四届蓝桥杯省赛CB

#include <bits/stdc++.h>

//#define int long long int
#define pii pair<int,int>
using namespace std;
const int N=55;
int T,m,n;
string str[N];
int vis[N][N];
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,1,-1,1,-1};
bool inside(int cx,int cy){
	return cx>=0&&cx<m&&cy>=0&&cy<n;
}
int num;
void dfs(int x,int y){
	
	for(int i=0;i<4;i++){
		int cx=x+dx[i];
		int cy=y+dy[i];
		if(inside(cx,cy)&&str[cx][cy]-'0'==1&&!vis[cx][cy]){
			vis[cx][cy]=num;
			dfs(cx,cy);
		}
	}
}
map<int,bool> mp;//岛屿编号 是否冲出去
//void dfs1(int x,int y,int sg){
//		
//		for(int i=0;i<4;i++){
//			int cx=x+dx[i];
//			int cy=y+dy[i];
//			if(inside(cx,cy)&&str[cx][cy]-'0'==1&&!vis[cx][cy]){
//			vis[i][j]=num;
//			dfs(cx,cy);
			走到0也走，只要能走出去
//		}
//	}
//}
int viss[N][N];
queue<pii> Q;
int forbid;
bool bfs(int sg){
	int x, y;
//	cout<<sg<<endl<<endl;
	while(!Q.empty()){
		pii t=Q.front();Q.pop();
		x=t.first,y=t.second;
		if(x==0||x==m-1||y==0||y==n-1){
			if(str[x][y]!=forbid){
//				Q.clear();
				
				return true;
			}
		}
//		cout<<x<<" "<<y<<endl;
		for(int i=0;i<8;i++){
			int cx=x+dx[i];
			int cy=y+dy[i];
			
			if(inside(cx,cy)&&!viss[cx][cy]&&(vis[cx][cy]!=forbid)){
			viss[cx][cy]=1;
//			cout<<cx<<" "<<cy<<"dvwierl"<<endl;
			Q.push({cx,cy});
//			走到0也走，只要能走出去
		}
	}
	
	}
return false;
}
signed main(){
	scanf("%d",&T);
	while(T--){
		memset(vis,0,sizeof(vis));
		mp.clear();
		scanf("%d %d",&m,&n);
		for(int i=0;i<m;i++)cin>>str[i];
//		dfs();
		num=1;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if(str[i][j]-'0'==1&&!vis[i][j])vis[i][j]=num,dfs(i,j),num++;
			}
		}
//		for(int i=0;i<m;i++){
//			for(int j=0;j<n;j++){
//				cout<<vis[i][j]<<" ";
//			}
//			cout<<endl;
//		}
		int cnt=0;
		
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				
					if(str[i][j]-'0'==1&&!mp[vis[i][j]]){
						for(forbid=1;forbid<num;forbid++){
						if(forbid==vis[i][j])continue;
	//					cout<<"hhh"<<endl;
						mp[vis[i][j]]=1;
						while(!Q.empty()){
							Q.pop();
						}
						memset(viss,0,sizeof(viss));
						Q.push({i,j});
						viss[i][j]=1;
						bool f=bfs(vis[i][j]);
	//					bool f=dfs1(i,j,vis[i][j]);
						if(!f){
							cnt++;break;//被包围了，不再看下去
						}
					
					}
				}
				
			}
		}
		cout<<num-1-cnt<<endl;
	}
    return 0;
}
//错在，子岛的定义是，不被一个道阻拦，而被多个岛屿阻拦不算自岛
//2
//5 5
//01111
//11001
//10101
//10001
//11111
//5 6
//111111
//100001
//010101
//100001
//111111

AC 搞半天，原来，只要不被八个角都被包围就好，也不用那么强的要求，不要求八个角都是一个岛的
woc，突然发现，如果被包围了，那么一定是被同一个岛包围的TTTTTTTT我是傻子

#include <bits/stdc++.h>

//#define int long long int
#define pii pair<int,int>
using namespace std;
const int N=55;
int T,m,n;
string str[N];
int vis[N][N];
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,1,-1,1,-1};
bool inside(int cx,int cy){
	return cx>=0&&cx<m&&cy>=0&&cy<n;
}
int num;
void dfs(int x,int y){
	
	for(int i=0;i<4;i++){
		int cx=x+dx[i];
		int cy=y+dy[i];
		if(inside(cx,cy)&&str[cx][cy]-'0'==1&&!vis[cx][cy]){
			vis[cx][cy]=num;
			dfs(cx,cy);
		}
	}
}
map<int,bool> mp;//岛屿编号 是否冲出去
int viss[N][N];
queue<pii> Q;
bool bfs(int sg){
	int x, y;
	while(!Q.empty()){
		pii t=Q.front();Q.pop();
		x=t.first,y=t.second;
		if(x==0||x==m-1||y==0||y==n-1){
			if(str[x][y]=='0'||vis[x][y]==sg)return true;
		}
		for(int i=0;i<8;i++){
			int cx=x+dx[i];
			int cy=y+dy[i];
			
			if(inside(cx,cy)&&!viss[cx][cy]&&(str[x][y]=='0'||vis[x][y]==sg)){
			viss[cx][cy]=1;
			Q.push({cx,cy});
//			走到0也走，只要能走出去
		}
	}
	
	}
	return false;
}
signed main(){
	scanf("%d",&T);
	while(T--){
		memset(vis,0,sizeof(vis));
		mp.clear();
		scanf("%d %d",&m,&n);
		for(int i=0;i<m;i++)cin>>str[i];
//		dfs();
		num=1;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				if(str[i][j]-'0'==1&&!vis[i][j])vis[i][j]=num,dfs(i,j),num++;
			}
		}
		int cnt=0;
		
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){			
				if(str[i][j]-'0'==1&&!mp[vis[i][j]]){
					mp[vis[i][j]]=1;
					while(!Q.empty()){
						Q.pop();
					}
					memset(viss,0,sizeof(viss));
					Q.push({i,j});
					viss[i][j]=1;
					bool f=bfs(vis[i][j]);
					if(!f){
						cnt++;
					}
				}
				}		
			}
		cout<<num-1-cnt<<endl;
	}
    return 0;
}
//错在，子岛的定义是，不被一个道阻拦，而被多个岛屿阻拦不算子岛
//2
//5 5
//01111
//11001
//10101
//10001
//11111
//5 6
//111111
//100001
//010101
//100001
//111111

G: 子串简写

十四届蓝桥杯省赛CB
十四届蓝桥杯省赛CB

猜猜坑在哪？c1可能等于c2 哈哈哈，把else if(str[i]==c2){改成直接判断c2 if(str[i]==c2)
十四届蓝桥杯省赛CB

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=5e5+5;
int n,k;
int res=0;
string str;
char c1,c2;
//int suffix[N];//不用，后缀和可以通过前缀和得到 sum[n]-sum[i-1]
int sum1[N];
int sum2[N];
//Prefix suffix
signed main(){
	scanf("%d",&k);
	cin>>str;
	getchar();
	cin>>c1;
	getchar();
	cin>>c2;
	int n=str.size();
	str="#"+str;
	
	for(int i=1;i<=n;i++){
		sum1[i]=sum1[i-1];
		sum2[i]=sum2[i-1];
		if(str[i]==c1){
			sum1[i]+=1;
		}
		else if(str[i]==c2){
			sum2[i]+=1;
		}
//		cout<<sum2[i]<<" ";
	}
//	cout<<endl;
	for(int i=1;i<=n;i++){
		if(str[i]==c1){
			int j=i+k-1;
			if(j<=n)res+=sum2[n]-sum2[j-1];
//			cout<<res<<" ";
		}
	}
	cout<<res;
    return 0;
}

H: 整数删除

十四届蓝桥杯省赛CB
十四届蓝桥杯省赛CB

虽然也没AC，但那天晚上，忘了sort(ans.begin(),ans.end(),cmp);这句代码真的让人气急攻心！
当时混乱一片，忘记排序，为了迎合样例倒序输出TT
十四届蓝桥杯省赛CB

十四届蓝桥杯省赛CB

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=5e5+5;
int n,k,x;
int res=0;
typedef struct node{
	int v,pos;
	bool operator<(const node & p)const{
		if(v==p.v)return pos>p.pos;
		else return v>p.v;
	}
}node;
vector<node> ans;
int add[N];//当即加上不太方便操作，等碰到再加
priority_queue<node > Q;//,vector<node>,greater<node>
bool cmp(node a,node b){
	return a.pos<b.pos;
}
map<int,int> del;
signed main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		Q.push({x,i});
	}
	while(k--){
		node t=Q.top();Q.pop();
		int pos=t.pos;
		if(!add[pos]){
			int l=pos-1,r=pos+1;
			while(del[r])r++;
			while(del[l])l++;
			add[l]+=t.v;
			add[r]+=t.v;
//			add[pos+1]+=t.v;
//			add[pos-1]+=t.v;
			//没有关系，即使相邻位置不存在或已经被删除，反正不会再碰到
//			但是最后因为要输出最终值，仍然在队列中的元素add的值需要加上
//错了，删除了元素之后，pos相邻的元素原下标就不一定是pos+-1
//删除元素的时候
del[pos]=1;
		}
		else{
			t.v+=add[pos];
			add[pos]=0;
			Q.push(t);
			k++;
		}
//		for(int i=1;i<=n;i++)cout<<add[i]<<" ";
//		cout<<endl;
	}
	
	while(!Q.empty()){
		node t=Q.top();Q.pop();
//		if(add[t.pos])
		t.v+=add[t.pos];
		ans.push_back(t);
	}
	sort(ans.begin(),ans.end(),cmp);
	for(int i=0;i<ans.size();i++)cout<<ans[i].v<<" ";
//	cout<<res;
    return 0;
}
//5 3
//1 4 2 8 7

I: 景区导游

十四届蓝桥杯省赛CB

6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1

十四届蓝桥杯省赛CB

暴力先行，第一次连Floyd都写不出来TT
二维空间爆了空间，最多3e7,这里到了1e10
十四届蓝桥杯省赛CB
十四届蓝桥杯省赛CB

#include <bits/stdc++.h>
using namespace std;
//#define int long long int
#define pii pair<int,int>
const int inf=0x3f3f3f3f;
const int N=1e3+5;//开小一点能过部分样例，开大了直接爆
int n,kk,u,v,w;
int e[N][N];
int r[N];
signed main(){
scanf("%d %d",&n,&kk);
//	memset(e,0x3f,sizeof(e));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j)e[i][j]=0x3f3f3f3f;
	}
}

	
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&u,&v,&w);
		e[u][v]=min(w,e[u][v]);
		e[v][u]=min(w,e[v][u]);
//		cout<<e[u][v]<<endl;
	}
//	cout<<e[1][2]<<endl;
	for(int i=1;i<=kk;i++)scanf("%d",&r[i]);
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(e[i][k]+e[k][j]<e[i][j])e[i][j]=e[i][k]+e[k][j];
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=n;j++){
//				cout<<e[i][j]<<" ";
//			}
//			cout<<endl;
//		}
		
		
	int res=0;
	for(int j=1;j<kk;j++){
		res+=e[r[j]][r[j+1]];
//		cout<<res<<endl;
	}
//	cout<<res<<endl;
	for(int i=1;i<=kk;i++){	
	int ans=res;
	if(i-1>=1)ans-=e[r[i-1]][r[i]];
	if(i+1<=kk)ans-=e[r[i]][r[i+1]];
	if(i-1>=1&&i+1<=kk)ans+=e[r[i-1]][r[i+1]];
	cout<<ans<<" ";
	}
    return 0;
}

//6 4
//1 2 1
//1 3 1
//3 4 2
//3 5 2
//4 6 3
//2 6 5 1

也才过24%，lca还不行？原来我会的只是简单粗暴版的lca

#include <bits/stdc++.h>
using namespace std;
//#define int long long int
#define pii pair<int,int>
const int N=1e5+5;
const int M=2e5+5;//注意是双向边，空间开小了也会wa很多
int n,kk,u,v,w;
struct node{
	int to,nxt,w;
}e[M];
int head[N];
int cnt;
void add(int u,int v,int w){
	e[++cnt].w=w;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int dep[N];
int fa[N];
int sum[N];//从根节点到这个节点路径的长度总和
void dfs(int u,int f){
	fa[u]=f;
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==f)continue;
		dep[to]=dep[u]+1;
		sum[to]=sum[u]+e[i].w;
		dfs(to,u);
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	while(dep[u]!=dep[v]){
		u=fa[u];
	}//现在处于同一高度了，找lca
	while(u!=v){
		u=fa[u];
		v=fa[v];
	}
	return u;
}
int r[N];
int dist(int u,int v){//任意两点之间的距离
	return sum[u]+sum[v]-2*sum[lca(u,v)];
}
signed main(){
	scanf("%d %d",&n,&kk);
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dep[1]=1;sum[1]=0;
	dfs(1,0);
	for(int i=1;i<=kk;i++)scanf("%d",&r[i]);
	int res=0;
	for(int j=1;j<kk;j++){
		res+=dist(r[j],r[j+1]);
//		cout<<res<<endl;
	}
	for(int i=1;i<=kk;i++){	
		int ans=res;
		if(i-1>=1)ans-=dist(r[i-1],r[i]);
		if(i+1<=kk)ans-=dist(r[i],r[i+1]);
		if(i-1>=1&&i+1<=kk)ans+=dist(r[i-1],r[i+1]);
		cout<<ans<<" ";
	}
    return 0;
}

倍增LCA/tarjan LCA
十四届蓝桥杯省赛CB
二进制拼凑的思想
11的二进制表示的最高1位就是8代表的这一位
十四届蓝桥杯省赛CB

if(dep[x]<dep[y]) swap(x,y);//先保证x比y更深，x往上跳
for(int i=20; i>=0; i--)
        if(dep[f[x][i]]>=dep[y])  // 找到和y同高度的节点
            x = f[x][i];

dep[f[x][i]]>=dep[y]表示x跳了 2 i 2^i 2i步还是比y深，还要继续往上跳，一直跳到xy深度相等，为什么一定可以跳到相等的一层，因为任何正数都可以通过二进制数表示，由 2 i 2^i 2i 累加而成
如果还不相等，一起往上跳
跳到公共祖先的最下面一层，因为先大步跳，如果判断f[x][i]==f[y][i],那么到达的自然是公共祖先，但无法判断是否是最近公共祖先，但如果跳到公共祖先的下面一层，判断f[x][i]！=f[y][i],就很确定，上一层就是最近公共祖先
AC代码，dfs，bfs都嘚！

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pii pair<int,int>
const int N=1e5+5;
const int M=2e5+5;//注意是双向边，空间开小了也会wa很多
int n,kk,u,v,w;
struct node{
	int to,nxt,w;
}e[M];
int head[N];
int cnt;
void add(int u,int v,int w){
	e[++cnt].w=w;
	e[cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int dep[N];
//int fa[N];
int fa[N][25];//节点i向上跳2^j能到达的节点
int sum[N];//从根节点到这个节点路径的长度总和
void dfs(int u,int f){
//	fa[u]=f;
//	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
//	首先，根节点需要最先初始化fa[root][0~20],其次如果放在循环里面对父节点更新u不合理
//两点，首先最先进的root需要得到fa，但根节点任何向上的祖先都只有0
//其次，每个节点都需要得到fa，要么每进入dfs获得，要么，根节点的每个孩子的孩子的……得到
	for(int i=head[u];i;i=e[i].nxt){
		int to=e[i].to;
		if(to==f)continue;
		sum[to]=sum[u]+e[i].w;
		dep[to]=dep[u]+1;
//		fa[u][0]=f;错误
//		for(int i=1;i<=20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
//		fa[to][0]=u;正确
//		for(int i=1;i<=20;i++)fa[to][i]=fa[fa[to][i-1]][i-1];
		dfs(to,u);
	}
}
void bfs(int rt){
	queue<int> Q;Q.push(rt);dep[rt]=1;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for(int i=head[u];i;i=e[i].nxt){
			int to=e[i].to;
//			if(dep[to])continue;
			if(to==fa[u][0])continue;
			sum[to]=sum[u]+e[i].w;
			dep[to]=dep[u]+1;
			fa[to][0]=u;
			for(int i=1;i<=20;i++)fa[to][i]=fa[fa[to][i-1]][i-1];
			Q.push(to);
		}
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=20;i>=0;i--){
		if(dep[fa[u][i]]>=dep[v])u=fa[u][i];
	}
	if(u==v)return u;
	for(int i=20;i>=0;i--){
//		if(dep[fa[u][i]]!=dep[fa[v][i]])u=fa[u][i],v=fa[v][i];
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	}
	return fa[u][0];
}

int r[N];
int dist(int u,int v){//任意两点之间的距离
	return sum[u]+sum[v]-2*sum[lca(u,v)];
}
signed main(){
	scanf("%d %d",&n,&kk);
	for(int i=1;i<n;i++){
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
//	dep[1]=1;sum[1]=0;
//	dfs(1,0);
	bfs(1);
	for(int i=0;i<kk;i++)scanf("%d",&r[i]);
	int res=0;
	for(int j=0;j<kk-1;j++){
		res+=dist(r[j],r[j+1]);
//		cout<<res<<endl;
	}
	for(int i=0;i<kk;i++){	
		int ans=res;
//		if(i-1>=1)ans-=dist(r[i-1],r[i]);
//		if(i+1<=kk)ans-=dist(r[i],r[i+1]);
//		if(i-1>=1&&i+1<=kk)ans+=dist(r[i-1],r[i+1]);
		
		// 跳过i(i不是端点),等同于砍掉i-1->i和i->i+1,加上i-1->i+1
        if (i && i != kk - 1) ans += dist(r[i - 1], r[i + 1]) - dist(r[i - 1], r[i]) - dist(r[i], r[i + 1]);
        // 跳过i(i是左端点),等同于砍掉i->i+1
        else if (!i) ans -= dist(r[i], r[i + 1]);
        // 跳过i(i是右端点),等同于砍掉i-1->i
        else ans -= dist(r[i - 1], r[i]);

		cout<<ans<<" ";
		
	}
    return 0;
}

//6 4
//1 2 1
//1 3 1
//3 4 2
//3 5 2
//4 6 3
//2 6 5 1

J: 砍树

十四届蓝桥杯省赛CB

6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5

十四届蓝桥杯省赛CB文章来源地址https://www.toymoban.com/news/detail-474775.html

到了这里，关于十四届蓝桥杯省赛CB的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 第十四届蓝桥杯省赛c/c++大学B组题解

    第十四届蓝桥杯省赛c/c++大学B组题解

    个人答案，有错漏感谢指正哈 本题总分：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

    2023年04月12日
    浏览(41)

  • 第十四届蓝桥杯省赛 Python B 组 D 题——管道（AC）

    有一根长度为 len text{len} len 的横向的管道，该管道按照单位长度分为 len text{len} len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。 一开始管道是空的，位于 L i L_i L i ​ 的阀门会在 S i S_i S i ​ 时刻打开，并不断让水流入管道。 对于位于 L i L_i L i ​ 的阀

    2024年02月07日
    浏览(32)
  • 第十四届蓝桥杯省赛JavaB组试题E【蜗牛】个人题解Dijkstra堆优化

    第十四届蓝桥杯省赛JavaB组试题E【蜗牛】个人题解Dijkstra堆优化

                                                                                     🍏🍐🍊🍑🍒🍓🫐🥑🍋🍉🥝                                               第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆

    2023年04月15日
    浏览(33)

  • 第十三届蓝桥杯省赛与国赛真题题解大汇总（十四届参赛者必备）

      大家好，我是执梗。本文汇总了我写的第十三届蓝桥杯所有省赛真题与国赛真题，会针对每道题打出我自己的难度评星⭐️，也会给出每道题的算法标签，帮助大家更有针对性的去学习和准备，当然许多题目由于难度或时间的原因暂未更新，如果有不懂的问题也可以在评

    2024年02月11日
    浏览(66)
  • 第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP？

    第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆优化 or 线性DP？

                                                                                     🍏🍐🍊🍑🍒🍓🫐🥑🍋🍉🥝                                               第十四届蓝桥杯省赛JavaB组试题E【蜗牛】Dijkstra堆

    2024年02月01日
    浏览(36)

  • 第十四届蓝桥杯省赛 C/C++ A 组 H 题——异或和之和（AC）

    给定一个数组 A i A_i A i ​ ，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 1 ≤ L ≤ R ≤ n 1 leq L leq R leq n 1 ≤ L ≤ R ≤ n 的 L , R L, R L , R ，求出数组中第 L L L 至第 R R R 个元素的异或和。然后输出每组 L , R L, R L , R 得到的结果加起来的值。 输入的第

    2024年02月13日
    浏览(28)

  • 蓝桥杯十四届单片机省赛

    【失败的博主】蓝桥杯最后一文 感想 ： 练完省赛题就去练国赛题！！！ 1.B站小蜜蜂老师（基础模块 ）（容易听懂） 2.做一套省赛题、你会发 现无法把模块结合起来。 3.学整体代码的思想（关键！!!） 来源：电子设计工坊、四梯科技、官方源代码、其他人做的题； 4.形成自

    2023年04月10日
    浏览(39)

  • 蓝桥杯2023年第十四届省赛-飞机降落

    N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早 可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li个单位时间。 一架飞机降落完毕时，另一架

    2024年02月15日
    浏览(37)
  • 第十四届蓝桥杯Python B组省赛复盘

    第十四届蓝桥杯Python B组省赛复盘

    【问题描述】（5 分） 请求出在 12345678 至 98765432 中，有多少个数中完全不包含 2023 。 完全不包含 2023 是指无论将这个数的哪些数位移除都不能得到 2023 。 例如 20322175，33220022 都完全不包含 2023，而 20230415，20193213 则 含有 2023 (后者取第 1, 2, 6, 8 个数位) 。 【思路】 正则表达

    2024年02月02日
    浏览(39)
  • 蓝桥杯嵌入式第十四届省赛题目解析

    蓝桥杯嵌入式第十四届省赛题目解析

    前几天刚刚参加完第十四届的省赛，这届题目比我想象中的要难，其实想一想这也是应该的，以前的知识点都被摸透了，也是需要加入新的知识点了，但是我还是想说能不能别在我参加的时候加大题目难度啊。 不过听说隔壁单片机的省赛都比往年的国赛还难，这就有点离谱了

    2024年02月06日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包