Leetcode每日一题 —— 1927. 求和游戏

Alice 和 Bob 这一对苦命鸳鸯又来了！

思路

如果采取最优策略的话，Alice 的目的是让两半尽量不相等，而 Bob 则是让两半尽量相等。

题目最终结果因此就取决于替换了问号后能不能使得左右各自数字和的差为 0。

分类讨论:

1. 如果问号数量总和为奇数，那么 Alice 必然能多放一次来打破平衡，是必赢的。


2. 如果问号数量总和为偶数，必然是 Alice 和 Bob 各放一半:
   
   
   
   1. 
      

      若左右两部分问号数量相等，Alice 和 Bob 各放一半，Bob 怎么样也能抵消 Alice 的改动，这种情况相当于问号不存在了，只用看左右其他数字的和的差是不是 0；

      
      
   
   
   2. 
      

      若左右两部分问号数量不相等，因为问号数量总和是偶数，左右问号数量差必然也是偶数。也就是说必然是一边比另一边多出偶数个问号，对于相同的部分我们按 2.1 处理，多出的部分依旧是 Alice 和 Bob 各能操作一半:

      
      
      
      
      1. Alice 为了破坏平衡会尽量填 9，而 Bob 则只能填 0;
      
      
      2. 如果填了 9 会导致两边平衡，Alice 会选择填 x \neq 9，但 Bob 可以填 9-x 来控制贡献总是为 9。
      
      
      
      

      因此对于这一多出的部分，我们取一半并乘上 9，如果能弥补左右其他数字和的差，那么 Bob 就赢了，否则是 Alice。

      
      
   
   
   
   

代码

class Solution {

public:

    bool sumGame(string num) {

        // 采用最优策略的话，Alice 尽量让两边不相等

        // Bob 尽量让两边相等

        // 1. 问号数量总和为偶数时，必然是 Alice 和 Bob 各放一半

        // 2. 但如果是奇数，那么 Alice 多放一次，肯定是必赢的

        // 3. 问号数量总和为偶数:  

        //     1. 左右问号数量相等，Alice 和 Bob 各放一半，Bob 怎么样也可以抵消 Alice 的修改，实际相当于没有问号的情况 (看左右其他数字差是不是 0)

        //     2. 左右问号数量不相等，因为问号数量总和是偶数，左右问号数量差肯定也是偶数（和差奇偶性一致）

        //         即有**同一边**多出偶数个问号，依旧是 Alice 和 Bob 能各操作一半:  

        //            Alice 为了破坏平衡会填 9，Bob 则只能填 0; 

        //            如果填了 9 会导致平衡，Alice 就只会填 x!=9，但是 Bob 可以填 9-x，也就是能控制 Alice 和 Bob 在这部分的贡献总是为 9

        //         这种情况下就看补了 9 之后能不能破坏平衡

        int n=num.size();

        // 左右数字和的差

        int diffRL=0;

        // 左右问号计数

        int leftCnt=0, rightCnt=0;

        for(int i=0;i<(n>>1);i++){

            if(num[i]=='?'){

                leftCnt++;

            }else{

                diffRL-=(num[i]-'0');

            }

        }

        for(int i=(n>>1);i<n;i++){

            if(num[i]=='?'){

                rightCnt++;

            }else{

                diffRL+=(num[i]-'0');

            }

        }

        // 左右问号数量和是奇数，Alice 必然赢

        if((leftCnt+rightCnt)&1){

            return true;

        }

        // 否则看问号数量差，Alice 和 Bob 各能放差的一半，而 Bob 能控制贡献为 9 的倍数

        if((rightCnt-leftCnt)/2*9==-diffRL){

            // 如果靠 9 的倍数能凑齐左右的差，Bob 赢了

            return false;

        }

        return true;

    }

};