【蓝桥杯第七届省赛】2016

有一堆煤球，堆成三角棱锥形。具体：

第一层放1个，

第二层3个（排列成三角形），

第三层6个（排列成三角形），

第四层10个（排列成三角形），

…

如果一共有100层，共有多少个煤球？

请填表示煤球总数目的数字。

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

题解：

找规律，每一次增加的值是 2,3,4,5,6…

#include 
using namespace std;
int main(int argc, const char * argv[]) {
    int pre=1;
    int plus=2;
    long sum=1;
    for (int k = 2; k <=100 ; ++k) {
        pre=pre+plus;
        sum+=pre;
        plus++;
    }
    cout< 

 
2.生日蜡烛 
某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。
 
现在算起来，他一共吹熄了236根蜡烛。
 
请问，他从多少岁开始过生日party的？
 
请填写他开始过生日party的年龄数。
 
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
 
思路
 
等差数列相关公式
 
 
假设 从 a岁开始过生日，过了 n 年。
 
# include
using namespace std;

int main(){
	int a,n;
	for(a=1;a<=100;a++){
		for(n=1;n<=100;n++){
			if( (n*(n-1))/2+n*a ==236 ){
				cout< 

 
3.凑算式 
     B    DEF

A + ---- + ------- = 10

     C    GHI
 
 
这个算式中AI代表19的数字，不同的字母代表不同的数字。
 
比如：
 
6+8/3+952/714 就是一种解法，
 
5+3/1+972/486 是另一种解法。
 
这个算式一共有多少种解法？
 
题解：
 
 
根据题目的意思：后面的两个分数不一定是可以整除，只要两个分数通分后可以整除即可。
 
用全排列，枚举每一个位置的情况，并判断每一种情况是否可以凑成10.
 
 
#include
using namespace std;

int a[]={1,2,3,4,5,6,7,8,9};
int ans;

//判断每一种情况是否符合条件
bool check(){
	int x = a[3]*100+a[4]*10+a[5];
	int y = a[6]*100+a[7]*10+a[8];
    //要求通分后的分数可以整除 并且 相加结果为10
	if((a[1]*y+a[2]*x)%(y*a[2])==0&&a[0]+(a[1]*y+a[2]*x)/(y*a[2])==10){
		return true;
	}
	return false;
}

int main(){
	do{
		if(check())
			ans++;
	}while(next_permutation(a,a+9));
    //next_permutation 函数用于生成全排列
	cout< 
方法二
 
这里用了自己的写的dfs生成全排列
 
dfs生成全排列
 
#include
using namespace std;

int a[]={1,2,3,4,5,6,7,8,9};
int ans;

bool check(){
	int x = a[3]*100+a[4]*10+a[5];
	int y = a[6]*100+a[7]*10+a[8];
	if((a[1]*y+a[2]*x)%(y*a[2])==0&&a[0]+(a[1]*y+a[2]*x)/(y*a[2])==10){
		return true;
	}
	return false;
}

void f(int k){
	if(k==9){
		if(check())
			ans++;
	}
	
	for(int i=k;i<9;i++){
		{
			int t=a[i];
			a[i]=a[k];
			a[k]=t;
		}
		f(k+1);
		{
			int t=a[i];
			a[i]=a[k];
			a[k]=t;
		}
	}
}

int main(){
//	do{
//		if(check())
//			ans++;
//	}while(next_permutation(a,a+9));
	f(0); 
	cout< 

 
4.快速排序 
快速排序
 
排序在各种场合经常被用到。
 
快速排序是十分常用的高效率的算法*
 
其思想是：先选一个“标尺”，
 
用它把整个队列过一遍筛子，
 
以保证：其左边的元素都不大于它，其右边的元素都不小于它。
 
这样，排序问题就被分割为两个子区间。
 
再分别对子区间排序就可以了。
 
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
 
#include 

void swap(int a[], int i, int j)
{
	int t = a[i];
	a[i] = a[j];
	a[j] = t;
}

int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];
    while(1){
        while(ix);
        if(i>=j) break;
        swap(a,i,j);
    }
	______________________;
    return j;
}

void quicksort(int a[], int p, int r)
{
    if(p 
题解：
 
#include 
#include 
using namespace std;
void swap(int a[], int i, int j)
{
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];//左端点的值
    // !! 这里 x 是标尺
    while(1){
        while(ix);
        if(i>=j) break;
        swap(a,i,j);
    }
    //while循环结束后，此时标尺左右两边的数组都已排好序
//    ______________________;
    //接下来就是要将 标尺 放到正确的位置上
    swap(a,p,j);
    return j;
}

void quicksort(int a[], int p, int r)
{
    if(p 

 
5.抽签 
X星球要派出一个5人组成的观察团前往W星。
 
其中：
 
A国最多可以派出4人。
 
B国最多可以派出2人。
 
C国最多可以派出2人。
 
…
 
那么最终派往W星的观察团会有多少种国别的不同组合呢？
 
下面的程序解决了这个问题。
 
数组a[ ] 中是每个国家可以派出的最多的名额。
 
程序执行结果为：
 
DEFFF
 
CEFFF
 
CDFFF
 
CDEFF
 
CCFF
 
CCEFF
 
CCDFF
 
CCDEF
 
BEFF
 
BDFFF
 
BDEFF
 
BCFFF
 
BCEFF
 
BCDFF
 
BCDEF
 
…
 
(以下省略，总共101行)
 
#include 
#define N 6
#define M 5
#define BUF 1024

void f(int a[], int k, int m, char b[])
{
	int i,j;

	if(k==N){
		b[M] = 0;
		if(m==0) printf("%sn",b);
		return;
	}

	for(i=0; i<=a[k]; i++){
		for(j=0; j 
题解：
 
#include 
#define N 6
#define M 5
#define BUF 1024
int ans;

//共 K 个国家，要求出 m 个人
void f(int a[], int k, int m, char b[])
{
    int i,j;

    if(k==N){
        b[M] = 0;//字符串结尾的标志
        if(m==0) {
            printf("%sn",b);
            ans++;
        }
        return;
    }

    for(i=0; i<=a[k]; i++){//试着将k国家，派出i人
        for(j=0; j 

 
6.方格填数 
如下的10个格子
 
   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+
 
填入0~9的数字。要求：连续的两个数字不能相邻。
 
（左右、上下、对角都算相邻）
 
一共有多少种可能的填数方案？
 
题解：
 
题目给的是 3*4的方格，但是对于边界的格子要判断它的四周，就在整个格子的外侧再放一层。即 5*6
 
从第一个格子开始搜。
 
#include 
#include 
using namespace std;
//3*4
// 5*6

bool vis[10]; // vis数组记录每个数字有没有用过
int pos[5][6];
int ans;//最终情况

bool check(int i,int j){//检查这种走法
	for(int x=i-1;x<=i+1;x++){
		for(int y=j-1;y<=j+1;y++){
			if(abs(pos[x][y]-pos[i][j])==1)
				return false;
		}
	}
	return true;
}

void dfs(int x,int y){
    //最后一个格子也搜完了
	if(x==3&&y==4){
		ans++;
		return;
	}
	
    //每个格子的值为 0~9
	for(int i=0;i<10;i++){
		if(vis[i]==0){//这个数字没有被用过
			pos[x][y]=i;
			if(!check(x,y)){//不合法，恢复，跳出这种填法
				pos[x][y]=-10;
				continue;
			}
			vis[i]=1;
			if(y==4){//如果走到了这一行的最后一个格子
				dfs(x+1,1);//换行
			}else{
				dfs(x,y+1);//继续搜下一个
			}
			
			{//回溯
				vis[i]=0;
				pos[x][y]=-10;
			}
		}
	}
}

int main()
{
    //初始化所有格子，将格子赋值为-10，相当于未走过，以后会给格赋值为 0~9
	for(int i=0;i<5;i++){
		for(int j=0;j<6;j++){
			pos[i][j]=-10;
		}
	}
	
    //从第一个格子开始搜
	dfs(1,2);
	cout< 

 
7.剪邮票 
 
如图，有12张连在一起的12生肖的邮票。
 
现在你要从中剪下5张来，要求必须是连着的。
 
（仅仅连接一个角不算相连）
 
比如，下图中，粉红色所示部分就是合格的剪取。
 
 
 
请你计算，一共有多少种不同的剪取方法。
 
请填写表示方案数目的整数。
 
题解：
 
单纯的dfs无法解决T字型连通方案。
 
本题的解决方法是，找出任意5个格子，判断是否连通。
 
步骤：
 
先用一个大小为12 的数组，里面存放 5个1，剩余全为0. 这个数组代表1~12，将这个数组生成全排列，代表每次随机选出来的5个格子。用一个数组path[12]接收每个下标为 i 的数字是否被选中。
 
接下来判断这5个格子是否连通。用刚才生成的path数组生成3*4的地图g[]，然后对地图g 上的每个点作为起点来判断，是否连通。
 
#include
using namespace std;

int a[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
int ans;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
void dfs(int g[3][4],int i,int j){
	g[i][j]=0;//先将这个格子设置为0
	for(int k=0;k<4;k++){
		int tx=i+dx[k];
		int ty=j+dy[k];
		if(tx>=0&&tx<=2&&ty>=0&&ty<=3&&g[tx][ty]==1){
			dfs(g,tx,ty);
		}
	}
}

bool check(int path[12]){//这里的path数组已经选出了5个数
	int g[3][4];//生成的地图g[]
	for(int i=0;i<3;i++){
		for(int j=0;j<4;j++){
			if(path[i*4+j]==1) g[i][j]=1;
            //path[i*4+j]表示每一个数，因为一行有4个数字，i是它的行数
			else g[i][j]=0;
		}
	}
	int cnt=0;//cnt记录连通块的数目 
	
	//现在已经给3*4的格子赋完值了，开始dfs找连通块
	for(int i=0;i<3;i++){
		for(int j=0;j<4;j++){
			if(g[i][j]==1){
				dfs(g,i,j);
				cnt++;//因为在dfs判断连通块时，将走过的格子设为0，所以最后只能搜到一个连通块，即cnt应该=1
			}
		}
	} 
	return cnt==1;
}

bool vis[12];//vis数组记录每个数字是否被用过
//f函数生成全排列，并对每次生成的排列进行判断
void f(int k,int path[12]){
	if(k==12){
		if(check(path)){
			ans++;
		}
	}
	for(int i=0;i<12;i++){
        //因为有重复的数字，这一步是为了生成的全排列不重复
		if(i>0&&a[i]==a[i-1]&&!vis[i-1]) continue;
		
		if(!vis[i]){
			vis[i]=true;
			path[k]=a[i];
			f(k+1,path);
			vis[i]=false;
		}
	}
}

int main(){
	int path[12];//path数组用来判断1~12每个数字是否选择
	f(0,path);
	printf("%d",ans);
	return 0;
}

 
方法二：
 
通过next_permutation函数来生成全排列。
 
#include
using namespace std;

int a[] = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1};
int ans;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
void dfs(int g[3][4],int i,int j){
	g[i][j]=0;
	for(int k=0;k<4;k++){
		int tx=i+dx[k];
		int ty=j+dy[k];
		if(tx>=0&&tx<=2&&ty>=0&&ty<=3&&g[tx][ty]==1){
			dfs(g,tx,ty);
		}
	}
}

bool check(int path[12]){
	int g[3][4];
	for(int i=0;i<3;i++){
		for(int j=0;j<4;j++){
			if(path[i*4+j]==1) g[i][j]=1;
			else g[i][j]=0;
		}
	}
	int cnt=0;//cnt记录连通块的数目 
	
	//现在已经给3*4的格子赋完值了，开始dfs找连通块
	for(int i=0;i<3;i++){
		for(int j=0;j<4;j++){
			if(g[i][j]==1){
				dfs(g,i,j);
				cnt++;
			}
		}
	} 
	return cnt==1;
}

bool vis[12];
//void f(int k,int path[12]){
//	if(k==12){
//		if(check(path)){
//			ans++;
//		}
//	}
//	for(int i=0;i<12;i++){
//		if(i>0&&a[i]==a[i-1]&&!vis[i-1]) continue;
//		
//		if(!vis[i]){
//			vis[i]=true;
//			path[k]=a[i];
//			f(k+1,path);
//			vis[i]=false;
//		}
//	}
//}

int main(){
	do{
		if(check(a)) 
			ans++;
	}while(next_permutation(a,a+12));

//	int path[12];
//	f(0,path);
	printf("%d",ans);
	return 0;
}

 

 
8.四平方和 
四平方和定理，又称为拉格朗日定理：
 
每个正整数都可以表示为至多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
 
题解：
 
最容易想到的方法是用3重循环，但会超时。
 
正解：
 
先用两重for循环，枚举 c 和 d 的值，并将 c2+d2 的值存储到 map中，
 
c：c^2 的值最大为 N/2 , 因为 c 后面还有 d，所以最大值可以取到 N/2.
 
然后再用 for循环枚举 a 和 b，在每次循环中判断 c 和 d 的值，判断是否合法，若合法，直接结束程序。
 
#include 
using namespace std;

int N;
map cache;

int main()
{
	scanf("%d",&N);
	for(int c=0;c*c<=N/2;c++){
		for(int d=c;c*c+d*d<=N;d++){
			if(cache.find(c*c+d*d)==cache.end()){//这种值未出现过 
				cache[c*c+d*d]=c;//记录它，并将它的值设为 c的值 
			}
		}
	}
	
	for(int a=0;a*a<=N/4;a++){
		for(int b=a;a*a+b*b<=N/2;b++){
			if(cache.find(N-a*a-b*b)!=cache.end()){//可以找到 c 和 d 的值
				int c = cache[N-a*a-b*b];
				int d = sqrt(N-a*a-b*b-c*c);
				printf("%d %d %d %dn",a,b,c,d); 
				return 0;
				
			}
		}
	} 
    return 0;
}
 

 
9.交换瓶子 
有N个瓶子，编号 1 ~ N，放在架子上。
 
比如有5个瓶子：
 
2 1 3 5 4
 
要求每次拿起2个瓶子，交换它们的位置。
 
经过若干次后，使得瓶子的序号为：
 
1 2 3 4 5
 
对于这么简单的情况，显然，至少需要交换2次就可以复位。
 
如果瓶子更多呢？你可以通过编程来解决。
 
输入格式为两行：
 
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
 
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
 
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
 
例如，输入：
 
5
 
3 1 2 5 4
 
程序应该输出：
 
3
 
再例如，输入：
 
5
 
5 4 3 2 1
 
程序应该输出：
 
2
 
题解：
 
遍历每一个位置的瓶子，如果这个瓶子在它本来应该在的地方，那就直接 continue。
 
如果不在它应该在的位置，那就 与它应该在的地方进行交换。
 
#include 
using namespace std;

int n;
int a[10005];
int ans; 

//找到标号为 x 的瓶子目前的位置 
int pos(int x){
	for(int i=1;i<=n;i++){
		if(a[i]==x) return i;
	}
	return -1;
}

//交换下标为 i 和 j 的瓶子 
void swap(int i,int j){
	int t=a[i];
	a[i]=a[j];
	a[j]=a[i];
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	//遍历每个瓶子 
	for(int i=1;i<=n;i++){
		//如果它的标号和它的下标相同，直接跳过当前循环 
		if(a[i]==i) continue;
		else{
			//pos(i)表示的是当前瓶子应该在的地方 
			swap(pos(i),i);
			ans++;
		}
	}
	printf("%dn",ans);
    return 0;
}
 

 
10.最大比例 
X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。
 
并且，相邻的两个级别间的比例是个固定值。
 
也就是说：所有级别的奖金数构成了一个等比数列。比如：
 
16,24,36,54
 
其等比值为：3/2
 
现在，我们随机调查了一些获奖者的奖金数。
 
请你据此推算可能的最大的等比值。
 
输入格式：
 
第一行为数字 N (0 
第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖数额
 
要求输出：
 
一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数
 
测试数据保证了输入格式正确，并且最大比例是存在的。
 
例如，输入：
 
3
 
1250 200 32
 
程序应该输出：
 
25/4
 
再例如，输入：
 
4
 
3125 32 32 200
 
程序应该输出：
 
5/2
 
再例如，输入：
 
3
 
549755813888 524288 2
 
程序应该输出：
 
4/1