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