SP9934 ALICE - Alice and Bob【题解】

Eon_Sky · 2021-07-29 08:31:17 · 题解

Update

2021.7.30 增加公式与文字之间忘加的空格以及公式错用。

博弈论

复杂度：O(TN)，应该是最优复杂度，读入 O(N)，判断 O(1)，题解首杀。
此外，也是码量最小的解法。

我们设 most 为除去石子数量为 1 的堆后的最大操作总数，cnt 为石子数量为 1 的堆数。

当拿走只有 1 个石子的堆时，先后手会发生变化，因为这相当于先合并再拿走 1，是两次操作，然而你只用一次就做到了，这是这道题的关键。

假设 cnt 为偶数，后手不需要改变先后，则此时无论先手进行啥操作，结果都取决于后手的决定（被动优势，建议和同伴试试）。

假设 most 是奇数且 most\ge3
- 则先手的目的就是保证操作最多即可（显然操作数是奇数时，先手必胜），所以先手不会拿走 1 （单独一堆）来改变先后手，先手会尽可能合并两个 1（单独一堆）来保证对手不能改变先后手，若后手拿走一张 1 (单独一堆)，先手也必须拿走一堆保证先后手不变。所以不难看出，先手要想赢的话，每轮操作都会减少两个 1 的数量（合并两个 1；后手拿一个，先手拿一个）。
  1. - 为了不让后手拿到被动优势，先手可以将 $1$ （单独一堆）合并到其他不为 $1$ 的堆里去，这时场上的 $1$ 一定是偶数，然而后手必须要改变先后，但是那样他又没有被动优势，要是为了拿到被动优势，又拿不到先后，所以先手必胜。
  2. - 这时先手合并两个 $1$ 即可得到被动优势，后手又像上面说的不能两全其美（改变先后和拿到被动优势），先手必胜。
假设 most 是偶数且 most\ge2
- 此时先手一定要改变先后（拿走单个）。
  1. - 此时先手可以直接拿走一张（改变先后），为了挽回，后手只能拿一张（否则相当于投降），拿几轮后最后一定只剩一堆单个的了，控制权此时在先手，先手必赢。
  2. - 此时先手不能两全其美，先手必输。

综上所述 cnt\bmod 2=1 或者 most\bmod 2=1 时先手必胜。

但是当 most\le2 时，结论不成立，此时的 most 可以不讨论（因为一定是偶数），就相当于只有 cnt 个 1 单取，此时我们一个个讨论。

0$ 个 $1
- 显然，先手必输。
1$ 个 $1
- 显然，先手必赢。
2$ 个 $1
- 先手合并两个 1，先手必赢。
3$ 个 $1
- 先手必输，自己推一下即可。
4$ 个 $1
- 先手拿走一个，变成情况 4，先手必赢。
5$ 个 $1
- 先手不想改变先后，合并两个，对手无论怎样一定要取走一张，此时先手拿到被动优势，先手必赢。

接下来的情况都可以转换成之前出现过的情况，就不往下推了。

综上所述

在 most>2 的前提下 cnt\bmod 2=1 或者 most\bmod 2=1 时先手必胜。
在 most\le2 的前提下 cnt\bmod 3=0 先手必输。

\text{Code:}

#include <bits/stdc++.h>

using namespace std;

int T;

int n;

int main() 
{
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        scanf("%d",&n);
        int most=0,cnt=0;
        for(int x,j=1;j<=n;j++)
        {
            scanf("%d",&x);
            if(x==1)
                cnt++;
            else 
                most+=x+1;
        }
        most--;
        if(most<=2)
        {
            if(cnt%3)
                printf("Case #%d: Alice\n",i);
            else 
                printf("Case #%d: Bob\n",i);
        }
        else
            if(cnt%2==1||most%2==1)
                printf("Case #%d: Alice\n",i);
        else 
            printf("Case #%d: Bob\n",i);
    }
    return 0;
}