南京理工大学第8回プログラム設計大会(校外鏡像)-誰が最強戦艦ですか!(ゲーム理論)

誰が最強戦艦だ!
Time Limit: 1000MS
Memory Limit: 65536KB
Description
イアワが鎮守府に来た最初のことは、大和ソロを探すことです!しかし、これは良いニュースではありません.不定と言って、鎮守府、甚だしきに至っては佐伯湾はこのように消えてしまいました.のそこで、提督君は簡単なゲームを考えて、彼女たちの勝負を分けた.ゲームのルールは以下の通りです.ここにはN個の石があり、それぞれの石がa[i](1<=i<=N)個あり、一人一人が順番にその中のある石の中から任意の石(その中の石の山でしか持てないので、取らないわけにはいかない)、大和先手、誰が最後の石を出したのか、誰が負けたのか.ヤマト必勝なら「Yamato_Saikou!」と出力し、アイワ必勝なら「Meidikeji_Shijiediyi!」と出力し、両方とも必勝できない場合は「サヨナラ_Konosekai!」と出力します.
Input
1行目に正の整数T(1<=T<=1000)を入力し、T組のテストデータがあることを示す.各試験データのセットについて、最初の行の正の整数、N(N<=1000)は、N堆石があることを示している.2行目のN個の整数a[i](1<=a[i]<=1000)は、石積み当たりの数を表す.
Output
ヤマト必勝なら「Yamato_Saikou!」と出力し、アイワ必勝なら「Meidikeji_Shijiediyi!」と出力し、両方とも必勝できない場合は「サヨナラ_Konosekai!」と出力します.
Sample Input
3 1 5 2 1 2 3 1 1 1
Sample Output
Yamato_Saikou! Yamato_Saikou! Meidikeji_Shijiediyi!
標準問題:
奇異な情勢、すべての山のxorと==0.
Sが非特異情勢であると仮定し,Tは特異情勢である.山の中の石の数>=2は、余裕の山を表し、=1は孤独な山を表す.
S 0すなわち非特異情勢下、余裕スタック0の状態S 1すなわち非特異情勢下、余裕スタック1の状態S 2すなわち非特異情勢下、余裕スタック>=2の状態
T 0は奇異な情勢の下で、余裕の山が0の状態T 2は奇異な情勢の下で、余裕の山>=2の状態
1.奇異な情勢の定義から分かるように、SはTに移行することができ、Sに移行することができ、TはSに移行することしかできない.
2.S 0必敗、T 0必勝
S 1はS 0に移行するだけでよいので、3.S 1は必ず勝つ.
4.S 2は必勝、T 2は必敗.1)T 2はS 1とS 2にしか移行できない)T 2がS 1に移行するとT 2は敗れ,T 2がS 2に移行するとS 2はT 2に戻るだけでよい.だからS 2勝、T 2敗.
したがって、必勝状態:T 0,S 1,S 2必敗状態:S 0,T 2
コード:

#include 
#include 
#include 
#include 
using namespace std;

int main(){
    int cases;
    scanf("%d",&cases);
    for (int cas=1;cas<=cases;cas++){
        int n; scanf("%d",&n);
        int sum=0,ones=0;
        for (int i=1;i<=n;i++){
            int x; scanf("%d",&x);
            sum^=x;
            if (x==1) ones++;
        }
        if (sum==0){
            if (n-ones==0) puts("Yamato_Saikou!");
            else puts("Meidikeji_Shijiediyi!");
        }
        else {
            if (n-ones==0){
                if (ones&1) puts("Meidikeji_Shijiediyi!");
                //      ，     
            }
            else puts("Yamato_Saikou!");
        }
    }
    return 0;
}