【CodeVS 3153】取石子游戏

时间:2022-04-07 21:41:49

http://codevs.cn/problem/3153/

对于这道题,直觉告诉我每一个状态一定是必胜或必败的【CodeVS 3153】取石子游戏

然后设定操作次数t,t为取完些石子最多需要多少步。

如果\(a_i\)不为1,\(t=\sum a_i+n-1\)。因为每次只让操作数减一。

但因为有\(a_i\)为1的情况,可以直接让操作数减二,所以我们把石子数为1的堆数和剩下的石子堆的操作数作为状态进行记忆化搜索。

正如xiaoyimi所说,细节确实很多QaQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 53;
const int M = 50003;
int in() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - 48;
return k * fh;
} int n, a, cnt, sum;
bool vis[M][N], f[M][N]; bool pd(int tot, int num) {
if (vis[tot][num]) return f[tot][num];
vis[tot][num] = true;
if (tot == 1) return f[tot][num] = pd(0, num + 1);
if (num >= 1 && !pd(tot, num - 1)) return f[tot][num] = true;
if (num >= 2 && !pd(tot + 2 + (tot > 0), num - 2)) return f[tot][num] = true;
if (tot >= 2 && !pd(tot - 1, num)) return f[tot][num] = true;
if (num >= 1 && tot != 0 && !pd(tot + 1, num - 1)) return f[tot][num] = true;
return false;
} int main() {
int T; T = in();
while (T--) {
n = in(); sum = cnt = 0;
for(int i = 1; i <= n; ++i) {
a = in();
if (a == 1) ++cnt;
else sum += a + 1;
}
if (sum) --sum;
puts(pd(sum, cnt) ? "YES" : "NO");
}
return 0;
}