“2020年第十届CC++ B组第一场蓝桥杯省赛”

参考https://blog.csdn.net/lihua777/article/details/123464862

1

#include
using namespace std;
int main(){
	int cha=300;
	int a=10000;
	int ans=0;
	while(a){
		if(a-600<0){
			ans=ans*60+a/10;
			break;
		}
		a-=300;
		ans+=2;
	}
	cout<<ans;
}

2

#include
using namespace std;
int day(int year){
	if((year%4==0&&year%100!=0)||(year%400==0)) return 366;
	return 365;
}
int main(){
	int ans=0;
	for(int i=1922;i<=2020;++i){
		ans+=day(i);
	}
	ans-=22;
	cout<<ans*24*60;
}

3

#include
using namespace std;
int main(){
	int ans=0;
	int num=INT_MAX;
	for(int i=1;i<=100;++i){
		if(100%i==0){
			if(100/i+i<num){
				num=100/i+i;
				ans=i;
			}
		}
		else{
			if(100/i+1+i<num){
				num=100/i+1+i;
				ans=i;
			}
		}
	}
	cout<<ans;
}

4

#include
using namespace std;
int main(){
	int a=0;
	for(int i=0;i<2;++i){
		a+=4;
		for(int j=0;j<5;++j){
			for(int k=0;k<6;++k){
				a+=5;
			}
			a+=7; 
		}
		a+=8;
	}
	cout<<a+9;
}

5

#include
using namespace std;
int dp[1017] [1017];
int main(){
	dp[0] [0]=1;
	for(int i=0;i<=1010;++i){
		for(int j=0;j<=i;++j){
			if(i-1>=j) dp[i] [j]+=dp[i-1] [j]%2020;
			if(j-1>=0) dp[i] [j]+=dp[i] [j-1]%2020;
		}
	}
	cout<<dp[1010] [1010];
}

7

#include
using namespace std;
int main(){
	string s;
	string ans="";
	cin>>s;
	for(int i=0;i<s.size();++i){
		int num=s[i]-'0';
		if(num>0&&num<10){
			while(num-1){
				--num;
				ans+=s[i-1];
			}
			continue;
		}
		ans+=s[i];
	}
	cout<<ans;
}

8

#include
using namespace std;
int dp[40][40];
int n,m;
int main(){
	cin>>n>>m;
	dp[1][1]=1;
	for(int i=1;i<=m;++i){
		dp[1][i]=1;
	}
	for(int i=1;i<=n;++i){
		dp[i][1]=1;
	}
	for(int i=2;i<=n;++i){
		for(int j=2;j<=m;++j){
			if(i%2==0&&j%2==0) continue;
			dp[i][j]=dp[i-1][j]+dp[i][j-1];
		}
	}
	cout<<dp[n][m];
}

9

#include
using namespace std;
int n,k;
int a[120];
int ans=0;
bool isk(int x,int y){
	int cnt=0;
	while(y){
		cnt++;
		y/=10;
	}
	x=x*pow(10,cnt)+y;
	if(x%k==0) return 1;
	return 0;
}
int main(){
	cin>>n>>k;
	for(int i=0;i<n;++i){
		cin>>a[i];
	} 
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++i){
			if(isk(a[i],a[j]&&i!=j)) ans++;
		}
	}
	cout<<ans;
}

10 dfs

#include
using namespace std;
int n,m;
int op;
int a,b;
bool g[10100][10100];
bool vis[10100];
int ans[10100];
void dfs(int p,int t){
	vis[p]=1;
	ans[p]+=t;
	for(int i=1;i<=n;++i){
		if(!vis[i]&&(g[p][i]==1||g[i][p]==1)){
			dfs(i,t);
		}
	}
}
int main(){
	cin>>n>>m;
	while(m--){
		int op,a,b;
		cin>>op>>a>>b;
		if(op==1) g[a][b]=g[b][a]=1; 
		else{
			memset(vis,0,sizeof(vis));
			dfs(a,b);
		}
	}
	for(int i=1;i<=n;++i){
		cout<<ans[i]<<" ";
	}
}

并查集模板：

//并查集 
int pre[1000];//前驱数组 
//查找根节点 
int find(int x){
	int r=x;//定义根节点
	//查找根节点 
	while(pre[r]!=r){
		r=pre[r];
	} 
	//路径压缩
	int i=x,tmp;
	while(i!=r){
		tmp=pre[i];
		pre[i]=r;
		i=tmp;
	} 
	return r;//返回根节点 
}
//不压缩简易方法 
int find(int x){
	return f[x]==x?x:(f[x]=find(f[x]));	
} 
//判断连通性
void join(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy) pre[fx]=fy;
} 

并查集做法：

#include
using namespace std;
int n,m;
int ans[10100];
int pre[10100];
int find(int x){
	return pre[x]==x?x:(pre[x]=find(pre[x]));
}
int join(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx!=fy) pre[fy]=fx;
}
void count(int p,int t){
	int fp=find(p);
	for(int i=1;i<=n;++i){
		if(fp==find(i)) ans[i]+=t;
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		pre[i]=i;
	}
	while(m--){
		int op,a,b;
		cin>>op>>a>>b;
		if(op==1){
			join(a,b);
		} 
		else{
			count(a,b);
		}
	}
	for(int i=1;i<=n;++i){
		cout<<ans[i]<<" ";
	}
}