題干：

鏈接：https://ac.nowcoder.com/acm/contest/373/A
來源：牛客網(wǎng)
?

Alice和Bob正在玩一個很經(jīng)典的游戲。

有?n?n個硬幣初始時全部正面朝上，每一輪Alice必須選擇其中任意的恰好?m?m枚硬幣并將它們?nèi)糠D(zhuǎn)，如果若干輪翻轉(zhuǎn)后所有硬幣全部反面朝上，那么Alice就贏得了游戲。

假設(shè)我們認為每枚硬幣只有正面朝上和反面朝上兩種狀態(tài)且只考慮?m?m為偶數(shù)的情況，問題會比較簡單。

但是出題人希望這道題更毒瘤一些，所以他增加了一條規(guī)則：Bob在整個游戲中可以有一次機會使壞--在Alice某一輪翻轉(zhuǎn)完之后，偷偷選擇任意一枚硬幣并將它翻轉(zhuǎn)。

為了不讓Alice贏得游戲，Bob會采取最優(yōu)的策略。

現(xiàn)在給定?n?n和?m?m，請問Alice是否可以贏得游戲？

注意：

Bob雖然可以在任何輪翻轉(zhuǎn)之后使壞，但是在整個游戲中只有一次這樣的機會。也就是說，如果在某一輪之后使用了這個機會，那么以后都不能再使用。

輪次可以認為是無限的，只要在任何一輪翻轉(zhuǎn)后所有硬幣全部反面朝上，Alice就立即贏得游戲勝利，Bob即使沒有用掉使壞的機會也不能再偷偷翻轉(zhuǎn)硬幣。

輸入描述:

每個輸入文件有多個測試樣例。

第一行一個整數(shù)?T(T≤30000)?T(T≤30000)--測試樣例個數(shù)。

然后?T?T行，每行兩個整數(shù)?n?n和?m?m?(1≤m≤n≤109,m是偶數(shù))?(1≤m≤n≤109,m是偶數(shù))--硬幣的數(shù)量和每一輪翻轉(zhuǎn)硬幣的數(shù)量。其中第?i+1?i+1行表示第?i?i個樣例。

輸出描述:

輸出?T?T行，第?i?i行輸出第?i?i個測試樣例的答案。

如果Alice可以贏得游戲輸出“Yes”，否則輸出“No”，請注意區(qū)分大小寫。

示例1

輸入

復制

2 2 2 8 6

輸出

復制

Yes No

說明

對于第一個樣例，Alice直接一輪翻轉(zhuǎn)全部兩個硬幣就可以贏得游戲。對于第二個樣例，Bob如果在第一輪結(jié)束后將任意一枚反面朝上的硬幣翻轉(zhuǎn)，之后Alice無論怎樣翻轉(zhuǎn)硬幣也永遠不能使得所有硬幣全部反面朝上。

解題報告：

? ?如果要贏，只能第一次就翻出結(jié)果來，否則就輸。作者：lililalala
證明：
一回合不能直接翻轉(zhuǎn)所有硬幣，因為m是偶數(shù)，所以只需要討論n的奇偶性。
（1）n是奇數(shù)
某回合結(jié)束后所有硬幣反面朝上可以等價于所有硬幣都被翻轉(zhuǎn)了奇數(shù)次。假設(shè)可以達成，那么
該回合后所有回合總翻轉(zhuǎn)次數(shù)一定要為奇數(shù)(因為奇數(shù)個奇數(shù)相加是奇數(shù))
然而m是偶數(shù)，即使在不使壞的情況下，無論翻轉(zhuǎn)多少個回合，總翻轉(zhuǎn)次數(shù)也一定是偶數(shù)，
所以在這種情況下是不可能贏得游戲的.答案是No
（2）n是偶數(shù)
同理，完成時所有硬幣都一定要被翻轉(zhuǎn)了奇數(shù)次，但是n是偶數(shù)，所以總翻轉(zhuǎn)次數(shù)一定要為偶
數(shù)，在不被使壞的情況下，至少有可能完成，但是除去n=m的情況外，只要在第一回合后立即
被使壞，不管翻轉(zhuǎn)哪一個硬幣，都會使得總翻轉(zhuǎn)次數(shù)由總是偶數(shù)變成總是奇數(shù)，和n為奇數(shù)
時原理相同，也不可能贏得游戲，答案是No
結(jié)論: n=m時答案是Yes，否則答案是No

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; ll n,m; int main() {int t;cin>>t;while(t--) {scanf("%lld%lld",&n,&m);if(n == m) puts("Yes");else puts("No");}return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 373A】翻硬币问题（博弈，结论，分析）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。