取石子

发表于
本文字数： 3.4k | 阅读时长 ≈ 3 分钟

取石子

$Description$

$Solution$

蛮神仙的一道题。

其实就是 $anti-Nim$ 。

我们约定只有一颗石子的堆叫孤单堆，有多颗石子的堆叫充裕堆。

设 $f_{i, j}$ 表示有 $i$ 个孤单堆，能操作次数为 $j$ 时是 $P-position$ 还是 $N-position$ 。

转移分类讨论，有如下情况：

$1.$ 取孤单堆内石子

因为孤单堆只有一个元素，所以取了之后就是 $f_{i - 1, j}$ 这个状态。

$2.$ 把孤单堆内的石子并到充裕堆当中

显然，转移到 $f_{i -1, j + 1}$ ，注意判断此时有无充裕堆，没有的话不能转移。

$3.$ 把孤单堆两个并起来。

此处我们也要考虑两种情况，如果没有充裕堆了，就从 $f_{i - 2, j + 2}$ 转移，

否则从 $f_{i - 2, j + 3}$ 转移过来。因为根据状态的定义，我们合并了两个孤单堆，如果本来有充裕堆，那么我们就多了一次两个充裕堆合并的机会，否则就没有。

$4.$ 把充裕堆石子取出一个

首先我们判断取出后是否变为孤单堆，是的话可以从 $f_{i + 1, j - 2}$ 转移到。

其次，显然还可以从 $f_{i, j - 1}$ 转移到。

一些关于博弈 $dp$ 的看法：

分类讨论时，注意一个一个情况来，有条理些，如本题，就是先孤单堆几种情况，再充裕堆的能转移的情况。

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
//#include <tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define lll bignum
#define ls(x) ( x << 1 )
#define rs(x) ( x << 1 | 1 )
#define lowbit(x) ( x & -x )
#define debug(x) (cout << "#x = " << (x) << endl)
#define Set(x, i) memset (x, i, sizeof(x))
#define re register
#define For(i, j, k) for(re int i = (j); i <= (k); ++i)
#define foR(i, j, k) for(re int i = (j); i >= (k); --i)
#define Cross(i, j, k) for(re int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 71, M = 50011;
const ll inf = 5e16;

ll T, n, a[N], f[N][M];

namespace IO {

    inline char gc() {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return (p1 == p2) && (p2 = (p1 = buf) +
            fread (buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
    }

    #define dd ch = getchar()
    inline ll read() {
        ll x = 0; bool f = 0; char dd;
        for (; !isdigit (ch); dd) f ^= (ch == '-');
        for (; isdigit (ch); dd)  x = x * 10 + (ch ^ 48);
        return f? -x: x;
    }
    #undef dd

    inline void write( ll x ) {
        if ( x < 0 ) putchar ('-'), x = -x;
        if ( x > 9 ) write ( x / 10 ); putchar ( x % 10 | 48 );
    }

    inline void wrn ( ll x ) { write (x); putchar (' '); }

    inline void wln ( ll x ) { write (x); putchar ('\n'); }

    inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using namespace IO;

/*
    设 f[i][j] 表示孤单堆有 i 个，充裕堆共有 j 个石子时有无必胜策略。 
*/

inline bool dfs (ll Num, ll Sum) {
    if (Num <= 0 && Sum <= 0) return 0; //
    if (f[Num][Sum] != -1) return f[Num][Sum]; //
    if (Num <= 0) return f[Num][Sum] = (Sum & 1); //
    if (Sum == 1) return f[Num][Sum] = dfs (Num + 1, 0);
    f[Num][Sum] = 0;
    if (!dfs (Num - 1, Sum)) return f[Num][Sum] = 1;
    if (Sum && !dfs (Num, Sum - 1)) return f[Num][Sum] = 1; //
    if (Sum && !dfs (Num - 1, Sum + 1)) return f[Num][Sum] = 1; //
    if (Num >= 2 && 
        !dfs (Num - 2, Sum + 2 + (Sum? 1: 0))) return f[Num][Sum] = 1; // 一半 
    return f[Num][Sum];
}

int main()
{
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    Set (f, -1); 
    T = read(); while (T--) {
        n = read(); 
        ll res = 0, cnt = 0;
        For (i, 1, n) {
            a[i] = read();
            if (a[i] == 1) ++cnt;
            if (a[i] > 1) res += a[i] + 1;
        }
        res = res? res - 1: res;
//        debug (res);
        puts ( dfs (cnt, res)? "YES": "NO" );
    } return 0;
}

/*
99
7
1 3 3 3 3 2 2 

1
5
1 2 1 2 2 
*/

题目链接