母牛的俄羅斯輪盤賭

鏈接：https://ac.nowcoder.com/acm/contest/9692/C
來源：牛客網

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld

題目描述

喜歡追求刺激的母牛打算和豬豬來一場緊張刺激的俄羅斯輪盤賭（當然只是用橡膠子彈），敗者需要請勝者吃宵夜，他們覺得一槍一槍輪流射擊還不夠刺激，決定遵循以下規則來輪流向自己扣動扳機，

? **·**可以扣動扳機不多于k+1次，最少1次，k為上一次操作者扣動扳機的次數.

? ·先手第一次操作能且只能扣動一次扳機

現在子彈已經裝在了玩具槍里，并且他們都知道這顆子彈會在第n次扣動扳機時射出，母牛和豬豬都不想輸掉這場對決，并且他們都聰明絕頂，會采用最好的策略進行對決，

由母牛發起的對決，自然是母牛先手，

如果母牛能贏下這頓宵夜則輸出"Cow",否則"Pig"，

輸入描述:

第一行讀入一個T，表示T組資料(1<=T<=100).每組資料讀入一個n(1<=n<=1000000).

輸出描述:

每組資料輸出一個答案，如果母牛能贏下這頓宵夜則輸出"Cow",否則"Pig"，

示例1

輸入

2
1
2

輸出

Pig
Cow

說明

對于樣例1，母牛第一槍把自己打“死”了，豬豬獲勝，
對于樣例2，母牛開完第一槍后輪到豬豬開槍槍決自己，所以母牛獲勝

問題分析：

這道題目和騙紅包神似，當時看到的第一眼真的很親切，覺得自己應該沒問題，但其實當時自己還卡在列舉求和那道題目上面難以脫身，導致在寫這道題目的時候心不在焉的，最后自然是兩道題都寫不出來，

當時比賽最后我推出來的是只要誰能夠制造剩下一個子彈留給對方的情況，它就贏了，因為此時只剩下最后一顆子彈，并且到了對方的輪回且對方至少要開一槍，

但難點就在于如何判斷局勢，因為每次的選擇都會影響下一次可操作的次數范圍，

再而言之，每一個n都與它前面的n有關聯，，鑒于之前騙紅包的經驗，我就先開始打表看看情況，

1	2	3	4	5	6	7
P	C	P	P	C	P	C

是的，當時比賽我只打表到7…

考完后再回過頭來看，打表到10看看

1	2	3	4	5	6	7	8	9	10
P	C	P	P	C	P	C	P	P	C

發現了什么！！！對，周期為5重復

哎，真的特別后悔當時比賽時沒有堅定內心去認真打表，

看下官方題解
在這里插入圖片描述

嗯，還真是一道證明題+找規律題

關于如何證明其實我是不會的，在比賽如果你有很強的數學功底我估計可以嚴謹的證明出來，但像我這種ruoji，還是找規律適合我hhhh

關于證明的詳細程序可以看下這個博主：https://blog.nowcoder.net/n/11522f0fc080451ea2247ca9d8537e7e

AC代碼：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while ( t-- )
    {
        int n;
        cin >> n;
        n = n%5;
        if ( n==0 )
            n=5;
        if ( n==1 )
            cout << "Pig" << endl;
        if ( n==2 )
            cout << "Cow" << endl;
        if ( n==3 )
            cout << "Pig" << endl;
        if ( n==4 )
            cout << "Pig" << endl;
        if ( n==5 )
            cout << "Cow" << endl;
    }
}

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/232528.html

標籤：其他

上一篇：淺談三子棋源代碼

下一篇：高精度【學習記錄】

【比賽回顧】廣工2020程式設計決賽——母牛的俄羅斯輪盤賭