Codeforces gym 102823J. Stone Game 题解

题目大意

Alice 和 Bob 取石子，每一回合只能从某一堆上取一个，并且任何时候相邻两堆石子个数不能相同，不能再取得人失败。Alice 先手，问二人谁必胜？

题解

我们来想最终极限不能取的状态应该是什么样子的。例如有一个部分最初为 \(2,3,5,7,8\)，我们发现取法是把这样的上升序列取成连续序列，比如刚才的部分最终的状态一定是 \(0,1,2,3,4\)​（从左边的小的石子堆取，取完之后向右继续），此时这一部分不能再被任何人取，可视为最终状态。

所以我们可以对原数组进行处理，把类似这样的上升序列转换为其最终的状态（代码中的 \(b[i]\) 即代表 \(i\) 位置最终的状态），由于下降序列同理，所以从左往右和从右往左各自来一遍，两次 \(b[i]\)​ 取最大的限制，然后得到最终状态后，计算初始到最终状态的石子数，若为奇数则先手 Alice 胜。

代码

// https://codeforces.com/problemset/gymProblem/102823/J
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
 
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
    for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
 
template <typename _Tp>
void write(_Tp a) {
    if(a < 0) putchar('-'), a = -a;
    if(a > 9) write(a / 10); putchar(a % 10 + '0');
}

const int N = 1e5 + 5;
ll n, a[N], b[N];

void init() {
    memset(b, 0, sizeof b);
}

int main() {
    // freopen("0721_2.in", "r", stdin);
    int T;
    read(T);
    for(int _T = 1; _T <= T; _T++) {
        init();
        read(n);
        ll x = 0;
        for(int i = 1; i <= n; i++) read(a[i]);
        ll tot = 0; // left up
        for(int i = 2; i <= n; i++) {
            if(a[i] > a[i - 1]) tot++;
            else tot = 0;
            b[i] = max(b[i], tot);
        }
        tot = 0; // right up
        for(int i = n - 1; i >= 1; i--) {
            if(a[i] > a[i + 1]) tot++;
            else tot = 0;
            b[i] = max(b[i], tot);
        }
        for(int i = 1; i <= n; i++) {
            x += a[i] - b[i];
        }
        printf("Case %d: %s\n", _T, x % 2 == 1 ? "Alice" : "Bob");
    }
    return 0;
}