2021牛客寒假算法基础集训营3

2021牛客寒假算法基础集训营3补题记录

J 加法和乘法

链接：https://ac.nowcoder.com/acm/contest/9983/J
来源：牛客网

题目描述

有一天牛牛和牛妹在做游戏，规则如下：
桌面上摆着n张纸牌，每张纸牌上写着一个正整数，由牛牛先手轮流执行以下操作：
1.如果桌面上只剩一张纸牌，游戏结束，这张纸牌上的数字如果是奇数则牛牛胜利，反之牛妹胜利。
2.当前行动玩家选择两张纸牌，设上面的数字分别为X,Y，接下来玩家从加法和乘法中选择一个并应用到这两个数字上，得到结果为Z，接下来将选择的两张纸牌丢弃，并拿一张新的纸牌放到桌面上，在上面写上Z。
假设双方均以最优策略行动，最后谁会赢？

输入描述:

第一行一个正整数n，代表开始的纸牌数。
第二行n个空格分隔的正整数ai代表开始纸牌上的数字。
1≤n≤10^6
1≤ai≤10^9

输出描述:

如果牛牛能赢，输出NiuNiu，否则输出NiuMei。

示例1:

输入

3
233 2333 23333

输出

NiuMei

示例2:

输入

4
1 1 1 1

输出

NiuNiu

思路

这道题只要在纸上进行演算一下即可，我们将两张牌的情况都列出来，可以发现，如果两张牌都是偶数的话，无论是加法还是乘法得到的都是偶数。剩下的两种情况下，加法和乘法可以一个得到偶数一个得到奇数。由此我们可以推出如果最后一次是牛妹进行操作的话，那么牛妹必胜，如果是牛牛的话，只要在最后一次不遇上两个偶数的情况就行。那么牛牛每一次的操作就是为了消除偶数，牛妹的操作就是为了造偶数。这就是两人的最优策略。

那么，游戏的过程就变成了牛牛消一个偶数，牛妹产生一个偶数，直到最后一次判断是否有两个偶数即可。

代码：

#include<bits/stdc++.h> 
using namespace std;
long long n, a, cnt;
int main() {
	cin >> n;
	for (int i=1;i<=n;++i) {
		cin >> a;
		if (a % 2 == 0) cnt ++;
	}
	if (n == 1)	cout << (cnt == 0 ? "NiuNiu" : "NiuMei"); 
	else {
		if (cnt > 1 || n % 2 == 1)
			cout << "NiuMei";
		else cout << "NiuNiu";
	}
	return 0;
}