2016第七届蓝桥杯国赛决赛c/c++本科B组试题总结及解题答案

时间:2021-04-18 11:14:01

    16年决赛的真题,个人见解,有不足之处还望指点。(后面两题,我尽量补上)

第一题:一步之遥   

    从昏迷中醒来,小明发现自己被关在X星球的废矿车里。 矿车停在平直的废弃的轨道上。 他的面前是两个按钮,分别写着“F”和“B”。

    小明突然记起来,这两个按钮可以控制矿车在轨道上前进和后退。 按F,会前进97米。按B会后退127米。 
    透过昏暗的灯光,小明看到自己前方1米远正好有个监控探头。 他必须设法使得矿车正好停在摄像头的下方,才有机会争取同伴的援助。 或许,通过多次操作F和B可以办到。

    矿车上的动力已经不太足,黄色的警示灯在默默闪烁… 每次进行 F 或 B 操作都会消耗一定的能量。 
    小明飞快地计算,至少要多少次操作,才能把矿车准确地停在前方1米远的地方。

    请填写为了达成目标,最少需要操作的次数。

    注意,需要提交的是一个整数,不要填写任何无关内容(比如:解释说明等)

解题思路:列一个方程即可:x*97-y*127=1,两重循环即可求出

答案:97

#include <stdio.h>
int main(void)
{
	int i=0,j=0;
	int sum=0;
	for(i=1;i<200;i++)
	{
		for(j=1;j<200;j++)
		{
			if(i*97-j*127==1)
			{
				printf("%d",i+j);
				return;
			}
		}
	}
	return 0;
}

第二题:凑平方数

    把0~9这10个数字,分成多个组,每个组恰好是一个平方数,这是能够办到的。 比如:0, 36, 5948721

    再比如: 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等…

    注意,0可以作为独立的数字,但不能作为多位数字的开始。 分组时,必须用完所有的数字,不能重复,不能遗漏。

    如果不计较小组内数据的先后顺序,请问有多少种不同的分组方案?

    注意:需要提交的是一个整数,不要填写多余内容。


解题思路:有题可知,最大数为9876543210,对其开平方为99380,我们可以先把0~99280之间,数的平方没有重复数字的数存储起来(存储的是平方),然后进行深度搜索。这里可以将每个组中的所有数字都存储在string类型中(操作方便)


参考答案:300


#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX 99380   //对987654321开二次方根

string toString(long long int num);
int judge(string num);
void init();
void search(int start,string number);

long long int NumSaved[MAX];  //NumSaved数组用于保存0~MAX中符合条件的平方数 
int NumLength=0;   //记录NumSaved中存储数据的个数 
int Sum=0;

int main(void)
{
	init();
//	for(int i=0;i<300;i++)	cout<<NumSaved[i]<<endl;  //测试数据
	search(0,"");
	cout<<Sum;
/*	for(int i=0;i<100;i++)   //测试数据
		cout<<toString(i*i)<<endl;*/
	return 0;
}
//搜寻 
void search(int start,string number)
{
	int j = judge(number);
	if(!j) return;
	if(j==11)   //judge中j初始化为1,所以这里是等于11 
	{
		Sum++;
	//	cout<<number<<endl;   //输出查看
		return;
	}
	for(int i=start;i<NumLength;i++)
		search(i+1,number+toString(NumSaved[i]));
}
//判断字符串num中是否含有重复数字 
int judge(string num)
{
	int count[10]={0},i=0,j=1;   //因为search函数刚开始时num=“”,不能让它直接返回,所以初始化为1 
	int len = num.length();
	for(i=0;i<len;i++)
	{
		if(num[i]=='.') continue;
		int tmp = num[i]-'0';
		count[tmp]++;		
		if(count[tmp]>1) return 0;
		j++;
	}
	return j;  //返回 
}
//将数字转换为字符串 
string toString(long long int num)   //错误发生地 
{
	string result = "";
	int tmp = num;
	if(num==0) result += "0";
	while(num!=0)
	{
		char tmp = num%10+'0';
		result.insert(0,1,tmp);  //将字符tmp存放在result字符串数组的0处 
		num/=10;
	}
	result.insert(0,1,'.');   //加'.'便于查错分析 
	return result;
}
//初始化,用NumSaved数组记录0~MAX中平方数没有重复数字的数字 
void init()
{
	long long int i=0;
	for(i=0;i<MAX;i++)
	{
		long long int num = i*i;
		if(judge(toString(num))) NumSaved[NumLength++] = num;
	}
}
第三题:棋子换位

    有n个棋子A,n个棋子B,在棋盘上排成一行。 它们中间隔着一个空位,用“.”表示,比如:

    AAA.BBB

    现在需要所有的A棋子和B棋子交换位置。 移动棋子的规则是: 
    1. A棋子只能往右边移动,B棋子只能往左边移动。 
    2. 每个棋子可以移动到相邻的空位。 
    3. 每个棋子可以跳过相异的一个棋子落入空位(A跳过B或者B跳过A)。

    AAA.BBB 可以走法: 

    移动A ==> AA.ABBB

     移动B ==> AAAB.BB

    跳走的例子: AA.ABBB ==> AABA.BB

    以下的程序完成了AB换位的功能,请仔细阅读分析源码,填写划线部分缺失的内容

源码如下:

#include <stdio.h>  
#include <string.h>  
  
void move(char* data, int from, int to)  
{  
    data[to] = data[from];  
    data[from] = '.';  
}  
  
int valid(char* data, int k)  
{  
    if(k<0 || k>=strlen(data)) return 0;  
    return 1;  
}  
  
void f(char* data)  
{  
    int i;  
    int tag;  
    int dd = 0; // 移动方向  
  
    while(1){  
        tag = 0;  
        for(i=0; i<strlen(data); i++){  
            if(data[i]=='.') continue;  
            if(data[i]=='A') dd = 1;  
            if(data[i]=='B') dd = -1;  
  
            if(valid(data, i+dd) && valid(data,i+dd+dd)   
            && data[i+dd]!=data[i] && data[i+dd+dd]=='.'){   
            //如果能跳...   
                move(data, i, i+dd+dd);  
                printf("%s\n", data);  
                tag = 1;  
                break;  
            }  
        }  
  
        if(tag) continue;  
  
        for(i=0; i<strlen(data); i++){  
            if(data[i]=='.') continue;  
            if(data[i]=='A') dd = 1;  
            if(data[i]=='B') dd = -1;             
  
            if(valid(data, i+dd) && data[i+dd]=='.'){   
            // 如果能移动...  
                if( ______________________ ) continue;  //填空位置   
                move(data, i, i+dd);  
                printf("%s\n", data);  
                tag = 1;  
                break;  
            }  
        }  
  
        if(tag==0) break;                     
    }  
}  
  
int main()  
{  
    char data[] = "AAA.BBB";      
    f(data);  
    return 0;  
}  

解题思路:可以先把填空位置注释掉,多用几个例子("AA.BB","AAAA.BBBB")查一查错误的共性,最后可以发现如果移动位前后字符一样,则不能移动。例如AABA.BB,此时A前后都是B,则不能移动,只能向左移动B.

#include <stdio.h>
#include <string.h>
//从from位置移动到to位置,to位置赋值为from位置的值,from位置设置为空,赋值为'.' 
void move(char* data, int from, int to)  
{
    data[to] = data[from];
    data[from] = '.';
}
//k值边界检查,在边界内返回1,出边界返回0 
int valid(char* data, int k)
{
    if(k<0 || k>=strlen(data)) return 0;
    return 1;
}

void f(char* data)
{
    int i;
    int tag;   //此次移动是否成功 
    int dd = 0; // 移动方向

    while(1){
        tag = 0;
        for(i=0; i<strlen(data); i++){
            if(data[i]=='.') continue;
            if(data[i]=='A') dd = 1;    //dd为1,向右 
            if(data[i]=='B') dd = -1;	//dd为-1,向左 
            
			//跳过相异的一个棋子落入空位,一次 
            if(valid(data, i+dd) && valid(data,i+dd+dd) //边界检查 
            && data[i+dd]!=data[i] && data[i+dd+dd]=='.'){ 
            //如果能跳... 
                move(data, i, i+dd+dd);
                printf("1    %s\n", data);
                tag = 1;
                break;
            }
        }
		//跳棋成功后,继续尝试跳棋 
        if(tag) continue;
		
        for(i=0; i<strlen(data); i++){
            if(data[i]=='.') continue;
            if(data[i]=='A') dd = 1;
            if(data[i]=='B') dd = -1;           

            if(valid(data, i+dd) && data[i+dd]=='.'){ 
            // 如果能移动...
                if(valid(data,i-dd)&&valid(data,i+dd+dd)&&data[i-dd]!=data[i]&&data[i+dd+dd]!=data[i]) continue;  //填空位置 
                move(data, i, i+dd);
                printf("2    %s\n", data);
                tag = 1;
                break;
            }
        }

        if(tag==0) break;                   
    }
}

int main()
{
    char data[] = "AAAA.BBBB";   
	puts(data); 
    f(data);
    return 0;
}

第四题:机器人塔

X星球的机器人表演拉拉队有两种服装,A和B。 他们这次表演的是搭机器人塔。

类似:

 A
B B    
A B A   
A A B B  
B B B A B 
A B A B B A

队内的组塔规则是: 
A 只能站在 AA 或 BB 的肩上。 B 只能站在 AB 或 BA 的肩上。

你的任务是帮助拉拉队计算一下,在给定A与B的人数时,可以组成多少种花样的塔。

输入一行两个整数 M 和 N,空格分开(0<M,N<500),分别表示A、B的人数,保证人数合理性。


要求输出一个整数,表示可以产生的花样种数。


例如:
用户输入:
1 2

程序应该输出:
3

再例如:
用户输入:
3 3

程序应该输出:

4

解题思路:根据输入提供的m,n可以率先确认底层机器人的个数,底层机器人的排列顺序确定了,那么顶层的机器人分布就确定了,这题的普遍思路是深度搜索(可能会超时),我又想了一种思路:既然机器人之后两种状况,那么我可以用二进制数来表示机器人的排列顺序,每一个排列对应一个数,可以减少搜索的时间。两种思路代码都在下面

深度搜索

#include <stdio.h>
#define MAX 45

int getBottom(int n,int m);
void setBottom(int m,int n,int cur,int bottom,int squery[][MAX]);
int count(int bottom,int squery[MAX][MAX],int m,int n);

int M=0,N=0;
int Sum=0;
int main(void)
{
	
	int i=0,j=0,k=0,num=0;
	int bottom;
	int squery[MAX][MAX]={0};
	scanf("%d %d",&M,&N);
	bottom = getBottom(N,M);
	setBottom(0,0,0,bottom-1,squery);
	printf("%d",Sum);
	return 0;
}

//求出最下面一层所有可能 
void setBottom(int m,int n,int cur,int bottom,int squery[][MAX])
{
	if(m>M||n>N) return;
	if(cur==bottom)
	{
		if(count(bottom,squery,m,n))
		{
			Sum++;
			int i=0,j=0;
			for(i=bottom;i>=0;i--)
			{
				for(j=0;j<bottom-i;j++)
				{
					if(squery[i][j]==-1) printf("%-3c",'A');
					else if(squery[i][j]==1) printf("%-3c",'B');
				}
				printf("\n");
			}
		} 
		printf("\n");
		return;
	}
	squery[0][cur] = -1;  //A为-1 
	setBottom(m+1,n,cur+1,bottom,squery);
	squery[0][cur] = 1;   //B为1 
	setBottom(m,n+1,cur+1,bottom,squery);
}
//由于最下面一层确定,则整体确定,对A和B计数 
int count(int bottom,int squery[MAX][MAX],int m,int n)
{
	int i=0,j=0,k=0;
	for(i=1;i<bottom;i++)
	{
		for(j=0;j<bottom-i;j++)
		{
			if(squery[i-1][j]==squery[i-1][j+1])
			{
				squery[i][j] = -1;
				m++;
			}
			if(squery[i-1][j]!=squery[i-1][j+1])
			{
				squery[i][j] = 1;
				n++;
			}
			if(m>M||n>N) return 0;  //如果大于总数,则返回0 
		}
	}
	return 1;
}
//计算出最下面一层的最大个数 
int getBottom(int n,int m)
{
	int limit = n+m;
	int i=0,sum=0;
	for(i=1;i<limit;i++)
	{
		sum+=i;
		if(sum>limit) break;
	}
	return i;
}

二进制表示法

#include <stdio.h>
#include <math.h>
#define MAX 45

int getBottom(int n,int m);
void build(int bottom);

int M=0,N=0;
int Sum=0;
int main(void)
{
	
	int i=0,j=0,k=0,num=0;
	int bottom;
	scanf("%d %d",&M,&N);
	bottom = getBottom(N,M)-1;
	build(bottom);
	printf("%d",Sum);
	return 0;
}

void build(int bottom)
{
	int i=0,j=0,k=0;
	int m=0,n=0;   //二进制中0代表A,1代表B 
	int num=0,pos=1,end=0;
	for(i=0;i<(1<<bottom);i++)
	{
		j = i;  //记录每一层的数量 
		num = 0;
		m=0,n=0;
		k = 0;  //记录二进制移位的次数 
		pos = 1;
		end = bottom;
		
		{
			if(j&1) n++;   //n代表B,代表1 
			else m++;      //m代表A,代表0 
		}
		
		while(k<end)
		{
			int tmp = j&3;
			//计算上一层二进制的数 
			if(tmp==1||tmp==2) num = pos+num;
			pos *= 2;
			//对这一层A,B数目计数 
			if(tmp==0||tmp==1) m++;
			else n++;
			if(n>N||m>M) break;
			
			j = j>>1;
			
			k++;
			if(k==end-1)  //进入上一层 
			{
				j = num;
				num=0;
				pos = 1;
				k=0;
				end--;
				if(j&1) n++;
				else m++;
				if(n>N||m>M) break;
				if(end==1)
				{
					Sum++;
					break;
				}
			}
			
		}
	}
}

//计算出最下面一层的最大个数 
int getBottom(int n,int m)
{
	int limit = n+m;
	int i=0,sum=0;
	for(i=1;i<limit;i++)
	{
		sum+=i;
		if(sum>limit) break;
	}
	return i;
}