丟史蒂芬妮

發布時間: 2017年7月9日 18:17?? 最后更新: 2017年7月9日 21:05?? 時間限制: 1000ms?? 內存限制: 128M

描述

有一天，空和白很無聊，決定玩盛大游戲，考慮到兩個人玩，他們隨便掏了一個游戲出來：在一個n*m的棋盤上，首先把史蒂芬妮·多拉放在左上角(1,1)的位置。每次一個人可以將她往下，往右，往右下丟一格。當前回合，誰不能丟史蒂芬妮，誰就輸了。（注意，不可以把活人丟出棋盤啦！）游戲總是空先手。

白說，這是一個垃圾游戲！我們每次把史蒂芬妮丟素數個位置吧！（換句話說，每次丟2或3或5或7或…格）空答應了。

我們都知道，空和白都很聰明，不管哪方存在一個可以必勝的最優策略，都會按照最優策略保證勝利。

玩了一局，空已經知道了這個游戲的套路，現在他決定考考你，對于給定的n和m，空是贏是輸？如果空必勝，輸出“Sora”（無引號）；反之，輸出“Shiro”（無引號）。

輸入

第一行有一個T表示數組組數，1<= T < 100000
從第二行開始，每行為棋盤大小，n、m分別表示行列。
1=< n <= 500，1=< m <= 500

輸出

對于每組數據，按題目要求輸出。

樣例輸入1 4 1 1 2 2 10 10 30 30 樣例輸出1 Shiro Shiro Shiro Sora

題解：我們可以看出這是一個Grundy博弈問題

每個局面（當前所處的位置）代表一個狀態。這個狀態如果不是必勝態，那么就是必敗態。

且滿足，從必敗態出發，一定有方法轉移到必勝態。并且從必勝態出發，不論怎樣走，都將轉變為必敗態。

這就是一個求grundy數的問題了

我們定義局面(i,j)的grundy數為grundy[i][j]，并且設prime[k]是可行的素數步數。

那么，從這個局面可以轉移到(i-prime[k],j)或者(i,j - prime[k])或者(i-prime[k],j - prime[k])

所以求grundy數的函數就可以寫成這樣：

for(int i = 1;i <= 500;i++){for(int j = 1;j <= 500;j++){//set<int> st;memset(st,0,sizeof(st));for(int k = 0;k < cnt;k++){int step = prime[k];if(step < i) st[grundy[i - step][j]]++;if(step < j) st[grundy[i][j - step]]++;if(step < i && step < j) st[grundy[i - step][j - step]] ++ ;}int g = 0;while(st[g] != 0) {g++;}//cout<<g<<endl;grundy[i][j] = g;}//cout<<i<<endl;}AC代碼:

#include <iostream> #include <cstdio> #include <cstring> #include <set> using namespace std; const int MAX = 505; int prime[MAX]; int grundy[MAX][MAX]; int cnt = 0; int n,m; int st[100]; void init(){for(int i = 2;i <= 500;i++){int f = 1;for(int j = 2;j*j <= i;j++){if(i%j == 0){f = 0;break;}}if(f){prime[cnt++] = i;}}//for(int i = 1;i <= 500;i++){for(int j = 1;j <= 500;j++){//set<int> st;memset(st,0,sizeof(st));for(int k = 0;k < cnt;k++){int step = prime[k];if(step < i) st[grundy[i - step][j]]++;if(step < j) st[grundy[i][j - step]]++;if(step < i && step < j) st[grundy[i - step][j - step]] ++ ;}int g = 0;while(st[g] != 0) {g++;}//cout<<g<<endl;grundy[i][j] = g;}//cout<<i<<endl;}} int main(){init();int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);puts((grundy[n][m] == 0) ? "Shiro" : "Sora");}return 0; }

總結

以上是生活随笔為你收集整理的2017上海金马五校赛 丢史蒂芬妮 博弈问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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