蓝桥杯第七届决赛(国赛)C++B组 第四题 机器人…

2018-06-17 20:37:46来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折


机器人塔

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

  

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:最新工控\建模仿真\组态\监控集成开发平台源码解决方案2018

下一篇:Windows编译Opencv