蓝桥杯刷题023——机器人塔(DFS)
创始人
2024-05-24 04:46:32
0

2016国赛

题目描述

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

输出描述

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

输入输出样例

输入

1 2

输出

3

题目大意

给出A,B两类机器人,让它们按—定规则堆成三角形塔,问可堆成的方案数
规则:

A只能放在AA,BB上B只能放在AB,BA上

思考:如何确定每一个方案   

  • 问题转换成:确定第一层(最下一层)的A,B分布情况即可

因为第一行确定了,第二次也随之确定(根据组塔规则),以此类推,所有的机器人的位置都是确定的。

        机器人的层数由机器人数量决定,1+2+3+...+n=\frac{n(1+n)}{2}\leq 100,n最大可取到13,所以最多13层。一个位置可以放A和B两种,所以第一层最多能放2^n=2^{13}\approx 10^4种,这个计算量不高。

A,B两个状态的表示

二进制法:
用0表示A,用1表示B
从最后一层向上递推的过程:

递推的结果符合异或运算的性质

解题思路:二进制枚举+异或运算递推

1、根据输入的A,B机器人数推算层数n:  N+M\rightarrow n
2、二进制法求底层AB的所有情况
3、对于每个底层,利用异或运算(^)不断向上递推,递推过程中根据二进制数0,1统计A,B机器人剩余未使用的个数
4、如果A,B剩余未使用的个数出现负数,或者到达最顶层时A、B机器人个数不全为0,那么这个方案无效
5、统计所有有效的方案数,即为结果

代码:

d = {}                      # 存机器人数和层数
base = 0
for i in range(1, 20):base += i               # 机器人数d[base] = i
M, N = map(int, input().split())
level = d[M + N]            # 根据机器人数算出有多少层def dfs(cur, clv, m, n):  # cur:当前情况,clv:当前层数(最底层的机器人个数),m:剩余A的人数,n:剩余B的人数if m < 0 or n < 0:    # 排除出现负数的情况return Falseif clv == 0:          # 层数为0return m == n == 0cb = bin(cur)[2:].count('1')  # 转为二进制:0bxxxx(字符串),统计1的个数count('1')ca = clv - cb        # 不直接统计0的个数,因为例如001010最前面的两个0没办法计入m -= ca; n -= cbup = (cur ^ (cur >> 1)) & ((1 << (clv - 1)) - 1)  # 计算出上一层的情况return dfs(up, clv - 1, m, n)        # 搜索上一层(层数-1)res = 0
for case in range(1 << level):    # 遍历2^n种情况if dfs(case, level, M, N):res += 1
print(res)

注:下面对代码up = (cur ^ (cur >> 1)) & ((1 << (clv - 1)) - 1) 进行解释

例如:cur为22(二进制位10110),clv为6

1、cur >> 1:将cur右移一位,右移一位为1011;

     1 << (clv - 1):1向左移动clv-1位,为01111

2、 (cur ^ (cur >> 1)):求上一层的情况,但最左边多出来一位

 

3、& ((1 << (clv - 1)) - 1):和一个二进制位为01111相与(&)就能去掉最左边的一位。注意“-”的优先级大于“>>”,所以需要加一个括号让<<先算。

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF,目录中的页码并非PDF中直接索引的页码...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...