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

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

    A：煤球数目

  • 等差数列的和$S_n$的前n项和

  • $S_1+S_2+S_3+…+S_n = 1+(1+2)+(1+2+3)+…+(1+2+3+…+n)$

答案：171700
——————————————————————————————————

1
2
3
4
5
   int ans = 0, n = 100;
for(int i = 1; i <= n; ++i){
	ans += i*(n - i + 1);
}
cout << ans << endl;

B：生日蜡烛

答案：20
——————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
   int ans = 0, n = 100;
for(int i = 1; i <= n; ++i){
	ans = i;
	for(int j = i; j <= n; ++j){
		ans += j;
		if(ans == 236){
			cout << i <<" " <<j<< endl;
			return 0;
		}
	}
}

C：凑算式

  • 由题目样例得：结果是通分后相加得10
  • c++提供的next_permutation()在这需要无脑dfs的时候，比较方便

答案：29
——————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int toInt(string s){
	int n;
	stringstream ss;
	ss << s;
	ss >> n;
	return n;
}
int main(){
	int ans = 0;
	string s = "123456789";
	do{
		int a = toInt(s.substr(0, 1));
		int b = toInt(s.substr(1, 1));
		int c = toInt(s.substr(2, 1));
		int d = toInt(s.substr(3, 3));
		int e = toInt(s.substr(6, 3));
		b = b*e;
		d = d*c;
		if((b+d) % (e*c) == 0){
			if((b+d)/(e*c) == (10-a)){
				ans++;
			}
		}
	}while(next_permutation(s.begin(), s.end()));
	cout << ans << endl;
	return 0;
}

F：方格填数

分析

  1. 又是一道可以闭着眼睛next_permutation()全排列的题目
  2. 排列的结果放到方格中，筛选调相邻即可

答案：1580
——————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool judge(char a, char b){	//两个方格是否相邻
	return abs(a-b) == 1;
}
bool solve(string s){	//判断该方案是否合法
	for(int i = 1; i < s.length(); ++i){
		if(judge(s[i], s[i-1])){
			return false;
		}
	}
	if(judge(s[0], s[5]) || judge(s[8], s[5]) || 
		judge(s[1], s[4]) || judge(s[4], s[9]) ||
		 judge(s[0], s[4]) || judge(s[1], s[3]) ||
		 judge(s[9], s[5]) || judge(s[6], s[8]) ||
		 judge(s[0], s[6]) || judge(s[1], s[5]) ||
		 judge(s[7], s[5]) || judge(s[2], s[4]) ||
		 judge(s[4], s[8]) || judge(s[3], s[9]) )
		 	return false;
	return true;
}
int main(){
	int ans = 0;
	string s = "0123456789";
	do{
		if(solve(s)){
			ans++;
		}
	}while(next_permutation(s.begin(), s.end()));
	cout << ans << endl;
	return 0;
}

G：剪邮票

分析

  1. 题意很简单，12个数中选5个数，然后判断是否相连

  2. 排列不组合，可以提前算一下一共$C_{12}^{5}$中可能的排列

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void dfs_1(int k, int step){ //dfs从12个数中排列出5个数 
    if(step == 5){
    	if(solve()){
    		ans++;
    	}
    	return;
    }
    for(int i = k; i < 12; ++i){
    	if(b[i] == 0){
    		b[i] = 1;
    		v.push_back(i+1);	//选取的数加入到vector中 
    		dfs_1(i, step+1);
    		b[i] = 0;
    		v.pop_back();
    	}
    }

  3. 关键是选出了5个数，如何判断他们相连。
    可以先对这5个数进行标记，然后从其中任一个数出发，上下左右开始dfs，将访问到的数的标记擦除；
    一趟结束后，若仍有数未被擦除（即标记还存在），则这5个数不相连，反之，则相连。

***注：12个数里对5个数进行标记，我用的是
string s = "0000000000000"; s[i] = '1';

答案：116
——————————————完整代码————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int b[12];
int ans = 0;
vector<int> v;
string s;
void dfs_2(int k){	//dfs从一个数出发，遍历到所有相连的数 
	s[k] = '0';
	if(k - 4 > 0 && s[k-4] == '1'){
		dfs_2(k-4);	//上
	}
	if((k + 1) % 4 != 1 && s[k+1] == '1'){
		dfs_2(k+1);	//右
	}
	if(k + 4 <= 12 && s[k+4] == '1'){
		dfs_2(k+4);	//下
	}
	if((k-1) % 4 != 0 && s[k-1] == '1'){
		dfs_2(k-1);	//左
	}
}
bool solve(){	//判断这5个数是否连通 
	s = "0000000000000";
	for(int i = 0; i < v.size(); ++i){
		s[v[i]] = '1';		//遍历vector，标记为1 
	}
	//cout << s << endl;
	dfs_2(v[0]);
	if(s.find('1') == string::npos){ 
		return true;	//dfs后没有标记的1，返回true 
	}else{
		return false;
	}
}
void dfs_1(int k, int step){ //dfs从12个数中排列出5个数 
	if(step == 5){
		if(solve()){
			ans++;
		}
		return;
	}
	for(int i = k; i < 12; ++i){
		if(b[i] == 0){
			b[i] = 1;
			v.push_back(i+1);	//选取的数加入到vector中 
			dfs_1(i, step+1);
			b[i] = 0;
			v.pop_back();
		}
	}
} 
int main(){
	dfs_1(0, 0);
	cout << ans << endl;
	return 0;
}

H：四平方和

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//哈希
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

int num[5000005];
int n;
int main(){
	scanf("%d", &n);
	for(int i = 0; i*i <= n; ++i){
		for(int j = i; i*i+j*j <= n; ++j){
			if(num[i*i+j*j] == 0)
				num[i*i+j*j] = j;
		}
	}
	for(int a = 0; a*a <= n; ++a){
		for(int b = a; a*a+b*b <= n; ++b){
			if(num[n-a*a-b*b] != 0){
				int d = num[n-a*a-b*b];
				int c = int(sqrt(n-a*a-b*b-d*d)+1e-3);//sqrt返回值为浮点数，有精度误差
				cout <<a<<" "<<b<<" "<<c<<" "<<d<<endl;		
				return 0;
			}
		}
	}
	return 0;
}

I：交换瓶子

本题很有意思，因此也特意有一篇博客总结了，这里不再赘述
我的博客：·【蓝桥】·交换瓶子
——————————————完整代码————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//精妙的算法往往简洁
#include <iostream>
#include <algorithm>
using namespace std;

int n, ans = 0; 
int a[10005];
int st[10005];
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i){
		if(!st[i]){
			ans++;
			for(int j = i; !st[j]; j=a[j]){
				st[j] = 1;
			}
		}
	}
	printf("%d\n", n-ans);
	return 0;
}