国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁
  2. >Toy博客

十四屆藍橋杯省賽CB

2年前作者：Selvaggia分類：Toy博客閱讀(20)違法舉報

這篇具有很好參考價值的文章主要介紹了十四屆藍橋杯省賽CB。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

A 日期統(tǒng)計

十四屆藍橋杯省賽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 二進制位數(shù)：32（4字節(jié)）
最小值：Integer.MIN_VALUE= -2147483648 （-2的31次方）
最大值：Integer.MAX_VALUE= 2147483647 （2的31次方-1
double范圍很大，基本不可能爆，不放心用long double

C語言int/double數(shù)據(jù)類型的范圍

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

int main()
{
	printf("int類型數(shù)據(jù)所占空間=%d\n", sizeof(int));
	//  int類型數(shù)據(jù)范圍
	// 方法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數(shù)據(jù)類型精度及范圍--數(shù)據(jù)很大
	printf("float類型數(shù)據(jù)所占空間:%d\n", sizeof(float));
	printf("double類型數(shù)據(jù)所占空間:%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: 接龍數(shù)列

十四屆藍橋杯省賽CB
十四屆藍橋杯省賽CB

先來個暴力
十四屆藍橋杯省賽CB
中了這段代碼的毒了

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

最本質(zhì)的暴力搜索是，已知一個具體的序列，選出一個子序列（注意了隱含的條件是選取元素的順序和原序列順序一致），滿足某種條件，爆搜的方式是對于1~n每個元素，走取或者不取兩個分支
這道題的暴力就是最原本的形式，u是指向原數(shù)組的指針，通過偏移將路徑像遠處延伸
從1~n依次考慮某個元素取或者不取自然可以保證順序

至于1~n打亂順序，u是指向目標數(shù)組的指針，代表這個位置該放哪個元素，通過數(shù)組長度的增長將路徑像遠處延伸，分支的可能是各個元素，需要遍歷原數(shù)組

至于上面這段，
怎么說呢，就是具體知道原來的順序，不需要通過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個里出現(xiàn)的最長子序列的長度，那么這個最長子序列就不一定以a[i]結尾
//如果dp[i]代表前i個里出現(xiàn)的最長子序列的長度，那么dp[i]可能由若干狀態(tài)遞推而來
//所以還是穩(wěn)妥的，讓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];//以數(shù)字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: 島嶼個數(shù)

十四屆藍橋杯省賽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，突然發(fā)現(xiàn)，如果被包圍了，那么一定是被同一個島包圍的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: 整數(shù)刪除

十四屆藍橋杯省賽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;
			//沒有關系，即使相鄰位置不存在或已經(jīng)被刪除，反正不會再碰到
//			但是最后因為要輸出最終值，仍然在隊列中的元素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: 景區(qū)導游

十四屆藍橋杯省賽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];//從根節(jié)點到這個節(jié)點路徑的長度總和
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];
	}//現(xiàn)在處于同一高度了，找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同高度的節(jié)點
            x = f[x][i];

dep[f[x][i]]>=dep[y]表示x跳了 2 i 2^i 2i步還是比y深，還要繼續(xù)往上跳，一直跳到xy深度相等，為什么一定可以跳到相等的一層，因為任何正數(shù)都可以通過二進制數(shù)表示，由 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];//節(jié)點i向上跳2^j能到達的節(jié)點
int sum[N];//從根節(jié)點到這個節(jié)點路徑的長度總和
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];
//	首先，根節(jié)點需要最先初始化fa[root][0~20],其次如果放在循環(huán)里面對父節(jié)點更新u不合理
//兩點，首先最先進的root需要得到fa，但根節(jié)點任何向上的祖先都只有0
//其次，每個節(jié)點都需要得到fa，要么每進入dfs獲得，要么，根節(jié)點的每個孩子的孩子的……得到
	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文章來源地址http://www.zghlxwxcb.cn/news/detail-474775.html

到了這里，關于十四屆藍橋杯省賽CB的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。如若轉(zhuǎn)載，請注明出處： 如若內(nèi)容造成侵權/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

領支付寶紅包贊助服務器費用

相關文章

  • 第十四屆藍橋杯省賽c/c++大學B組題解

    第十四屆藍橋杯省賽c/c++大學B組題解

    個人答案，有錯漏感謝指正哈 本題總分：5 分 【問題描述】 ??小藍現(xiàn)在有一個長度為 100 的數(shù)組，數(shù)組中的每個元素的值都在 0 到 9 的范圍之內(nèi)。數(shù)組中的元素從左至右如下所示： 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日
    瀏覽(24)

  • 第十四屆藍橋杯省賽 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日
    瀏覽(24)
  • 第十四屆藍橋杯省賽JavaB組試題E【蝸?！總€人題解Dijkstra堆優(yōu)化

    第十四屆藍橋杯省賽JavaB組試題E【蝸?！總€人題解Dijkstra堆優(yōu)化

    ??????????????????????????????????????????????????????????????????????????????????????????????????????? ????????????????????????????????????????????? 第十四屆藍橋杯省賽JavaB組試題E【蝸?！緿ijkstra堆

    2023年04月15日
    瀏覽(28)

  • 第十三屆藍橋杯省賽與國賽真題題解大匯總（十四屆參賽者必備）

    ??大家好，我是執(zhí)梗。本文匯總了我寫的第十三屆藍橋杯所有省賽真題與國賽真題，會針對每道題打出我自己的難度評星??，也會給出每道題的算法標簽，幫助大家更有針對性的去學習和準備，當然許多題目由于難度或時間的原因暫未更新，如果有不懂的問題也可以在評

    2024年02月11日
    瀏覽(37)

  • 第十四屆藍橋杯省賽 C/C++ A 組 H 題——異或和之和（AC）

    給定一個數(shù)組 A i A_i A i ? ，分別求其每個子段的異或和，并求出它們的和?；蛘哒f，對于每組滿足 1 ≤ L ≤ R ≤ n 1 leq L leq R leq n 1 ≤ L ≤ R ≤ n 的 L , R L, R L , R ，求出數(shù)組中第 L L L 至第 R R R 個元素的異或和。然后輸出每組 L , R L, R L , R 得到的結果加起來的值。 輸入的第

    2024年02月13日
    瀏覽(89)
  • 第十四屆藍橋杯省賽JavaB組試題E【蝸?！緿ijkstra堆優(yōu)化 or 線性DP？

    第十四屆藍橋杯省賽JavaB組試題E【蝸?！緿ijkstra堆優(yōu)化 or 線性DP？

    ??????????????????????????????????????????????????????????????????????????????????????????????????????? ????????????????????????????????????????????? 第十四屆藍橋杯省賽JavaB組試題E【蝸?！緿ijkstra堆

    2024年02月01日
    瀏覽(22)

  • 藍橋杯2023年第十四屆省賽-飛機降落

    N 架飛機準備降落到某個只有一條跑道的機場。其中第 i 架飛機在 Ti?時刻到達機場上空，到達時它的剩余油料還可以繼續(xù)盤旋 Di?個單位時間，即它最早 可以于 Ti?時刻開始降落，最晚可以于 Ti?+ Di?時刻開始降落。降落過程需要 Li個單位時間。 一架飛機降落完畢時，另一架

    2024年02月15日
    瀏覽(101)

  • 藍橋杯十四屆單片機省賽

    【失敗的博主】藍橋杯最后一文 感想 ： 練完省賽題就去練國賽題?。。?1.B站小蜜蜂老師（基礎模塊 ）（容易聽懂） 2.做一套省賽題、你會發(fā) 現(xiàn)無法把模塊結合起來。 3.學整體代碼的思想（關鍵！!!） 來源：電子設計工坊、四梯科技、官方源代碼、其他人做的題； 4.形成自

    2023年04月10日
    瀏覽(21)
  • 第十四屆藍橋杯Python B組省賽復盤

    第十四屆藍橋杯Python B組省賽復盤

    【問題描述】（5 分） 請求出在 12345678 至 98765432 中，有多少個數(shù)中完全不包含 2023 。 完全不包含 2023 是指無論將這個數(shù)的哪些數(shù)位移除都不能得到 2023 。 例如 20322175，33220022 都完全不包含 2023，而 20230415，20193213 則 含有 2023 (后者取第 1, 2, 6, 8 個數(shù)位) 。 【思路】 正則表達

    2024年02月02日
    瀏覽(20)
  • 藍橋杯嵌入式第十四屆省賽題目解析

    藍橋杯嵌入式第十四屆省賽題目解析

    前幾天剛剛參加完第十四屆的省賽，這屆題目比我想象中的要難，其實想一想這也是應該的，以前的知識點都被摸透了，也是需要加入新的知識點了，但是我還是想說能不能別在我參加的時候加大題目難度啊。 不過聽說隔壁單片機的省賽都比往年的國賽還難，這就有點離譜了

    2024年02月06日
    瀏覽(103)

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請作者喝杯咖啡吧~博客贊助

支付寶掃一掃領取紅包，優(yōu)惠每天領

二維碼1

領取紅包

二維碼2

領紅包