题目大意

给出 \(n\) 堆石子，每次可以做以下两种操作之一：

将某两堆石子进行合并
将某一堆石子抽走一个石子

问谁必胜。

思路

就nm很妙好么？

首先，我们需要考虑每堆石子大小都 \(>1\) 的情况，你发现判断条件就是判断石子总数加上堆数减一是否为奇数。因为每次合并实际上就相当于翻转先后手，然后如果两人足够聪明那么他们一定会用完合并的机会，因为如果自己当前必败就让对方走，反之对方就会让自己走。

我们再考虑存在大小 \(=1\) 的情况，你发现无非就多了几种操作：

将某两个大小为 \(1\) 的堆合并
将一个大小为 \(1\) 的堆与大堆合并
删掉一个小堆
抽掉大堆中的一个石子

然后你发现这个直接暴力记搜即可。时间复杂度 \(\Theta(n^2w)\)，其中 \(w\) 是值域。

\(\texttt{Code}\)

#include <bits/stdc++.h>

using namespace std;

#define Int register int

#define MAXM 50105

#define MAXN 55

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}

template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}

template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int t,n,sg[MAXN][MAXM];

int dfs (int a,int b){

	if (!a) return b & 1;

	if (b == 1) return dfs (a + 1,0);

	if (~sg[a][b]) return sg[a][b];

	int &t = sg[a][b];

	if (a && !dfs (a - 1,b)) return t = 1;

	else if (a && b && !dfs (a - 1,b + 1)) return t = 1;

	else if (a > 1 && !dfs (a - 2,b + 2 + (b ? 1 : 0))) return t = 1;

	else if (b && !dfs (a,b - 1)) return t = 1;

	else return t = 0;

} 

signed main(){

	memset (sg,-1,sizeof (sg)),read (t);

	while (t --> 0){

		int sum1 = 0,sum2 = 0;

		read (n);for (Int i = 1,v;i <= n;++ i) read (v),sum1 += (v == 1),(v != 1) && (sum2 += v + (sum2 ? 1 : 0));

		puts (dfs (sum1,sum2) ? "YES" : "NO");

	}

	return 0;

}

巴特西

题解 UVA1500 Alice and Bob

题目大意

思路

\(\texttt{Code}\)

最新文章

热门文章