ARC137C Distinct Numbers

题意

简化题意

给定一个序列。A,B 轮流操作，每次选序列中最大的元素，并将其变成一个更小的元素，且变换后序列元素两两不同。分析局面情况。

$n\leq 3\times 10^5,a_i<a_{i+1}$。

题解

考虑到如果存在一个局面满足 $a_n\geq a_{n-1}+2$。则这个决策可以到达它能到的一个局面能到的所有的局面，这个局面就是必胜的，这就是决策包容性。

例如 $a_1,\cdots,a_{n-1},a_{n-1}+x(x\geq 2)$ 这样的局面能到达 $a_1,\cdots,a_{n-1},a_{n-1}+1$ 这个局面。如果这个局面是必败的，当前先手直接行动到这个局面就可以了；如果这个局面是必胜的，说明这个局面后续一定有一个必败的局面，则先手移动到它后续的那个必败局面即可。

对于 $a_n-a_{n-1} = 1$ 的情况，显然双方为了不输都会保持这个性质。因此胜负由 $a_n-n$ 决定。

代码

#include<bits/stdc++.h>
#define int long long
#ifdef DEBUG
#   define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#   define debug
#endif
using namespace std;
bool Begin;
const int max_n=300005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(!isdigit(c)) w|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,a[max_n];

bool End;
#define File ""
signed main(){
    #ifndef ONLINE_JUDGE
    freopen(File ".in","r",stdin);
    freopen(File ".out","w",stdout);
    #endif
    debug("Memory : %lf\n",(&Begin-&End)/1024.0/1024);
    n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    if(a[n]-a[n-1]>1) return puts("Alice"),0;
    puts((a[n]-n)&1?"Bob":"Alice");
    return 0;
}