简单情况:所有堆的石子个数>1
设b=堆数+石子总数−1
先手必胜 <=>
b是奇数
对于任何一个奇数,一定存在一个偶数后继
对于任何一个偶数,所有后继必然是奇数
又当b=1时,有b=1(堆数)+1(石子总数)−1=1则最终状态一定是奇数
证明思路:
奇数出发(自己)->
能到偶数(对手)->
必回奇数(自己)->...->
剩1(自己)->
自己赢
奇数:
堆数>1 =>
合并两堆(堆数-1) b->
偶数
堆数=1,≥3 =>
取1石子(石子数-1)b->
偶数
即任何一个奇数状态都可以转移到某一个偶数状态
偶数:
堆数>1 =>
合并两堆(堆数-1) b->
奇数
取一子
1 该堆>2 b->
奇数
2 该堆=2 b->
奇数
该堆剩1
2.1 总共堆数=1 则奇对手赢
2.2 总共堆数>1 则奇对手一定在之后把这剩1的堆给合并
假设剩两堆 2数的堆+奇数个数的堆(b=2+奇-1+2=偶) 拿完后 1+奇 奇对手合并两堆
->
最后只剩1堆偶数给偶对手(b=1+偶−1)
一般情况:有堆的石子个数=1
石子个数=1的堆个数=a
b 其他个数(>1)的堆个数+其他堆石子总数−1
f(a,b)={f(a−1,b),从a中取1个f(a,b−1),从b中取1个f(a,b−1),合并b中2个f(a−2,b+3),合并a中2个(b堆石子数+2,堆数+1)f(a−1,b+1),合并a中1个b中1个(b堆石子数+1,a个数−1)
#include <cstdio>
#include <cstring>
#include<iostream>
using namespace std;
const int N = 55, M = 50050;
int f[N][M];
int dp(int a, int b)
{
int &v = f[a][b];
if (v != -1) return v;
// 简单情况
if (!a) return v = b % 2;
// 一般情况
// 上一次取完后 b中只有1堆 且只有1个石子 b=1+1-1=1 这堆并入a中
if (b == 1) return dp(a + 1, 0);
// 有a 从a中取1个
if (a && !dp(a - 1, b)) return v = 1;
// 有b 从b中取1个 or 合并b中2个
if (b && !dp(a, b - 1)) return v = 1;
// 合并a中2个
if (a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return v = 1;
// 合并a中1个b中1个
if (a && b && !dp(a - 1, b + 1)) return v = 1;
return v = 0;
}
int main()
{
memset(f, -1, sizeof f);
int T;
cin >> T;
while (T -- )
{
int n;
cin >> n;
int a = 0, b = 0;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
if (x == 1) a ++ ;
// b==0时 加1堆+加x石子=0 + 1+x-1=x
// b!=0时 加1堆+加x石子=原来的+x+1
else b += b ? x + 1 : x;
}
if (dp(a, b)) puts("YES");
else puts("NO");
}
return 0;
}
如果
b为奇数 且堆数>1
此时 为什么不能从b中任意一堆取走一个 , 这样堆数不变, 总数-1 b也是可以变为偶数啊? y总这里好像也没讲清楚.... :(奇数: 堆数>1>1 => 合并两堆(堆数-1) b->偶数
简单情况下所有堆的石子个数大于1,如果恰好有一堆石子个数是2,那么如果先手从这堆取走一个,此时
b
是偶数,然后后手再把这堆剩下一个取走,那么石子个数和堆数均减去1,b
就还是偶数,对于先手而言就是必败态了。嗯所以应该是>=3时奇数可以任一取一才是最优解或者是合并防止状态的跳跃说白了就是sg函数中你有通往0的方法也有通往1的方法但是你自然是走通往0的方法而不是通往1
对于// 有b 从b中取1个 or 合并b中2个
if (b && !dp(a, b - 1)) return v = 1;
如果b中有一堆为2,取走一个后a不应该加1吗
a中的石子可以取1操作,b中如果产生了石子数为1的堆,该堆只能合并不能再取1