丟史蒂芬妮

發(fā)布時(shí)間: 2017年7月9日 18:17?? 最后更新: 2017年7月9日 21:05?? 時(shí)間限制: 1000ms?? 內(nèi)存限制: 128M

描述

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

白說(shuō)，這是一個(gè)垃圾游戲！我們每次把史蒂芬妮丟素?cái)?shù)個(gè)位置吧！（換句話(huà)說(shuō)，每次丟2? 或3? 或5? 或7? 或…格）空答應(yīng)了。

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

玩了一局，空已經(jīng)知道了這個(gè)游戲的套路，現(xiàn)在他決定考考你，對(duì)于給定的n? 和m? ，空是贏是輸？如果空必勝，輸出“Sora”（無(wú)引號(hào)）；反之，輸出“Shiro”（無(wú)引號(hào)）。

輸入

第一行有一個(gè)T表示數(shù)組組數(shù)，1<=T<100000?
從第二行開(kāi)始，每行為棋盤(pán)大小，n? 、m? 分別表示行列。
1=<n<=500? ，1=<m<=500?

輸出

對(duì)于每組數(shù)據(jù)，按題目要求輸出。

樣例輸入1 復(fù)制 4 1 1 2 2 10 10 30 30 樣例輸出1 Shiro Shiro Shiro Sora
分析：記憶化搜索即可；
代碼： #include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <bitset> #include <map> #include <queue> #include <stack> #include <vector> #include <cassert> #include <ctime> #define rep(i,m,n) for(i=m;i<=(int)n;i++) #define mod 1000000007 #define inf 0x3f3f3f3f #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair<int,int> #define sys system("pause") #define ls rt<<1 #define rs rt<<1|1 const int maxn=5e2+10; const int N=5e2+10; using namespace std; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;} int n,m,k,t,qu[maxn]; bool dp[maxn][maxn],vis[maxn][maxn]; bool dfs(int x,int y) {if(vis[x][y])return dp[x][y];vis[x][y]=true;for(int i=1;i<=qu[0];i++){if(x-qu[i]>0)dp[x][y]|=(!dfs(x-qu[i],y));if(y-qu[i]>0)dp[x][y]|=(!dfs(x,y-qu[i]));if(x-qu[i]>0&&y-qu[i]>0)dp[x][y]|=(!dfs(x-qu[i],y-qu[i]));}return dp[x][y]; } bool sushu(int x) {if(x==2)return true;else if(x%2==0)return false;for(int i=3;i*i<=x;i+=2)if(x%i==0)return false;return true; } void init() {int i,j;rep(i,2,maxn-10)if(sushu(i))qu[++qu[0]]=i;rep(i,1,maxn-10)rep(j,1,maxn-10)dfs(i,j); } int main() {int i,j;init();scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);puts(dp[n][m]?"Sora":"Shiro");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/dyzll/p/7144463.html

總結(jié)

以上是生活随笔為你收集整理的上海五校赛 丢史蒂芬妮的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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