发布时间: 2017年7月9日 20:20 最后更新: 2017年7月10日 21:11 时间限制: 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 提示数据量很大，建议使用scanf或关闭cin的同步。
选择语言 想法：记忆化搜索
可以将问题转化成取石子：
有两堆石子，数量分别为n个和m个（n*m的棋盘），每次可以取走其中一堆质数个石子，
也可以同时取走两堆数量相同的质数个石子，到谁不能取谁失败
很明显，(0, 0)，(0,1)，(1,0)都是必输态
那么(2,0)，(0,2)，(2,1)，(0,3)，(3,0)，(0,3)，……，(k,1)，(1,k)，(k+1,0)，(0,k+1)（k为质数）都是必赢态，因为它们都可以一步取到必输态
知道可以这样处理就好办了，因为n和m就500，直接记忆化搜索预处理
dp[x][y]==0表示(x,y)状态必输，dp[x][y]==1表示(x,y)状态必赢
那么如果(x,y)的前驱只要有一个是必输态，那么(x,y)就是必赢态，否则必输
代码一：
#include<stdio.h> #include<string.h> int k=0, dp[505][505], pri[505], jud[505] = {1,1}; int Sech(int x, int y) { int i; if(dp[x][y]!=-1) return dp[x][y]; for(i=1;i<=k&&pri[i]<=x;i++) { if(Sech(x-pri[i], y)==0) { dp[x][y] = 1; return dp[x][y]; } } for(i=1;i<=k&&pri[i]<=y;i++) { if(Sech(x, y-pri[i])==0) { dp[x][y] = 1; return dp[x][y]; } } for(i=1;i<=k&&pri[i]<=y&&pri[i]<=x;i++) { if(Sech(x-pri[i], y-pri[i])==0) { dp[x][y] = 1; return dp[x][y]; } } dp[x][y] = 0; return dp[x][y]; } int main(void) { int T, n, i, j, m; for(i=2;i<=500;i++) { if(jud[i]) continue; pri[++k] = i; for(j=i*i;j<=500;j+=i) jud[j] = 1; } scanf("%d", &T); memset(dp, -1, sizeof(dp)); while(T--) { scanf("%d%d", &n, &m); dp[0][0] = dp[1][0] = dp[0][1] = dp[1][1] = 0; if(Sech(n-1, m-1)) printf("Sora\n"); else printf("Shiro\n"); } return 0; }
代码二：
#include<bits/stdc++.h> using namespace std; const int maxn= 500; int prime[maxn+5]= {0}; int num_prime=0; bool isprime[maxn+5]= {1,1}; int vis[maxn+5][maxn+5]; void init() { for(int i=2; i<maxn+5; i++) { if(!isprime[i]) prime[num_prime++]=i; for(int j=0; j<num_prime&&i*prime[j]<maxn+5; j++) { isprime[i*prime[j]]=1; if(i%prime[j]==0) break; } } memset(vis,0,sizeof(vis));//1:必胜 2：必败 vis[1][1]=2; for(int i=1; i<=maxn; i++) { for(int j=1; j<=maxn; j++) { if(vis[i][j]==0) { vis[i][j]=2; } if(vis[i][j]==2) { for(int k=0; ; k++) { if(i+prime[k]>maxn&&j+prime[k]>maxn) break; if(i+prime[k]<=maxn) { vis[i+prime[k]][j]=1; } if(j+prime[k]<=maxn) { vis[i][j+prime[k]]=1; } if(i+prime[k]<=maxn&&j+prime[k]<=maxn) { vis[i+prime[k]][j+prime[k]]=1; } } } } } } int main() { init(); int n,m; int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); if(vis[n][m]==1) puts("Sora"); else puts("Shiro"); } return 0; }
