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

, , 评论

Problem: 1927. 求和游戏

初始思路

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

Noirking's Pawn

个人简介。