題目背景
（原創）
有一天 pb和zs玩游戲 你需要幫zs求出每局的勝敗情況
題目描述
游戲規則是這樣的： 每次一個人可以對給出的數進行分割，將其割成兩個非零自然數，之后由另一個人選擇留下兩個數中的其中一個；之后由另一個人進行分割這個剩下的數，重復步驟……
當一個人無法對數進行分割的時候游戲結束，另一個人獲勝
現在要你求出N次游戲的勝敗
每局由pb先進行分割，如果pb贏輸出"pb wins" 如果zs贏輸出"zs wins"
注：雙方都是絕頂聰明的
輸入格式
第一行一個數N，表示資料組數
之后N行，每行一個數M，表示每局初始的數
輸出格式
共N行，每行一串字符 表示游戲結果
輸入輸出樣例
輸入
5
1
3
7
20
5輸出
zs wins
zs wins
zs wins
pb wins
zs wins
說明/提示
1<N<50 1<=m<=1000000000
*************************************************************************************************************************************************************************************************************************************
解題思路：
這是一道很簡單的博弈問題，甚至只要多寫幾組資料測驗一下就可以找到規律，就是偶數的時候先手必勝，奇數的時候后手必勝，下面我們來分析一下這是為什么
博弈問題還是自底向上的尋找解決思路，我們來簡單的模擬一下，
n=1，先手無法再分，先手必敗
n=2，先手將其分為1+1，后手無法再分，先手必勝
n=3，先手只能分為1+2，后手遇見n=2情況，后手必勝
n=4，先手將其分為1+4，后手遇見n=3的情況，這個時候則變成了先手必勝
……
我們首先知道，任何一個奇數只能轉化成一個奇數加一個偶數，也就是說如如果先手是奇數，先手一定會拆出一個偶數m，后手就可以把m轉化為1+(m-1)，(m-1)就是奇數，讓先手始終面對奇數的情況，這樣最后先手一定會遇見3拆出一個1+2的狀態，這時候后手就是贏了，也就是說如果n是奇數，先手就是必敗的，反之如果先手是n偶數，那么拆成1+(n-1)，讓后手始終面對奇數，這樣先手就是必勝的，
另外對于博弈論偶然發現了一句話覺得對于理解必勝態，必敗態，最優策略有很大的幫助，分享給大家
必敗態從來沒有最佳策略, 博弈也不是雙方的博弈, 而是處在必勝態的那方和自己博弈. 而這場博弈, 由于絕頂聰明的前提, 是必勝的, 而我們要做的, 只是找出誰有跟自己博弈的機會.
下面附上ac代碼
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
#define M 1000000
int num[15]={2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768};
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
ll t,n,m,p;
cin>>t;
while(t--)
{
ll n;
ll cntpb=0,cntzs=0,step=1;
cin>>n;
if(n%2==0)
cout<<"pb wins"<<endl;
else
cout<<"zs wins"<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/277706.html
標籤：其他
上一篇：Fragment學習總結（1）