shu418丢史蒂芬妮博弈np图

xiaoxiao2021-02-27  166

丢史蒂芬妮

发布时间: 2017年7月9日 18:17   最后更新: 2017年7月9日 21:05   时间限制: 1000ms   内存限制: 128M

描述

有一天,空和白很无聊,决定玩盛大游戏,考虑到两个人玩,他们随便掏了一个游戏出来:在一个 nm 的棋盘上,首先把史蒂芬妮·多拉放在左上角 (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

思路:

这道题目是一道博弈里面关于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个赋值为true flag[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;*/ }

丢史蒂芬妮

发布时间: 2017年7月9日 18:17   最后更新: 2017年7月9日 21:05   时间限制: 1000ms   内存限制: 128M

描述

有一天,空和白很无聊,决定玩盛大游戏,考虑到两个人玩,他们随便掏了一个游戏出来:在一个 nm 的棋盘上,首先把史蒂芬妮·多拉放在左上角 (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
转载请注明原文地址: https://www.6miu.com/read-16284.html

最新回复(0)