本文作者：Altwilio 希望写的题解不要再被小破网站爬了。
本题解给出所有情况下保证先手必败的具体方案。
有一排 (n) 堆石子，两人轮流从最左或最右一堆取若干石子，不能取的人输。
问对于给定的初始局面，是否有先手必胜策略。
假设当前 (i) 到 (j) 堆已经固定。 如 [?] [i j] [?]， [?] 代表未固定。
设 (left_{i,j}) 表示我在 (i) 左边放多少个棋子先手必败。
结论是 (left_{i,j}) 存在且唯一。
使用反证法：假设有两个取值 (a < b) 使得先手必败，那么当先手取 (b – a) 个时，留给后手 (a) 个，后手必败先手就不必败了。所以 (left_{i,j}) 存在且唯一。
同理可以求出 (right_{i,j}) 表示我在 (j) 右边放多少个棋子先手必败。
则当 (left_{2,n} = a_1) 时，先手没有必胜策略。这句话就是字面意思，当在 (a_2) 左边也就是 (a_1) 放 (left_{2,n}) 是先手必败。
接下来是 (\textbf{重点}), 分析 (left_{i,j}) 如何递推，不分析 (right_{i,j}) 因为对称。
假设当前状态为 [?] [i j-1] [j(x)]，第 (j) 堆的大小为 (x)。则需要求 [?] 等于什么可以使状态 [?] [i j-1] [j(x)] 必败。
再定义一个 (L) 代表使状态 [?] [i j-1] 必败的 [?] 值，(R) 代表使状态 [i j-1] [?] 必败的 [?] 值。
然后就是大幅分类讨论啦！
(R = x)。
结论 [0] [i j-1] [x]。
在状态 [?] [i j-1] [x] 中 (R = x)，则 (left_{i,j} = 0)。
(x < L, x < R)。
结论 [x] [i j-1] [x]。
在状态 [x] [i j-1] [x] 中 (x < L)， (x < R)，先手取完后，后手只要在另一堆取相同的个数即可，最后这两堆肯定会存在先手取完后有一堆为 (0) 的情况，则状态为 [0] [i j-1] [y]，(0 < y ≤ x)。而此时的必败态只有 (L)，(R)，而 (y
(L>R) 则有 (R < x ≤ L)。
结论 [x-1] [i j-1] [x]。
先手取右边：
先手把右边取到 (R)。后手把左边取完，先手面临必败状态。
先手把右边取到 (x < R)。后手把左边取到与右边相等，则转换为 情况2，先手必败。
先手把右边取到 (x > R)。后手把左边取到比右边小 (1)，则右边必然会到达 情况1 或 情况2。先手必败。
先手取左边：
先手把左边取到 (x ≥ R)。后手把右边取到 (x + 1)，则转换为 情况3.1。
先手把左边取到 (x < R)。后手把右边取到 (R)，则转换为 情况2。
则只要 左边 (≥R)， 右边 (≥R+1)， 后手保证左边比右边少一个，一旦左边或者右边有一个 (
(R > L) 则有 (L ≤ x < R)。
结论 [x+1] [i j-1] [x]。
如果先手把左边取到 (≥L+1) 时，后手就把右边取到 (≥L)，后手永远保证左边比右边多 (1)。
如果先手把左边取到 (L) 时，后手就把右边取完，先手必败。
如果先手把左边或右边取到 (
则后手保证左边比右边多一个，一旦左边或者右边有一个 (
(x > L) 且 (x > R)。
结论 [x] [i j-1] [x]。
意味着只要 (x>L) 且 (x>R)，左边和右边取一样多就行。
当 (L>R) 时。
先手取完后 (>L)，后手保证左右两边相同。
一旦先手把某一边个数取到 ((R,L]) 后手保证左边比右边少一个，转换为 情况3.1。
一旦先手把某一边个数取到 ([R,L)) 后手保证右边比左边多一个。
一旦先手把某一边个数取到 ((,R)) 后手保证右边和左边一样多。
当 (R>L) 时，对称。
先手取完后 (>R)，后手保证左右两边相同。
一旦先手把某一边个数取到 ((L,R]) 后手保证右边比左边少一个，转换为 情况3.2。
一旦先手把某一边个数取到 ([L,R)) 后手保证左边比右边多一个。
一旦先手把某一边个数取到 ((,L)) 后手保证右边和左边一样多。
const int N = 1010;
int n, a[N], l[N][N], r[N][N];
signed main(){
int T; read(T);
while(T --){
read(n);
for(int i = 1; i L && X > R) l[i][j] = X; //情况3.1 情况4.1
else if(L > R) l[i][j] = X - 1; //情况3.2 情况4.2
else l[i][j] = X + 1;
//以下对称
L = l[i + 1][j], R = r[i + 1][j], X = a[i];
if(L == X) r[i][j] = 0;
else if(X < L && X < R || X > L && X > R) r[i][j] = X;
else if(R > L) r[i][j] = X - 1;
else r[i][j] = X + 1;
}
}
}
if(n == 1) puts("1");
else print(l[2][n] != a[1]), puts("");
}
return 0;
}
Original: https://www.cnblogs.com/William-Sg/p/16521689.html
Author: Altwilio
Title: ZJOI 2009 取石子游戏题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604735/
转载文章受原作者版权保护。转载请注明原作者出处！