题目链接：http://acmoj.shu.edu.cn/problem/418/ 题意： 题目是中文，很容易理解，博弈论 规模： T:[1,1e5] n:[1,500] m[1,500] 类型： 博弈论，搜索
分析： 看起来像威尔夫博弈，但不同是要根据素数筛选。T很大，就是要把表打出来直接查询
时间复杂度&&优化： O(1*T) 代码：
#include <iostream> #include <bits/stdc++.h> using namespace std; int a[505][505]; int is_prime[505]; void get_prime(){ for(int i=0;i<505;i++){ is_prime[i]=1; } is_prime[1]=0; is_prime[0]=0; for(int i=2;i<505;i++){ for(int j=2;j*i<505;j++){ is_prime[j*i]=0; } } } void get_a(){ memset(a,1,sizeof(a)); a[1][1]=1; for(int i=1;i<505;i++){ for(int j=1;j<505;j++){ a[i][j]=!a[i][j]; for(int k=0;k<505;k++){ if(is_prime[k]==1){ if(i+k<=500)a[i+k][j]&=a[i][j]; if(j+k<=500)a[i][j+k]&=a[i][j]; if(i+k<=500&&j+k<=500)a[i+k][j+k]&=a[i][j]; } } } } } int main() { int T; cin>>T; int n,m; get_prime(); get_a(); while(T--){ scanf("%d%d",&n,&m); if(a[n][m]==0)printf("Shiro\n"); else printf("Sora\n"); } return 0; }