Alice and Bob

題意：

兩人博弈，每次一個人從一堆中拿k個，同時從另一堆拿k * s(s>=0)個，問誰先不能拿
10000組數據,N<=5000

題解：

(x,y)表示第一堆石頭數量為x，第二堆為y
如果(x,y)是必敗狀態，那么通過取走石頭一次直接形成(x,y)的(x1,y1)必然不是必敗狀態

如果(x,y)不是必敗狀態，那(x1,y1)就不一定了
可以通過反證去理解
指向必敗狀態的是必勝狀態，必勝狀態可以指向必敗，也可以指向必勝。必敗狀態無法到必敗狀態

綜上：我們只需要關注一個點是否可以由必敗點得到，如果可以，該點不是必敗點，否則是必敗點

此時復雜度為O(n⁴),但是要知道一個結論：對于一個的i只存在至多一種j后手能夠獲勝
證明如下：
若存在（i，q）（i，p）（p>q）滿足后手勝，那么Alice只需將（i，p）->（i，q）即可獲勝，不滿足后手勝的條件。
這樣復雜度就大約在O(n³)

代碼：

#include<iostream> #include<stdio.h> using namespace std; bool f[5001][5001]; int main() { for(int i=0;i<=5000;i++)//自小到大枚舉i，jfor(int j=0;j<=5000;j++){if(f[i][j]==0)//對于每種必敗態進行拓展{for(int k=1;k+i<=5000;k++)for(int s=0;s*k+j<=5000;s++)f[i+k][j+s*k]=1;for(int k=1;k+j<=5000;k++)for(int s=0;s*k+i<=5000;s++)f[i+s*k][j+k]=1;}}int t,n,m;cin>>t;while(t--){scanf("%d%d",&n,&m);if(f[n][m]==0){puts("Bob");}else puts("Alice");}return 0; }

總結

以上是生活随笔為你收集整理的Alice and Bob的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。