题目描述
有一天牛牛和牛妹在做游戏,规则如下:
桌面上摆着\mathit nn张纸牌,每张纸牌上写着一个正整数,由牛牛先手轮流执行以下操作:
1.如果桌面上只剩一张纸牌,游戏结束,这张纸牌上的数字如果是奇数则牛牛胜利,反之牛妹胜利。
2.当前行动玩家选择两张纸牌,设上面的数字分别为X,Y,接下来玩家从加法和乘法中选择一个并应用到这两个数字上,得到结果为Z,接下来将选择的两张纸牌丢弃,并拿一张新的纸牌放到桌面上,在上面写上Z。
假设双方均以最优策略行动,最后谁会赢?
输入样例1
3
233 2333 23333
输出样例1
NiuMei
输入样例2
4
1 1 1 1
输出样例2
NiuNiu
分析
- 当桌面上只有一张牌时,如果是奇数,就NiuNiu赢;是偶数则NiuMei赢。
- 当牌数n是奇数的时候一定是牛妹进行最后一次操作,不管最后的牌是奇奇,奇偶,偶偶,牛妹都可以合成偶数,一定赢
- 当牌数n是偶数的时候一定是牛牛进行最后一次操作,因为偶数不能改变奇偶性,所以牛妹如果不想让它赢就提前把全部可能的奇数合成偶数就行了。在牛牛动手游戏结束前,牛妹可以动n/2-1次,加入每次操作两个奇数,一共可以操作k=(n/2-1)*2个奇数,如果k>奇数牌总数,就NiuMei赢,否则NiuNiu赢。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL x;
int n,co;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x;
if(x%2) co++;
}
if(n==1) //只有一张牌时要特判
{
if(co) puts("NiuNiu");
else puts("NiuMei");
}
else if(n%2) puts("NiuMei");
else{
if((n/2-1)*2<co) puts("NiuNiu"); //判断牛妹是否可以把所有奇数牌操作完
else puts("NiuMei");
}
return 0;
}