转自PoPoQQQ大佬博客
题目大意：给定n堆石子，两人轮流操作，每个人可以合并两堆石子或拿走一个石子，不能操作者输，问是否先手必胜
直接想很难搞，我们不妨来考虑一个特殊情况
假设每堆石子的数量都>1
那么我们定义操作数b为当前石子总数+当前堆数-1
若b为奇数，则先手必胜，否则后手必胜
证明：
若当前只有一堆，则正确性显然
否则：
若b为奇数，那么先手只需进行一次合成操作，此时操作数会-1，且仍不存在大小为1的堆
因此只需要证明b为偶数时先手必败即可
若先手选择了合成操作，那么操作数-1且不存在大小为1的堆，状态回到了b为奇数的状态
若先手取走了某个大小>=3的堆中的一个石子，那么操作数-1且不存在大小为1的堆，状态回到了b为奇数的状态
若先手取走了某个大小为2的堆中的一个石子，那么后手只需要将另一个石子与其它堆合成，b的奇偶性不变且仍不存在大小为1的堆
故b为偶数时先手必败
现在回到一般情况 可能存在大小为1的堆
我们设有a个大小为1的堆，其余堆的操作数为b
那么当前的状态就可以用一个二元组(a,b)来表示
容易发现a<=50,b<=50049
于是枚举每种操作暴力记忆化搜索即可
CODE(BZOJ)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 55;
const int MAXM = 50050;
int T, n, x;
char SG[MAXN][MAXM];
char ser(int a, int b) {
if(a == 0) return b&1;
//当不存在大小为1的堆时按照操作数计算必胜或必败
if(b == 1) return ser(a+1, 0);
//若操作数为1则此时b部分只有1个石子 划到a中
if(~SG[a][b]) return SG[a][b];
char &res = SG[a][b];
if(a && !ser(a-1, b)) return res = true;
//取走某个大小为1的堆中的石子
if(a && b && !ser(a-1, b+1)) return res = true;
//将某个大小为1的堆中的石子与某个大小不为1的堆合并
if(a > 1 && !ser(a-2, b+2+(b?1:0))) return res = true;
//将两个大小为1的堆中石子合并
if(b && !ser(a, b-1)) return res = true;
//对大小>1的堆进行合并或取走石子使操作数-1
return res = false;
}
int main () {
memset(SG, -1, sizeof SG);
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
int A = 0, B = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &x);
if(x == 1) ++A;
else B += x+(B?1:0);
}
puts(ser(A, B) ? "YES" : "NO");
}
}
CODE(Luogu)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 55;
const int MAXM = 50050;
int T, n, x;
char SG[MAXN][MAXM];
char ser(int a, int b) {
if(a == 0) return b&1;
//当不存在大小为1的堆时按照操作数计算必胜或必败
if(b == 1) return ser(a+1, 0);
//若操作数为1则此时b部分只有1个石子 划到a中
if(~SG[a][b]) return SG[a][b];
char &res = SG[a][b];
if(a && !ser(a-1, b)) return res = true;
//取走某个大小为1的堆中的石子
if(a && b && !ser(a-1, b+1)) return res = true;
//将某个大小为1的堆中的石子与某个大小不为1的堆合并
if(a > 1 && !ser(a-2, b+2+(b?1:0))) return res = true;
//将两个大小为1的堆中石子合并
if(b && !ser(a, b-1)) return res = true;
//对大小>1的堆进行合并或取走石子使操作数-1
return res = false;
}
int main () {
memset(SG, -1, sizeof SG);
scanf("%d", &T); int kase = 0;
while(T--) {
scanf("%d", &n);
int A = 0, B = 0;
for(int i = 1; i <= n; ++i) {
scanf("%d", &x);
if(x == 1) ++A;
else B += x+(B?1:0);
}
printf("Case #%d: ", ++kase);
puts(ser(A, B) ? "Alice" : "Bob");
}
}
之所以用char存是因为只可能有-1/0/1三个值
还有对于b的其中某一堆石子可能从2取成1的情况的解释,见PoPoQQQ大佬博客评论区