题目大意：给定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
于是枚举每种操作暴力记忆化搜索即可
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1010using namespace std;char f[60][50500];//1-先手必胜 0-先手必败int n;char Memorial_Search(int a,int b){if(a==0) return b&1;//当不存在大小为1的堆时按照操作数计算必胜或必败if(b==1) return Memorial_Search(a+1,0);//若操作数为1则此时b部分只有1个石子 划到a中if(~f[a][b]) return f[a][b];char &re=f[a][b];if( a && !Memorial_Search(a-1,b) )return re=true;//取走某个大小为1的堆中的石子if( a && b && !Memorial_Search(a-1,b+1) )return re=true;//将某个大小为1的堆中的石子与某个大小不为1的堆合并if( a>=2 && !Memorial_Search(a-2,b+2+(b?1:0) ) )return re=true;//将两个大小为1的堆中石子合并if( b && !Memorial_Search(a,b-1) )return re=true;//对大小>1的堆进行合并或取走石子使操作数-1return re=false;}int main(){int T,i,x;memset(f,-1,sizeof f);for(cin>>T;T;T–){cin>>n;int a=0,b=-1;for(i=1;i<=n;i++){scanf("%d",&x);if(x==1) ++a;else b+=x+1;}if(b==-1) b=0;puts(Memorial_Search(a,b)?"YES":"NO");}return 0;}
当你感到悲哀痛苦时，最好是去学些什么东西。
