2017年蓝桥杯省赛题解（无E、F、J题）

历届真题可直接在官网下载，链接：蓝桥杯大赛历届真题

A：购物单

数据导入到word，替换调没用的，插入-文本替换为表格
全选表格复制到excel中，计算即可

答案：5200

B：等差素数列

人有多大胆，地有多大产
填空题，请放心枚举

分析

先打个素数表出来，然后开始枚举，枚举素数、枚举公差、枚举后九项。。。
至于素数表的长度、公差的大小范围，灵活变动即可

#include <iostream>

using namespace std;

const int maxn = 1e5 + 5;
const int INF = 1e6+5;
int prime[maxn];    //记录素数
bool judge(int n){
	for(int i = 2; i*i <= n; ++i){
		if(n % i == 0){
			return false;
		}
	}
	return true;
}
int solve(){    //统计素数
	int cnt = 0;
	for(int i = 2; i < INF; ++i){
		if(judge(i)){
			prime[cnt++] = i;
		}
	}
	return cnt;
}
int main(){
	int cnt = solve();
	cout <<cnt << " "<< prime[cnt-1]<<endl;
	for(int i = 0; i < cnt; ++i){   //枚举素数
		//cout << i << endl;
		for(int k = 2; k < 1000; ++k){  //枚举公差
			int j;
			for(j = 1; j <= 9; ++j){    //枚举10项
				if(!judge(prime[i]+k*j)){
					break;
				}
			}
			if(j == 9){
				cout << k<<":"<<prime[i] << endl;
				return 0;
			}
		}
	}
	return 0;
}

答案：210

C：承重计算

每个金属的质量会平均分给下一层的两层金属
double双精度存金属的质量，遍历到最后一层得到质量最大和最小的金属maxx, minn
电子秤显示的是放大倍数后的质量，所以结果取2086458231 / minn * maxx

double a[50][50];
int main(){
	int n = 30;
	for(int i = 1; i < n; ++i){
		for(int j = 1; j <= i; ++j){
			double temp;
			scanf("%lf", &temp);
			temp += a[i][j];
			temp /= 2;
			a[i+1][j] += temp;
			a[i+1][j+1] += temp;
		}
	}
	double maxx = a[n][1];
	double minn = a[n][1];
	for(int i = 1; i <= n; ++i){
		maxx = max(maxx, a[n][i]);
		minn = min(minn, a[n][i]);
	}
	cout << minn << endl;
	cout << maxx << endl;
	printf("%lf", 2086458231 / minn * maxx);
	//cout << 2086458231 / minn * maxx << endl;
	return 0;
}

答案：72665192664

D：方格分割

特意有一篇博客总结了，这里不再赘述
我的博客：·【蓝桥】·方格分割
——————————————完整代码————————————————

#include <iostream>

using namespace std;

int a[7][7];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int ans = 0;
void dfs(int x, int y){
	if(x==0 ||y==0 || x==6 || y==6){  //走到边界就成功了
		ans++;
		return;
	}
	a[x][y] = 1;
	a[6-x][6-y] = 1;    //对称的点也标记
	for(int i = 0; i < 4; ++i){
		int xe = x + dx[i];
		int ye = y + dy[i];
		if(a[xe][ye] == 1){
			continue;
		}
		dfs(xe, ye);
		a[xe][ye] = 0;
		a[6-xe][6-ye] = 0;
	}
} 
int main(){
	dfs(3, 3);
	cout << ans/4 <<endl;
	return 0;
}

G：日期问题

题目来源：·【Acwing】·日期问题
题目分析

最多就三种情况，输出合法的日期格式即可
注意多个日期要求从早到晚输出，食用set最佳

***附几处容易遗漏的bug：

==天数不为0==
- 输入：02/02/00 输入：2002/02/00
==闰年的2月29日合法==
==日期去重、排序==

——————————————完整代码————————————————

#include <iostream>
#include <cstdio>
#include <sstream>
#include <algorithm>
#include <set>

using namespace std;
/*
1960 1 1
2059 12 31
02/02/00
04/02/29
02/02/02
*/
set<string> v;
int months[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int toInt(string s){
	int t;
	stringstream ss;
	ss << s;
	ss >> t;
	return t;
}
string toString(int t){
	stringstream ss;
	ss << t;
	return ss.str();
}
bool must(string y, string m, string d){ //判断天数是否合法
	int yy = toInt(y);
	int mm = toInt(m);
	int dd = toInt(d);
	if(dd == 0){
		return false;
	}
	if((yy%4==0&&yy%100!=0) || yy%400==0){
		if(mm == 2 && dd == 29){
			return true;
		}
	}
	if(months[mm] < dd){
		return false;
	}else{
		return true;
	}
}
int judge(string y, string m, string d){//先判断年、月是否合法
	if((y[0] - '0') <= 5){	//处理年份
		y = "20" + y;
	}else{
		y = "19" + y;
	}
	//cout << y << endl;
	if(m[0] == '0'){		//处理月份
		if(m[1] == '0' || !must(y, m, d)){
			return -1;
		}
	}else if(m[0] == '1'){
		if(m[1] == '0' || m[1] == '1' || m[1] == '2'){
			if(!must(y, m, d)){
				return -1;
			}
		}else{
			return -1;
		}
	}else{
		return -1;
	}
	return toInt(y);
}
void solve(string y, string m, string d){ //合法，加入set集合中
	int t = judge(y, m, d);
	if(t != -1){
		string ans = toString(t)+"-"+m+"-"+d;
		v.insert(ans);
		//cout << toString(t)+"-"+m+"-"+d << endl;
	} 
}
int main(){
	string s;
	cin >> s;
	string s1 = s.substr(0, 2);
	string s2 = s.substr(3, 2);
	string s3 = s.substr(6, 2);
	solve(s1, s2, s3);
	solve(s3, s1, s2);
	solve(s3, s2, s1);
	for(set<string>::iterator i = v.begin(); i != v.end(); ++i){
		cout << *i<< endl;	//遍历输出即可
	}
	return 0;
}

H：包子凑数

题目来源：·【Acwing】·包子凑数
特意有一篇博客总结了，这里不再赘述
我的博客：·【蓝桥】·包子凑数
——————————————完整代码————————————————

#include <iostream>

using namespace std;

int n;
int a[105];
bool b[10005];
int gcd(int a, int b){
	return b ? gcd(b,a%b) : a;
}
void solve(){
	int ans = 0;
	b[0] = true;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j+a[i] < 10005; ++j){
			if(b[j]){
				b[j+a[i]] = true;
			}
		}
	}
	for(int i = 1; i < 10005; ++i){
		if(!b[i]){
			ans++;
		}
	}
	printf("%d\n", ans);
}
int main(){
	scanf("%d", &n);
	for(int i = 0 ; i < n; ++i){
		scanf("%d", &a[i]);
	}
	int g = 0;
	for(int i = 0; i < n; ++i){
		g = gcd(g, a[i]);
	}
	if(g == 1){		//互质，则有确定无解的个数
		solve();
	}else{
		printf("INF\n");
	}
	return 0;
}

I：分巧克力

题目来源：·【Acwing】·分巧克力

分析

例如样例中的5 6可分得的以2为边长的巧克力6块（(5/2)(6/2) = 6）;
或者分得以3为边长的巧克力2块（(5/3)(6/3) = 2）
设最大边长为m，判断能否够分，只需遍历n块，累加结果若cnt>=k则够分
很容易想到二分边长m，n log n的规模正好满足

***注：优雅的进行二分时，要牢记循环结束的标志while(l <= r)，以及最终结果的输出
——————————————完整代码————————————————

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
/*
2 4  
6 5  
5 6
*/
int n, k;
int ans = 0;
const int maxn = 1e5 + 5;
struct note{
	int x, y;
}a[maxn];
int judge(int m){	//判断以m为边长分巧克力是否满足题意
	int cnt = 0;
	for(int i = 0; i < n; ++i){
		cnt += (a[i].x/m)* (a[i].y/m);
	}
	return (k <= cnt);
}
int main(){
	scanf("%d%d", &n, &k);
	int maxx = -1;
	for(int i = 0; i < n; ++i){
		int xv, yv;
		scanf("%d%d", &xv, &yv);
		a[i].x = xv;
		a[i].y = yv;
		maxx = max(maxx, max(xv, yv));	//取最大的边开始二分
	}
	int l = 1, r = maxx;
	while(l <= r){
		int mid = (l + r)>>1;
		if(judge(mid)){
			l = mid + 1;
		}else{
			r = mid - 1;
		}
	}
	cout << r << endl;	//输出的是r
	return 0;
}

题目

蓝桥

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

2016年蓝桥杯省赛题解（无D、E、J题）上一篇

2018年蓝桥杯省赛题解（无E、J题）下一篇