2022年蓝桥杯省赛真题解析（C++B组）

2022.4.9  记录我第一次参加蓝桥杯

填空

答案：1478

答案4

感觉012三个连续的应该不算

 7天做5a+2b道题，算n中有几个5a+2b，再算还需要几天

#include<iostream>
using namespace std;
int main(){
	long long a,b,n;
	cin>>a>>b>>n;
	int day=0;
	day+=(n/(5*a+2*b))*7;
	int d=n%(5*a+2*b);
	int d1=0;
	d1+=a;
	if(d1>=d){
		cout<<day+1;
		return 0;
	}
	d1+=a;
	if(d1>=d){
		cout<<day+2;
		return 0;
	}
	d1+=a;
	if(d1>=d){
		cout<<day+3;
		return 0;
	}
	d1+=a;
	if(d1>=d){
		cout<<day+4;
		return 0;
	}
	d1+=a;
	if(d1>=d){
		cout<<day+5;
		return 0;
	}
	d1+=b;
	if(d1>=d){
		cout<<day+6;
		return 0;
	}
	d1+=b;
	if(d1>=d){
	  cout<<day+7;
	  return 0; 
	} 
	 
	
}

通过模拟，发现当修剪两个回合后就会重复，所以只要循环两个回合。注意当循环到最后一个和第一个注意变向.

#include<iostream>
#include<cstring>
using namespace std;
int n;
int h[10001];
int m[10001];
int flag;
int main(){
	cin>>n;
	memset(h,0,sizeof(h));
	memset(m,0,sizeof(m));
	int index=1;
	flag=0;
	for(int k=0;k<3*n;k++){
	 for(int i=1;i<=n;i++){
		h[i]++;
		m[i]=max(h[i],m[i]);
	 }
	 h[index]=0;
	 if(index==1){
	 	flag=0;
	 }
	 if(index==n){
	 	flag=1;
	 }
	 if(flag==0){
	 	index++;
	 }
	 else{
	 	index--;
	 } 
    }
	for(int i=1;i<=n;i++){
		cout<<m[i]<<endl;
	}
	return 0;
	
}

 这题卡了我好长时间~

一开始不知道为什么321转化为65。后来通过一个个数枚举发现了规律。

321=3*10*2+2*2+1

然后这题用贪心

#include<iostream>
using namespace std;
int n;
int ma;
int a[100000];
int mb;
int b[100000];
int c[100000];
int jin[100000];
int main(){
	cin>>n;
	cin>>ma;
	for(int i=ma;i>=1;i--){
		cin>>a[i];
	}
	cin>>mb;
	for(int i=mb;i>=1;i--){
		cin>>b[i];
	}
	jin[0]=1;
	for(int i=1;i<=max(ma,mb);i++){
		c[i]=a[i]-b[i];
		if(c[i]>=0){
		   if(a[i]<=2&&b[i]<=2){
		   	jin[i]=2;
		   }
		   else{
		   	jin[i]=max(a[i],b[i])+1;
		   }
		}
		else{
			jin[i]=n;
		}
	}

	
	int sum=0;
	for(int i=1;i<=max(ma,mb);i++){
		int s=1;
		for(int k=0;k<i;k++){
			s*=jin[k];
		}
		sum+=c[i]*s;
	}
	cout<<sum;
	return 0;
}
	

不会化简，前缀和预处理之后，直接暴力写 

#include<iostream>
#include<cstring>
using namespace std;
int n,m,k;
int num[501][501];
int sum[501][501];
int sum1[501][501];
int a[501];
int dp[501];
void input(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>num[i][j];
		}
	}
}
void init_sum() {
	memset(sum, 0, sizeof(sum));
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; i++) {
			sum[i][j] = sum[i - 1][j] + num[i][j];
		}
	}
}

int cnt(int a[]){
	int cnt=0;
	int sum=0;
	for(int i=1;i<=m;i++){
		for(int j=i;j<=m;j++){
			sum=0;
		      for(int k=i;k<=j;k++){
		      	sum+=a[k];
		      }
		      if(sum<=k)
		      cnt++;
		}
	}
	return cnt;
}
int main(){
	input();
	init_sum();
	int count=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			for(int l=1;l<=m;l++){
				a[l]=sum[j][l]-sum[i-1][l];
				
			}
			count+=cnt(a);
		}
	}
	cout<<count;
	return 0;

} 

/*
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
*/ 

不会。。。。

 这题我用dfs连通分量写的。

火箭和雷统一可以看成一个半径为r的圆，圆心距小于半径时（d<=r）时，说明两个圆邻接。用grid[x][y]记录编号为x，y的圆是否邻接

#include<iostream>
#include<cmath> 
using namespace std;
int n, m;
int grid[5000][5000];
struct node {
	int x, y, r;
	node() {
	}
	node(int _x, int _y, int _r) {
		x = _x;
		y = _y;
		r = _r;
	}
}no[50001];
void input() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> no[i].x >> no[i].y >> no[i].r;
	}
	for (int i = n+1; i <= n+m; i++) {
		cin >> no[i].x >> no[i].y >> no[i].r;
	}
}
double dis(int i, int j) {
	return sqrt((no[i].x - no[j].x) * (no[i].x - no[j].x) + (no[i].y - no[j].y) * (no[i].y - no[j].y));
}
int cnt = 0;
void dfs(int n) {

	for (int i = 1; i <= n + m; i++) {
		if (grid[n][i] == 1 && n != i) {
			grid[n][i] =grid[i][n]=0;
			cnt++;
			dfs(i);
		}
	}
}
int main() {
	input();
	for (int i = 1; i <= n+m; i++) {
		for (int j = 1; j <= n+m; j++) {
			if (dis(i, j)<=no[i].r) {
		
				grid[i][j]=1;
			}
		}
	}
	for (int i = n + 1; i <= n + m; i++) {
		dfs(i);
	}
	cout << cnt;
}

这题我用dfs+ 记忆化搜索

#include<iostream>
#include<cstring>
using namespace std;
int N, M;
int dp[1000][101][101];
int dfs(int sum, int n, int m) {
    if (sum < 0)return 0;
	if (n > N)return 0;
	if (m > M - 1)return 0;
	if (dp[sum][n][m])return dp[sum][n][m]%1000000007;
	if (sum == 1 && n == N && m == M - 1)return 1;
	dp[sum][n][m] =(dfs(2 * sum, n + 1, m) + dfs(sum - 1, n, m + 1))%1000000007;
	return dp[sum][n][m];
}
int main() {
	memset(dp, 0, sizeof(dp));
	cin >> N >> M;
	cout << dfs(2, 0, 0);
}

 不会。。。。