蓝桥杯第七届决赛（国赛）C++B组 第四题 机器人塔

机器人塔

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

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

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

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

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

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

 

　　

　　

　　这道题确实有点恶心，开始想了好多办法都错了。。。。比如列举底层全排列，显然有重有漏。底层dp基本没结果。

　　不过可以确定，不论是从底层开始该排列唯一。从顶层开始则为DFS，这里不进行证明！

说一下思路，顶层开始每一个位置都是 A或者B，尝试AB推导法则：

　　　　　　　　　　仔细观察，每层第i个和上层第i个有异或运算A^B=B ,A^A=A,B^B=A,B^A=B。   好了，本题基本结束。

　　　　　　　　　　　　　　map[line][i]=map[line][i-1]^map[line-1][i-1];

　　解题时间（2.5hour）

//代码思路

//0表A，1表B，存在二维数组map中，进行DFS
//每一行的上层确定并且每行第一个数字确定，该行唯一
//所以本题就是DFS每行第一个

//为什么敢开50*50二维数组，下面进行公式推导
//题意，A和B的总数cnt<999,设一共可以摆n行,等差数列求和 cnt=n*n(n+1)/2
//得到n最大为44

　　不懂再问，下面给出代码：

#include<iostream> 
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<stdio.h>
#define ll long long 
using namespace std;
int ans;
int map[50][50];        
void DFS(int line,int re_A,int re_B,int n)    //line 当前行 re_A 可用的A   re_B 可用的B  n代表层数
{
	int A=re_A;
	int B=re_B;
	
	if(re_A<0||re_B<0)
		return;
	if(line == n&&A==0&&B==0)
	{
		ans++;
		return;
	}
		re_A=A;
		re_B=B;
		map[line][0]=0;
		re_A-=1;
		for(int i=1;i<=line;i++)
		{
			map[line][i]=map[line][i-1]^map[line-1][i-1];
			if(map[line][i]==0){
			
				re_A--;
			}
			else{
			
				re_B--;
			}
		}
		DFS(line+1,re_A,re_B,n);
		
		
		
		re_A=A;
		re_B=B;
		map[line][0]=1;
		
		re_B-=1;
		for(int i=1;i<=line;i++)
		{
			map[line][i]=map[line][i-1]^map[line-1][i-1];
			if(map[line][i]==0)
				re_A--;
			else
				re_B--;
		}
		DFS(line+1,re_A,re_B,n);
	
}
int main()
{
	int x,y,n;
	while(cin>>x>>y)
	{
		ans=0;
		for(int i=1;;i++)
		{
			if(2*x+2*y==i*i+i)
			{
				n=i;
				break;
			}
		}
		DFS(0,x,y,n);
		
		cout<<ans<<endl;
		
	}
}