题目描述

难度分:$2043$

输入$n(2 \leq n \leq 3 \times 10^5)$和长为$n$的严格递增数组$a(0 \leq a[i] \leq 10^9)$。

Alice和Bob在玩一个回合制游戏，Alice先手。
游戏规则如下：

1. 一开始，数轴上有$n$颗石子，第$i$颗石子的位置是$a[i]$。

2. 每个回合，玩家只能移动最右边的那颗石子。且必须将它移动到在它左边的没有石子的非负整数空位上。例如 $a=[2,4]$，你只能移动位置$4$上的石子到位置$0$或$1$或$3$。

3. 移动石子后，轮到另一个玩家继续移动这$n$颗石子中的最右边的石子。如此交替。

4. 无法移动的玩家输掉游戏，另一位玩家获胜。

如果Alice必胜，输出Alice，否则输出Bob。

输入样例$1$

2
2 4

输出样例$1$

Alice

输入样例$1$

3
0 1 2

输出样例$1$

Bob

算法

打表找规律

完全不会做，先写了个DP寻找必败态。

状态定义

$dp[mask]$表示在给出的数为$mask$状态时，Alice能否获胜，$mask$上第$i$位为$1$就表示数字$i$是给出的。

状态转移

先找出$mask$最右边$1$的位置$x$，然后枚举将其放在前面各个为$0$的位置$i$。带来的效果就是第$x$位变成$0$，第$i$位变成$1$，因此状态转移方程为

$dp[mask]=dp[mask-2^x+2^i]$

只要有一个$i$位置能让Alice回合的$dp[mask]$为true，那么Alice就是必胜的。

打印一下必败态发现规律：如果最大值和次大值相差$1$，并且除了它们两个数之外，剩余数的个数奇偶性与次大值是相同的，就是个必败态，Bob获胜，否则就是Alice获胜。

复杂度分析

时间复杂度

由于读入的数字本来就是有序的，因此判断一下最大值与次大值的差是否为$1$，然后判断$n-2$和次大值奇偶性是否相同就可以了，两个判断时间复杂度$O(1)$。

空间复杂度

仅适用有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 6, M = 300010;
bool dp[(1<<N) + 10];
int n;
int a[M];

void get_loss() {
    for(int mask = 0; mask < 1<<N; mask++) {
        int x = -1;
        for(int i = 0; i < N; i++) {
            if(mask>>i&1) x = i;
        }
        bool loss = false;
        for(int i = 0; i < x; i++) {
            if(!(mask>>i&1)) {
                loss |= !dp[mask - (1<<x) + (1<<i)];
                if(loss) break;
            }
        }
        dp[mask] = loss;
        if(!dp[mask]) {
            // 必败态
            vector<int> ans;
            for(int i = 0; i < N; i++) {
                if(mask>>i&1) {
                    ans.push_back(i);
                    printf("%d ", i);
                }
            }
            puts("");
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    if(a[n] - a[n - 1] == 1 && (((n - 2)&1)^(a[n - 1]&1)) == 0) puts("Bob");
    else puts("Alice");
    return 0;
}