P2599 取石子游戏

potatoler · 2020-08-01 09:22:41 · 题解

题目简述：

### 思路：比较容易想到的是，如果两端石子相同时，先手必败。这是因为无论先手做什么操作，后手只需要做与之对称的操作就可以了，最后拿光石子的一定是后手。那么对于先手自身来讲，使其必胜的状态就是能够使两端石子相同的状态，这样就可以先发制人，使后手面对刚才说过的局面。与之前做过的其他题目有一个显著的不同在于，这道题只允许玩家从两端取石子，在两端的石子取完之前中间的石子状态并不会发生改变。两端的石子的确可以决定玩家的状态，但生活总不是风平浪静，两端的石子被取完后，曾经的优势者也可能面临着劣势局面 —— 如何力挽狂澜是他需要考虑的事情，而对于我们来讲，不仅需要考虑能操作范围内 (即两端) 石子的状态，更要考虑现在能操作的石子与未来要操作的石子之间的关系，考虑 DP。不妨先做一些规定吧：$l_{i,j}$ 表示先手必败时中间石子形成的闭区间 $[i,j]$ 左端的石子数，$r_{i,j}$ 表示先手必败时闭区间 $[i,j]$ 右端的石子数，$a_i$ 表示 $i$ 位置的石子数。值得注意的是，前两个条件不仅限制了两端的石子数，还限制了游戏中剩余所有石子的范围 —— 换句话说，只有除去两端石子，剩下的石子正好是闭区间 $[i,j]$ 时，$l_{i,j}$ 和 $r_{i,j}$ 才会生效。首先，如果 $l_{i,j}$ 和 $r_{i,j}$ 存在，那它们一定是唯一的。假设 $l_{i,j}$ 有两个值 $l_1$ 和 $l_2$ ( $l_1>l_2$ )，那么当最左端的石子数量为 $l_1$ 时，先手本应必败，但是他可以将最左端石子拿成 $l_2$，局面变为后手必败，与前边先手必败矛盾。其次，$l_{i,j}$ 和 $r_{i,j}$ 一定都存在。假设 $l_{i,j}$ 不存在，那么无论最左端有多少石子都是必胜态。拿左边的石子显然是徒劳的，因为不管剩下多少都一定是必胜态，所以先手拿右边的石子。现在先手拿了右边的石子使得后手必败，那么后手无论从左边拿多少都必败，与「无论最左端有多少石子都是必胜态」矛盾。综上，$l_{i,j}$ 和 $r_{i,j}$ 存在且唯一。 #### Case0：边界 $[i,i]

#### Case1：$a_j=r_{i,j-1}

最右边的石子已经满足了先手必败时的条件，先手必败。

Case2：a_j<l_{i,j-1},\ a_j<r_{i,j-1}

此时有 l_{i,j}=a_j，又构成了最开始说的情况：最右端的石子是 a_j，那么最左端的石子和最右端对称的时候先手必败。

Case3：a_j≥l_{i,j-1},\ a_j<r_{i,j-1}

此时有 l_{i,j}=a_j+1。如果先手取左侧：

若剩余石子大于 l_{i,j-1}，后手只需要在右侧取相同数量的石子就可以循环回到 Case3。
若剩余石子等于 l_{i,j-1}，后手只需要取完右端所有石子，触发 a_{i-1}=l_{i,j-1} 的先手必败状态。
若剩余石子小于 l_{i,j-1}，后者只需要取右端石子直至与左端相等，则回到 Case2。由于有 a_j≥l_{i,j-1}，所以先手取完时一定有 a_j≥l_{i,j-1}≥a_{i-1}。

如果先手取右侧：

若剩余石子大于 l_{i,j-1}，后手只需要在左侧取石子直至比右端多一就可以回到 Case3。
若剩余石子等于 l_{i,j-1}，后手只需要在左侧取石子直至比右端多一就可以回到 Case3。
若剩余石子小于 l_{i,j-1}，后手只需要在左侧取石子直至与右端相等，则回到 Case2。

Case4：a_j≤l_{i,j-1},\ a_j>r_{i,j-1}

此时有 l_{i,j}=a_j-1。如果先手取左侧：

若剩余石子大于 r_{i,j-1}，后手只需要在右侧取石子直至比左端多一就可以回到 Case4。
若剩余石子等于 r_{i,j-1}，后手只需要在右侧取石子直至比左端多一就可以回到 Case4。
若剩余石子小于 r_{i,j-1}，后者只需要取右端石子直至与左端相等，则回到 Case2。

如果先手取右侧：

若剩余石子大于 r_{i,j-1}，后手只需要在左侧取相同数量的石子就可以循环回到 Case3。
若剩余石子等于 r_{i,j-1}，后手只需要取完左端所有石子，触发 a_{j}=r_{i,j-1} 的先手必败状态。
若剩余石子小于 r_{i,j-1}，后者只需要取左端石子直至与右端相等，则回到 Case2。

Case5：a_j≥l_{i,j-1},\ a_j>r_{i,j-1}

此时有 l_{i,j}=a_j。无论先手取哪一侧：

若剩余石子小于 l_{i,j-1}，r_{i,j-1}，一定可以回到 Case2。
若剩余石子大于 l_{i,j-1}，r_{i,j-1}，一定可以回到 Case5。
若剩余石子等于 l_{i,j-1}，r_{i,j-1}，后手可以通过在另一堆取石子回到 Case4 或 Case3。

上面的五个 Case 对称过来就是其他的方案，方案类似不再赘述。最后只需要判断 a_1 是否等于 l_{2,n}

Code：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#include<utility>
#define int long long
using namespace std;
const int MaxN=1003;
int lL[MaxN][MaxN], rR[MaxN][MaxN], a[MaxN];

inline int Read(){
    int num = 0, op = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') op = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        num = num * 10 + ch - '0';
        ch = getchar();
    }
    return num * op;
}

signed main(){
    int T = Read();
    while(T--){
        int n = Read();
        for(int i=1;i<=n;++i)
            a[i] = Read(), lL[i][i] = rR[i][i] = a[i];
        for(int len=1; len<n; len++){
            for(int l=1,r=l+len; r<=n; l++,r++){
                int x, L, R;
                x = a[r], L = lL[l][r-1], R = rR[l][r-1];
                if(x == R) lL[l][r] = 0;
                else if(x > R && x > L || x < R && x < L) lL[l][r] = x;
                else if(x >= L && x < R) lL[l][r] = x + 1;
                else if(x > R && x <= L) lL[l][r] = x - 1;
                x = a[l], L = lL[l+1][r], R = rR[l+1][r];
                if(x == L) rR[l][r] = 0;
                else if(x > R && x > L || x < R && x < L) rR[l][r] = x;
                else if(x > L && x <= R) rR[l][r] = x - 1;
                else if(x >= R && x < L) rR[l][r] = x + 1;
            }
        }
        if(a[1]==lL[2][n]) printf("0\n");
        else printf("1\n");
    }
    return 0;
}