加法和乘法
? 題目鏈接：https://ac.nowcoder.com/acm/contest/9983/J
? 時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld
題目描述
有一天牛牛和牛妹在做游戲，規則如下：
桌面上擺著n張紙牌，每張紙牌上寫著一個正整數，由牛牛先手輪流執行以下操作：
1.如果桌面上只剩一張紙牌，游戲結束，這張紙牌上的數字如果是奇數則牛牛勝利，反之牛妹勝利，
2.當前行動玩家選擇兩張紙牌，設上面的數字分別為X,Y，接下來玩家從加法和乘法中選擇一個并應用到這兩個數字上，得到結果為Z，接下來將選擇的兩張紙牌丟棄，并拿一張新的紙牌放到桌面上，在上面寫上Z，
假設雙方均以最優策略行動，最后誰會贏？
輸入描述:
第一行一個正整數n，代表開始的紙牌數，
第二行n個空格分隔的正整數ai代表開始紙牌上的數字，
1 ≤ n ≤ 1 0 6 ， 1 ≤ a i ≤ 1 0 9 1≤n≤10^6，1≤ai≤10^9 1≤n≤106，1≤ai≤109
輸出描述:
如果牛牛能贏，輸出NiuNiu，否則輸出NiuMei，
示例1
輸入
3
233 2333 23333
輸出
NiuMei
示例2
輸入
4
1 1 1 1
輸出
NiuNiu
這是一道博弈題，一般博弈題都要打表找規律，這題可以通過分析解決，
眾所周知，奇數 * 奇數=奇數，奇數 * 偶數=偶數，偶數* 偶數=偶數，奇數+奇數=偶數，奇數+偶數=奇數，偶數+偶數=偶數，
也就是說，如果剩下的數字中全是偶數，牛牛必輸，所以牛牛要想獲勝，就要盡量把偶數都變成奇數，
所以牛牛的最優策略是減少偶數的數量，比如 1 2 2，讓1加2，就變成 3 2 ，一奇一偶，或者讓2加2，就變成1 4.也是一奇一偶，所以當有偶數的時候，牛牛的最優策略是減少1個偶數，
牛妹則盡量減少奇數，最優策略是讓2個奇數相加，變成1個偶數，或者讓1奇與1偶相乘變成1個偶數，
比如：
當偶數的個數大于等于2時
假設
有10個奇數，2個偶數
牛牛行動后，偶數-1
有10個奇數，1個偶數
牛妹行動后，奇數-2，偶數+1
有8個奇數，2個偶數
可以看到，一回合過后偶數數量沒變，奇數減少了2個，一直這樣下去，牛牛肯定輸了，
得出結論，偶數個數>=2時，牛牛必輸，
當只有1個偶數時：
假設
有10個奇數，1個偶數
按照上面的模式之后…
有2個奇數，1個偶數
此時到牛牛行動，偶數-1
有2個奇數，0個偶數
這時，牛妹讓兩個奇數相加，變成一個偶數，所以最后牛妹贏了，
但這只是因為最后剛好只剩下兩個奇數，如果是只剩下一個奇數，那就是牛牛贏了，
因此
結論：只有一個偶數，奇數有奇數個時，牛牛贏
當沒有偶數時：
可以打表找到規律，奇數有奇數個時，牛牛輸，奇數有偶數個時，牛牛贏，但要注意，n可以取1，所以
沒有偶數時，且奇數的個數為偶數或者只有一個奇數時，牛牛贏
綜上所述：
牛牛贏：偶數有一個且奇數個數為奇，或者沒有偶數且 奇數個數為偶或只有一個奇數，
#include<iostream>
#define endl '\n'
#define int long long
#define Please return
#define AC 0
using namespace std;
void fastio(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);}
signed main()
{
fastio();
int n,jishu=0;
int oushu=0;
cin>>n;
while(n--)
{
int a;
cin>>a;
if(a&1)jishu++;
else oushu++;
}
if(((jishu&1)&&oushu==1)||((!(jishu&1))&&oushu==0)||(jishu==1&&oushu==0)) cout<<"NiuNiu"<<endl;
else cout<<"NiuMei"<<endl;
Please AC;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/257138.html
標籤：其他