题解-求和游戏-数学,以及简单分类证明

Problem: 1927. 求和游戏

初始思路

• 考虑一些等价:我们先把这个数分为两个部分$left,right$,分别是左右两边数字的和,形式化写为$\displaystyle right=\sum_{i=n/2}^{n}num_i(0<=num_i<=9)$剩下的问号数量分别为$n_{left},n_{right}$
• 我们要做的实际上是对$left和right$分别操作$n_{left},n_{right}$n次,其中我们允许的操作就是对该数加上0-9的任意一个数
• 显然操作是对称的,所以我们只考虑有效的操作数,也就是$abs(n_{left}-n_{right})$,而且显然有效的操作数只会存在于一个数身上:如果出现在两个身上就会对称消除
• 我们可以先除去一些情况:
  • 如果剩下的有效操作是奇数,则Alice一定赢,因为她一定不会选择让数相等的操作(只有一个选择),而Alice有10个合法选择
  • 然后我们发现操作一定会让数增加,也就是说,如果存在有效操作的是较大的那个数,则一定不可能相等
• 现在我们只剩下了一种情况:有一个较小的数能够让双方都操作$x$次,如何让较小的数变为较大的数
• 设两数相差的绝对值为$gap$,每个人能操作$x$次
• Alice有两个选择:
  • 一个是积极加,在自己的回合里都加9,这样会让较小的数飞快增长,如果两数相差比较小,就能让这个数超过大点的数,从而Bob不能选出来:也就是$9x>gap$,Alice能赢
  • 另一个是完全消极,每次都加0,这样会让数缓慢增长,单靠Bob变数增加,如果$gap>9x$,此时Alice也赢
• 我们惊讶地发现此时出现了9x大于小于gap,Bob都会输,就只剩下了$$9x==gap$$,所幸,我们能发现此时Bob会赢,因为不管此时Alice如何操作,Bob后手都能补齐9

Code

class Solution:
    def sumGame(self, num: str) -> bool:
        n=len(num)
        nums=0
        left=0
        right=0
        for i in range(n//2):
            if num[i]=='?':
                nums+=1
            else:
                left+=ord(num[i])-ord('0')
        for i in range(n//2,n):
            if num[i]=='?':
                nums-=1
            else:
                right+=ord(num[i])-ord('0')
        if nums%2!=0 or (left>right and nums>0) or (left<right and nums<0):
            #最后轮到Alice或者一定不能赢的情况
            return True
        AliceCan=abs(nums)//2
        want=abs(left-right)
        if AliceCan*9!=want:
            return True
        return False