2016年第六届蓝桥杯国赛题解

系统管理员 2022-02-01 15:15 356阅读 0赞

以下题目分值分别为：15，35，25，47，79，99

## 第一题：一步之遥(5min) ##

*  从昏迷中醒来，小明发现自己被关在X星球的废矿车里。 矿车停在平直的废弃的轨道上。 他的面前是两个按钮，分别写着“F”和“B”。
 *  小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。 按F，会前进97米。按B会后退127米。
 *  透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。 他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。  
    或许，通过多次操作F和B可以办到。
 *  矿车上的动力已经不太足，黄色的警示灯在默默闪烁… 每次进行 F 或 B 操作都会消耗一定的能量。
 *  小明飞快地计算，至少要多少次操作，才能把矿车准确地停在前方1米远的地方。
 *  请填写为了达成目标，最少需要操作的次数。
 *  注意，需要提交的是一个整数，不要填写任何无关内容（比如：解释说明等）
 *  答案：97
 *  思路：双重循环，暴力求解  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2NDc0NA_size_16_color_FFFFFF_t_70]
 *  思路： 扩展的欧几里德  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2NDc0NA_size_16_color_FFFFFF_t_70 1]

## 第二题：凑平方数 ##

把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。 比如：0, 36, 5948721
    
    再比如： 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等…
    
    注意，0可以作为独立的数字，但不能作为多位数字的开始。 分组时，必须用完所有的数字，不能重复，不能遗漏。
    
    如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？
    
    注意：需要提交的是一个整数，不要填写多余内容。

## 第三题：棋子换位（43min) ##

有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;  
    }

*  答案：（ i+dd+dd+dd= =6||i+dd+dd+dd==0 )&&data\[i\]!=data\[i+dd+dd\] (我的，推理得出）
 *  valid(data,i-dd)&&valid(data,i+dd+dd)&&data\[i-dd\]!=data\[i\]&&data\[i+dd+dd\]!=data\[i\]（他人的）
 *  思路：
 *      首先把那一行注释掉，发现停止在一段，推测，前方有一步交换错误。
 *      由题意易知，BA，或者，AB不可跳，且可改变位置在交换处
 *      可得到两处交换点故，将其更改做限制在看

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2NDc0NA_size_16_color_FFFFFF_t_70 2]

## 第四题：机器人塔（1h） ##

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

程序应该输出：

*  思路：首先根据m+n求出层数t（三角形的层数不超过50层）
 *  然后从由下而上推出所有情况（动归），每一次都判断得到的三角形是不是满足题目上给的A和B的个数
 *  最后来进行累加su；（递推，DP，深搜）

#include<bits/stdc++.h>
    using namespace std;
    int a[1000],b[1000];
    int n,m,t,su=0;
    int ac(int b[],int ee,int cc)//a[][max]
    {
    	int te=0,bb=ee,c=cc;
    	for(int i=t-1;i>=1;i--)
    	{
    		for(int j=1;j<=i;j++)
    		{
    			if(bb<0||c<0)
    			{
    				te=1;
    				break;
    			}
    			if(b[j]==b[j+1])
    			{
    				b[j]=1;bb--;
    			}
    			else
    			{
    				b[j]=0;c--;
    			} 
    		}
    	}
    	if(te==0&&bb==0&&c==0) return 1;
    	else return 0;
    }
    int bc(int a[ ],int l,int n,int m)
    {
    	if(m<0||n<0) return 0;
    	if(l==t+1)
    	{
    		for(int i=1;i<=t;i++)
    		{
    			b[i]=a[i];
    		}//cout<<n<<" "<<m<<endl;
    		if(ac(b,n,m)==1)
    		{
    			su++;//
    		}
    		return 0;
    	}
    	a[l]=1;
    	//弄了半天 
    	a[l]=1;///
    	bc(a,l+1,n-1,m);//
    	a[l]=0; //
    	bc(a,l+1,n,m-1);//m-1代入，但是m的值并没有变哟
    //	m=m+1;a[l]=1;
    }
    int main()
    {
    	cin>>n>>m;
    	for(int i=1;;i++)
    	{
    		if(n+m==i*(i+1)/2)
    		{
    			t=i;
    			break;
    		}
    	}
    	memset(a,0,sizeof(0));
     	bc(a,1,n,m);
    	cout<<su;
    	return 0;
    }

## 第五题：广场舞 ##

LQ市的市民广场是一个多边形，广场上铺满了大理石的地板砖。

地板砖铺得方方正正，就像坐标轴纸一样。  
以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。

广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。  
舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。  
（广场形状的例子参考【图1.png】）

现在，告诉你广场的形状，请帮LQ市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。

【输入格式】  
输入的第一行包含一个整数n，表示广场是n边形的（因此有n个顶点）。  
接下来n行，每行两个整数，依次表示n边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。

【输出格式】  
输出一个整数，表示最多有多少市民可以在广场跳舞。

【样例输入】  
5  
3 3  
6 4  
4 1  
1 -1  
0 4

【样例输出】  
7

【样例说明】  
广场如图1.png所示，一共有7块完整的地板砖，因此最多能有7位市民一起跳舞。

【数据规模与约定】  
对于30%的数据，n不超过100，横纵坐标的绝对值均不超过100。  
对于50%的数据，n不超过1000，横纵坐标的绝对值均不超过1000。  
对于100%的数据，n不超过1000，横纵坐标的绝对值均不超过100000000（一亿）。

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

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0  
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。  
注意: 所有依赖的函数必须明确地在源文件中 \#include ， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2NDc0NA_size_16_color_FFFFFF_t_70 3]

## 第六题：判定生成树个数 ##

给定一个 n*m 的格点图，包含 n 行 m 列共 n*m 个顶点，相邻的顶点之间有一条边。  
【图1.png】给出了一个3\*4的格点图的例子。

如果在图中删除部分顶点和其相邻的边，如上图删除第2行第3列和第3行第1列的顶点后，如【图2.png】所示。

图的生成树指包含图中的所有顶点和其中的一部分边，使得任意两个顶点之间都有由边构成的唯一路径。如果两个生成树包含有不同的边即被认为不同，则上图中共有31种不同的生成树，其中a边不选有10种，a边选有21种。  
给出格点图中保留的顶点的信息，请计算该图一共有多少种不同的生成树。

【输入格式】  
输入的第一行包含两个整数n, m，用空格分隔，表示格点图的行数和列数。  
接下来n行，每行m个字母（中间没有分隔字符），每个字母必然是大写E或大写N，E表示对应的顶点存在，N表示对应的顶点不存在。保证存在至少一个顶点。

【输出格式】  
输出一行，包含一个整数，表示生成树的个数。答案可能很大，你只需要计算答案除以1000000007的余数即可。

【样例输入】  
3 4  
EEEE  
EENE  
NEEE

【样例输出】  
31  
![在这里插入图片描述][20190514203638496.png]![在这里插入图片描述][20190514203652149.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2NDc0NA_size_16_color_FFFFFF_t_70]: /images/20220201/a5723c9db4de4bcaa472f8786da0470f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2NDc0NA_size_16_color_FFFFFF_t_70 1]: /images/20220201/3aad502b239f455f85fa66b1fddd1c57.png
[AAAB.BB]: http://AAAB.BB
[AABA.BB]: http://AABA.BB
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2NDc0NA_size_16_color_FFFFFF_t_70 2]: /images/20220201/731b319311a942cdb509c25fdd58cb72.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDI2NDc0NA_size_16_color_FFFFFF_t_70 3]: /images/20220201/27abb3d973d8442caf4bbe739204fdc8.png
[20190514203638496.png]: https://img-blog.csdnimg.cn/20190514203638496.png
[20190514203652149.png]: /images/20220201/3acac2bc00cc461ba24e61b741fe876c.png