[数据结构与算法]2016年第七届C/C++ B组蓝桥杯省赛真题

第一题：煤球数目

题目描述

有一堆煤球，堆成三角棱锥形。具体：
第一层放1个，
第二层3个（排列成三角形），
第三层6个（排列成三角形），
第四层10个（排列成三角形），…
如果一共有100层，共有多少个煤球？
请填表示煤球总数目的数字。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

题目分析

该题目是一个模拟题，首先找出他的规律

• 第一层:1
• 第二层:1+2
• 第三层:1+2+3
• 第四层:1+2+3+4
• 第100层:1+2+…+100

最终的要求是**求所有的煤球数** ,看清题意 很重要哦!

题目代码

#include<bits/stdc++.h>
using namespace std;

int main(){
	int res = 0;
	int temp = 0;
	for(int i = 1;i <= 100; i++){
		temp+=i;//temp:1  1+2  1+2+3
		res += temp;//
	}
	cout<<res<<endl;//171700
	return 0;
}

题目答案

171700

第二题：生日蜡烛

题目描述

某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。
现在算起来，他一共吹熄了236根蜡烛。
请问，他从多少岁开始过生日party的？
请填写他开始过生日party的年龄数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

题目分析

暴力法，两层循环，第一层表示从多少岁过生日，第二层表示当前多少岁了。满足条件就跳出循环。

题目代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
	for(int i = 1;i <=100; i++){
		int temp = i;
		for(int j = i+1; j<= 100;j++) {
			temp += j;
			if(temp==236){
				cout<<i<<" "<<j<<endl;//26 33
			}else if(temp > 236){
				break;
			}
		}
	}
	return 0;
}

题目答案

26

第三题：凑算式

题目描述

/*
凑算式

     B      DEF
A + --- + ------- = 10
     C      GHI
     
（如果显示有问题，可以参见【图1.jpg】）
*/

这个算式中A ~ I代表1~9的数字，不同的字母代表不同的数字。

比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。

这个算式一共有多少种解法？

注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。

题目分析

暴力循环，直接用next_permutation(） .直接写9层for循环也可,但是太low了.

**注意:**根据题目中的样例,可以看出,可以存在分数的加法运算. 所以我们计算时要转换成精度更高的float或者double .最后和10做差值的结果只要 <= 1e-5,则认为相等.

题目代码

#include<bits/stdc++.h>
using namespace std;
int nums[9]  = {1,2,3,4,5,6,7,8,9};// A B C D E F G H I
//全排列
int main() {
	int ans = 0;
	do {
		int A = nums[0],B = nums[1],C = nums[2],D = nums[3],E = nums[4],F = nums[5],G = nums[6],H = nums[7],I = nums[8];
		double m = D*100.0 + E*10 + F;
		double n = G*100.0 + H*10 + I;
		if(fabs(A+B*1.0/C+m/n - 10) <=1e-5) {
			cout<<A<<" "<<B<<" "<<C<<" "<<m<<" "<<n<<endl;
			ans++; 
		}

	} while(next_permutation(nums,nums+9));
	cout<<ans<<endl;//29 
	return 0;
}

//abs:求整数的绝对值 fabs:求float或double的绝对值 
//根据题目中的样例,可以看出,可以存在分数的加法运算. 所以我们计算时要转换成精度更高的float或者double .最后和10做差值的结果只要 <= 1e-5,则认为相等. 

题目答案

29

第六题：方格填数

题目描述

如下的10个格子

+--+--+--+
| | | |
+--+--+--+--+
| | | | |
+--+--+--+--+
| | | |
+--+--+--+

填入0~9的数字。要求：连续的两个数字不能相邻。
（左右、上下、对角都算相邻）

一共有多少种可能的填数方案？

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

题目分析

模拟+全排列+深搜

将数组放到一维数组中,然后进行全排列,将结果 转换成二维数组.然后判断该二维数组是否是一个可行的方案.

题目代码

#include<bits/stdc++.h>
using namespace std;

int nums[10] = {0,1,2,3,4,5,6,7,8,9},map1[4][5],total;
int NEXT[8][2] = {
	-1,0,//上 
	1,0,//下 
	0,-1,//左 
	0,1,//右 
	-1,-1,//左上 
	1,1,//右下 
	-1,1,//右上 
	1,-1//左下 
};

bool check(int x,int y) {//判断该位置 八个方向的数字是否和其相邻 
	//遍历该数的八个方向
	int tx,ty;
	for(int i = 0; i < 8; i++) {
		tx = x+NEXT[i][0];
		ty = y+NEXT[i][1];
		if(tx<1 || tx >3 || ty < 1 || ty > 4){//越界 
			continue;
		}
		if(abs(map1[x][y]-map1[tx][ty])==1) {
			return false;
		}
	}
	return true;
}

void solve() { //判断当前填数方案是否成立
	//将nums放入到map1中  0-9
	int k =  0; 
	for(int i = 1; i<=3; i++){
		for(int j = 1; j<= 4; j++){
			if((i==1&&j==1) || (i==3&&j==4)){//两个特殊位置初始化 
				map1[i][j] = 1000;
				continue;
			}
			map1[i][j] = nums[k++];
		}
	}
	
	//判断每个位置是否符合,只要有一个不符合就结束
	for(int i = 1;i <= 3; i++) {
		for(int j = 1;j <= 4; j++){
			if(!check(i,j)){
				return;
			}
		}
	}
	total++;//都符合,则方案数++ 
	 
}

int main() {
	do {
		solve();
	} while(next_permutation(nums,nums+10));//有几个数就加几啊~~~ 
	cout<<total<<endl;
	return 0;
}

参考答案

1580

第七题：剪邮票

题目描述

如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。

请你计算，一共有多少种不同的剪取方法。

请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

题目分析

直接搜索感觉很难实现,还要考虑去重和回溯的问题. 我们采用的方式是 全排列+深搜

• 可以创建一个数组,存放5个1,7个0,然后我们对其进行全排列(next_permutation()),判断该情况是否成立

• 如何判断:将一维数组转变成二维数组,然后进行深搜,最后统计连通块的个数.

• 如果只有一个连通块,说明该情况成立,否则循环判断下一个排列数.

题目代码

#include<bits/stdc++.h>
using namespace std;

int stamp[12] = { 0,0,0,0,0,0,0,1,1,1,1,1 }, map1[4][5];//一共12张邮票,需要剪下来五张
int NEXT[4][2] = {
	-1,0,//上
	1,0,//下
	0,-1,//左
	0,1//右
};
int ans = 0;//方案数
int book[4][5];//标记是否访问过

void dfs(int x, int y) {
	//结束条件
	if (map1[x][y] == 0) {
		return;//结束
	}

	for (int i = 0; i < 4; i++) {
		int tx = x + NEXT[i][0];
		int ty = y + NEXT[i][1];
		if (tx < 1 || tx>3 || ty < 1 || ty>4) { //判断是否越界
			continue;
		}
		if (!book[tx][ty]) {
			book[tx][ty] = 1;//进行标记
			dfs(tx, ty);//继续深搜
		}
	}
}

bool check() {
	//数据的初始化
	memset(book, 0, sizeof(book));
	int cnt = 0;//邮票连通块的个数
	int w = 0;
	//将一维数组转成二维
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 4; j++) {
			map1[i][j] = stamp[w++];
		}
	}

	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 4; j++) {
			if (map1[i][j] == 1 && !book[i][j]) {
				book[i][j] = 1;//这里一定要注意,先标记后深搜,不然会陷入死循环呢.
				dfs(i, j);//进行深搜
//				book[i][j] = 1;
				cnt++;
			}
		}
	}
	return cnt == 1;//如果只有一个连通块则返回true,否则返回false
}

int main() {
	do {
		if (check()) {
			ans++;
		}
	} while (next_permutation(stamp, stamp + 12));
	cout << ans << endl;
	return 0;
}

参考答案

116

第八题：四平方和

题目描述

四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去，就正好可以表示为4个数的平方和。比如：

5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2 （^符号表示乘方的意思）

对于一个给定的正整数，可能存在多种平方和的表示法。
要求你对4个数排序：0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法
程序输入为一个正整数N (N<5000000), 要求输出4个非负整数，按从小到大排序，中间用空格分开
例如

5
0 0 1 2

再例如

12
0 2 2 2

再例如

773535
1 1 267 838

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms

题目分析

暴力枚举+剪枝

数据量是 5*10^6,直接暴力枚举必定爆!可以采用以下剪枝

• 根据四平方和定理, 数据a,b,c,d范围都是 <= sqrt(n)
• 写四层for必定超时,最后一层可以用 n - (a*a + b*b + c*c) 表示,这样就少了一个循环.
• 第二、三层开始进行剪枝约束。只要值超过 n,则直接break.

最后一个循环中判断a,b,c确定后的d是不是整数.需要用到强制转换.

注意:

• double类型的数据强制转换没有误差,但运行运算时可能出现误差.

• sqrt()的返回值是double类型

• 计算机1s大约运行10^8次,可以根据这个简单判断程序是否超时.

题目代码

#include<bits/stdc++.h> 
using namespace std;

int main(){
	int n;//最多三个循环+剪枝操作
	cin>>n;
	int q =  (int)sqrt(n);//sqrt的返回值是double类型 
	for(int a = 0;a<=q;a++){
		for(int b = 0; b<=q;b++){
			//开始第一轮剪枝
			if(a*a+b*b>n) {//直接结束循环,因为后面的数更大 
				break;
			}
			for(int c = 0; c <=q;c++) {
				//开始第二轮剪枝 
				if(a*a+b*b+c*c > n){
					break;
				}
				double d = sqrt(n - (a*a+b*b+c*c)) ;//判断d是否可以分解成两个整数的平方 
				if(d==(int)d){
					cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
					return 0;
				}
			}
		}
	}
	return 0;
}

第九题：交换瓶子

题目描述

有N个瓶子，编号 1 ~ N，放在架子上。

比如有5个瓶子：2 1 3 5 4

要求每次拿起2个瓶子，交换它们的位置。经过若干次后，使得瓶子的序号为：1 2 3 4 5

对于这么简单的情况，显然，至少需要交换2次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式为两行：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。

输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。

输入样例

样例1

5
3 1 2 5 4
3    

样例2

5
5 4 3 2 1
2

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms

题目分析

使用一个标记数组,在输入元素时,记录元素的位置.之后遍历排序时,如果元素和该位置A应该放置的元素B不同时,根据标记数组找到元素B位置,和当前元素A进行交换. 时间复杂度为 $O(n)$.

题目代码

#include<bits/stdc++.h> 
using namespace std;

const int M = 10000+5;

int arr[M],book[M];//book:标记数组,记录元素的所在.  arr:原始数组 

int main(){
	int n,ans;
	ans = 0;
	cin>>n;
	for(int i = 1; i <= n;i++){
		cin>>arr[i];
		book[arr[i]] = i;
	}
	for(int i = 1; i<= n;i++) {
		if(arr[i]!=i){
			swap(arr[i],arr[book[i]]);
			ans++; 
		}
	}
	cout<<ans<<endl;
	return 0;
}

第十题：最大比例

题目描述

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。并且，相邻的两个级别间的比例是个固定值。

也就是说：所有级别的奖金数构成了一个等比数列。比如：16,24,36,54 其等比值为：3/2

现在，我们随机调查了一些获奖者的奖金数。请你据此推算可能的最大的等比值。

输入格式：
第一行为数字N，表示接下的一行包含N个正整数
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额

要求输出：
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数

测试数据保证了输入格式正确，并且最大比例是存在的。

输入样例

样例1

3
1250 200 32
25/4    

样例2

4
3125 32 32 200
5/2    

样例3

3
549755813888 524288 2
4/1

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms

题目分析

题目代码

待续...

备注:由于蓝桥杯不再考察补全代码题型，所以未整理总结其思路

如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客