shu418丢史蒂芬妮 博弈n/p图

第一行有一个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

思路：

这道题目是一道博弈里面关于P/N的应用，和杭电的2147是一样的解法，算个升级版，不懂的可以先去做一下2147.

主要的思路就是，因为这个数据比较小，总共最大的棋盘也就500*500，所以可以先对棋盘进行处理。现在已知的条件是：1.从（1,1）开始  2 .向下，向右，对角线向下走素数个位置。所以先求出五百以内的所有素数，然后对于每一个i,j位置进行判断能否进行2操作，如果行，那么当前位置为必胜态，即不会输。然后每一个dp[i][j]存的是有多少个必胜态能够走到这个位置。所以到时候我们直接判断dp[n][m]是否为0，因为如果为0，那么从起点到最后的n,m位置没有一个可以走到，所以，起点为必输态，即先手一定会输。

下面是代码：

#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
#define N 1001
bool prime[N];
int flag[N];
int kk[N],v=0;
int dp[505][505];
int st[505];void getprime()///快速求素数
{int z=0,i;//flag[z++]=2;kk[v++]=2;for(i=3; i<N; i++)if(i%2) //在flag数组中存n的奇数{prime[z]=true;//把prime中数组前n个赋值为trueflag[z]=i;z++;}for(i=0; i<z; i++)//算法的核心 在奇数中求素数  如3是素数  3的所有倍数都不是{for(int j=i+flag[i]; j<z; j+=flag[i])if(prime[i]) prime[j]=false;}for(int i=0;i<=500;i++)if(prime[i])//cout<<flag[i]<<endl;kk[v++]=flag[i];//cout<<555<<endl;
}
void judge()///预处理
{//cout<<v<<endl;for(int i=1;i<=500;i++){for(int j=1;j<=500;j++){//cout<<"---"<<endl;memset(st,0,sizeof(st));for(int k=0;k<v;k++){if(kk[k]<i) st[dp[i-kk[k]][j]]++;if(kk[k]<j) st[dp[i][j-kk[k]]]++;if(kk[k]<i&&kk[k]<j) st[dp[i-kk[k]][j-kk[k]]]++;}int g=0;while(st[g]){g++;}dp[i][j]=g;///可以走到i,j位置的次数}}
}
int main()
{int t,n,m;getprime();judge();//cout<<132<<endl;scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);if(dp[n][m]==0) printf("Shiro\n");///判断是否走到n,m位置，如果有，即dp[n][m]，为必输点，else printf("Sora\n");            ///那么先手一定会走这条路达到胜利，即如果存在，那么先手一定赢。}return 0;/*for(int i=0;i<v;i++)cout<<kk[i]<<endl;*/
}