度小满2018.9.26笔试小游戏

柔情只为你懂 2022-05-09 06:42 204阅读 0赞

# 题目描述 #

![在这里插入图片描述][70]  
这是[球盒问题][Link 1]中的，n个球有区别，m个盒子有区别，且盒子可以为空（但球都放进盒子里）的这种情况，这种情况的方案数为 m n m^n mn，而在本题中，方案数则为 a b a^b ab。

根据题意表述以及输入输出，可以发现输出其实输出是输的那一方（出题人把输出弄错了）。为了方便理解，这里让输出为赢的一方。所以：  
**样例输入：**  
3  
2 2 10  
3 1 4  
1 4 10  
**样例输出：**  
A  
B  
A&B

# 思路 #

在每个回合，A和B两个人都只能增加a，或者增加b，所以每种状态只有两个分支（增加底数或增加指数）。可以想象，如果考虑所有分支，那么就能画出一个二叉树。  
本文认为，如果只考虑当前状态的两个分支，然后再判断下一步走哪个分支，只能算是贪心算法。而题目说了双方都是采取的**最优策略**，则应该考虑双方都知道所有分支的结果，即知道所有分支的**二叉树**。

那么怎么画这颗二叉树呢，**考虑增加底数为左孩子，增加指数为右孩子。如果左右孩子都小于n，那么画出左右孩子；如果只有左孩子小于n，那么只画左孩子；右孩子同理；如果左右孩子都大于等于n，那么该节点为叶子节点。**  
![在这里插入图片描述][70 1]  
以输入为2 2 10为例，所有的叶子节点的深度%2==1。且这种情况，A赢。  
![在这里插入图片描述][70 2]  
以输入为3 1 4为例，所有的叶子节点的深度%2==0。且这种情况，B赢。  
总结：

*  所有的叶子节点再往下走都会大于等于n，所以它们是一个叶子节点。
 *  如果，所有的叶子节点的深度%2==1，那么肯定是A赢。
 *  如果某个叶子节点的深度%2==1，那么从根节点到该叶子节点的这种流程，是A赢。
 *  如果，所有的叶子节点的深度%2==0，那么肯定是B赢。
 *  如果某个叶子节点的深度%2==0，那么从根节点到该叶子节点的这种流程，是B赢。

但如果二叉树中，两种叶子节点都有，这种情况要复杂点：  
我们为叶子节点赋值，如果深度%2==1，那么赋值1。如果深度%2==0，那么赋值0。即节点为1代表A赢，节点为0代表B赢。叶子节点的值，能够自底向上地传递，传递规则如下：  
被传递肯定只有非叶子节点。分析只有**一个孩子的非叶子节点**，那么孩子的值就是该节点的值。  
分析有**两个孩子的非叶子节点**，这里分两种情况。

1.**非叶子节点的深度%2==0，那么该节点的分支是由A决定的，那么该节点的两个孩子只要有一个1，那么该节点就为1。即left or right。因为这个节点的分支是A决定的，所以只要有一个分支为1那么A自然肯定就会选择为1的这条分支。**

2.**非叶子节点的深度%2==1，那么该节点的分支是由B决定的，那么该节点的两个孩子只要有一个0，那么该节点就为0。即left and right。因为这个节点的分支是B决定的，所以只要有一个分支为0那么B自然肯定就会选择为0的这条分支。**  
![在这里插入图片描述][70 3]  
如上图所示，假设画出来的二叉树是这样。那么初始时，有三个叶子节点。  
b)中，由于是只有一个孩子的非叶子节点，所以直接传递值。  
c)中，由于该节点是由B决定分支，所以取1 and 0即0。  
d)中，由于该节点是由A决定分支，所以取1 or 0即1。  
所以，最终是A赢。

还有一种特殊情况是a=1  
因为底数为1，那么二叉树的右孩子能一直产生（1的任何次幂都为1，如果此时n还大于1），但左孩子到达某个深度后就会没有左孩子了（因为此时b很大，a一旦从1变成2，就会不小于n）。  
这种情况下多了平局的情况，而且注意此时双方会在输和平局两种分支中，选择平局。  
![在这里插入图片描述][70 4]  
以起始为1,4为例，现假设画出来的二叉树为这样，红色字节点之后可能还会有分支，但是在本图中不画出来，而是看作这些红色字节点已经被传递到了值。  
**思路是从上到下分析红色字节点。**  
1.首先是2,4，因为其父节点是A作决定，所以如果2,4被传递到的值为1，那么A赢，但如果值为0，那么走右分支，结果待定，还得看下一个红色字节点。  
2.然后如果到了2,5，因为其父节点是B作决定，所以如果2,5被传递到的值为0，那么B赢，但如果值为1，那么走右分支，结果待定，还得看下一个红色字节点。  
3.之后就是这样，交替分析下一个红色字节点。  
4.最后如果走到了只有右分支的节点，那么此时平局。

# 代码 #

T = eval(input())
    
    def solve(a,b,n,step):#step代表深度
        #此函数处理a>1的情况
        left = (a+1) ** b
        right = a ** (b+1)
        if (left >= n) & (right >= n):#递归终点，也是二叉树中的叶子节点
            if step%2 == 1:
                return 1
            elif step%2 == 0:
                return 0   
    
        #递归过程
        if left >= n:#只有右孩子可以走
            return solve(a,b+1,n,step+1)
        elif right >= n:#只有左孩子可以走
            return solve(a+1,b,n,step+1)
        else:#左右孩子都可以走
            leftResult = solve(a+1,b,n,step+1)
            rightResult = solve(a,b+1,n,step+1)
            if step%2 == 1:#B决定
                return leftResult and rightResult
            elif step%2 == 0:#A决定
                return leftResult or rightResult
    def solve_one(b,n):
        #此函数处理a=1的情况
        step = 1
        left = 2 ** b
        if left >= n:
            return None
        else:
            while(True):
                if 2 ** b >= n:
                    break
                result = solve(2,b,n,step)
                if (step%2 == 1) and (result == 1):
                    return 1
                if (step%2 == 0) and (result == 0):
                    return 0            
                b += 1
                step += 1 
        return None
    
    for i in range(T):
        a,b,n = map(int,input().split())
        result = 0
        if a != 1:
            result = solve(a,b,n,0)
        else:
            result = solve_one(b,n)
        if result is 1:
            print('A')
        elif result is 0:
            print('B')
        else:
            print('A&B')

函数返回1，A赢。返回0，B赢。返回None，平局。  
**输入：**  
4  
2 2 10  
3 1 4  
1 4 10  
1 4 17  
![在这里插入图片描述][70 5]

# 使用短路与、短路或 #

![在这里插入图片描述][70 6]  
这种情况中，其实根本不用传递所有值，因为根节点的分支是由A决定的，既然有一个孩子为1，那么另一个孩子的值也就无所谓了。所以代码可以这样优化。Python中短路用的是and or。

def solve(a,b,n,step):
        #此函数处理a=1的情况
        left = (a+1) ** b
        right = a ** (b+1)
        if (left >= n) & (right >= n):#递归终点，也是二叉树中的叶子节点
            if step%2 == 1:
                return 1
            elif step%2 == 0:
                return 0   
    
        #递归过程
        if left >= n:#只有右孩子可以走
            return solve(a,b+1,n,step+1)
        elif right >= n:#只有左孩子可以走
            return solve(a+1,b,n,step+1)
        else:#左右孩子都可以走
            if step%2 == 1:#B决定
                return solve(a+1,b,n,step+1) and solve(a,b+1,n,step+1)
            elif step%2 == 0:#A决定
                return solve(a,b+1,n,step+1) or solve(a+1,b,n,step+1)

A决定的节点能短路1，B决定的节点能短路0。所以：  
在A决定的节点中，要把左右孩子中，更可能为1的孩子放在前面。  
在B决定的节点中，要把左右孩子中，更可能为0的孩子放在前面。  
虽然说了如上两个结论，但左右孩子的值到底更可能为0还是1，这是一件不确定的事情（根据a,b,n的取值来决定，而且分析起来挺复杂）。如上代码，我是这样放的：A决定的就先放右孩子，B决定的就先放左孩子。

# 重复计算优化 #

![在这里插入图片描述][70 7]  
如上图所示，从第三层开始，每层的中间节点肯定都是重复的（除了每层的两端）。即使根节点是4,2或者别的什么，也是一样，读者可以自己画图尝试。所以需要设置一个全局变量，存储已经计算过的节点值，再遇到相同的(a,b)就直接使用该值，不用考虑节点在哪层，因为相同(a,b)的节点必定出现在同一层中。

T = eval(input())
    d = dict()#存储每个节点
    
    def solve(a,b,n,step):
        #此函数处理a=1的情况
        left = (a+1) ** b
        right = a ** (b+1)
        if (left >= n) & (right >= n):#递归终点，也是二叉树中的叶子节点
            if step%2 == 1:
                return 1
            elif step%2 == 0:
                return 0   
    
        #递归过程
        if left >= n:#只有右孩子可以走
            result = solve(a,b+1,n,step+1) if (a,b+1) not in d else d[(a,b+1)]#如果d已经存了就直接使用
            d[(a,b+1)] = result#为d赋值
            return result
        elif right >= n:#只有左孩子可以走
            result = solve(a+1,b,n,step+1) if (a+1,b) not in d else d[(a+1,b)]
            d[(a+1,b)] = result
            return result
        else:#左右孩子都可以走
            if step%2 == 1:#B决定
                leftResult = solve(a+1,b,n,step+1) if (a+1,b) not in d else d[(a+1,b)]#先看左孩子
                d[(a+1,b)] = leftResult
                if leftResult == 0:#手动短路
                    return 0
                rightResult = solve(a,b+1,n,step+1) if (a,b+1) not in d else d[(a,b+1)]
                d[(a,b+1)] = rightResult
                return leftResult and rightResult
            elif step%2 == 0:#A决定
                rightResult = solve(a,b+1,n,step+1) if (a,b+1) not in d else d[(a,b+1)]#先看右孩子
                d[(a,b+1)] = rightResult
                if rightResult == 1:#手动短路
                    return 1
                leftResult = solve(a+1,b,n,step+1) if (a+1,b) not in d else d[(a+1,b)]
                d[(a+1,b)] = leftResult
                return leftResult or rightResult
    
    def solve_one(b,n):
        #此函数处理a>1的情况
        step = 1
        left = 2 ** b
        if left >= n:
            return None
        else:
            while(True):
                if 2 ** b >= n:
                    break
                result = solve(2,b,n,step)
                if (step%2 == 1) and (result == 1):
                    return 1
                if (step%2 == 0) and (result == 0):
                    return 0            
                b += 1
                step += 1 
        return None
    
    for i in range(T):
        a,b,n = map(int,input().split())
        result = 0
        if a != 1:
            result = solve(a,b,n,0)
        else:
            result = solve_one(b,n)
        if result is 1:
            print('A')
        elif result is 0:
            print('B')
        else:
            print('A&B')

其实可能还能优化一下，就是不直接`d[(a,b+1)] = result`，而是先判断该键值在不在`d`里。如下：

if left >= n:#只有右孩子可以走
            rightFlag = (a,b+1) not in d
            result = solve(a,b+1,n,step+1) if rightFlag else d[(a,b+1)]
            if rightFlag: 
                d[(a,b+1)] = result
            return result

[70]: /images/20220509/b032c9c80bf44be194ac727684a3725d.png
[Link 1]: https://baike.baidu.com/item/%E6%94%BE%E7%90%83%E9%97%AE%E9%A2%98/12740706
[70 1]: /images/20220509/506611de686941cd85931e214e4a24af.png
[70 2]: /images/20220509/9e832664a0bd44a9ba3eb06357fec09a.png
[70 3]: /images/20220509/764d6198b7074e30b4e231dce0336404.png
[70 4]: /images/20220509/81652623501c40e68336a5d9a51d6f17.png
[70 5]: /images/20220509/4a5e84595aa14f10903a8adfa42fe6c2.png
[70 6]: /images/20220509/833afd65bf554c26b606d9f982724615.png
[70 7]: /images/20220509/15c73e8b4c4249709d1bbd8a1d2ebd39.png