题目描述
桌上有若干个石子，每次可以取质数个。谁先取不了，谁就输。问最少几步能赢？（一个人取一次算一步）
输入输出格式
输入格式：
第一行N，表示有N组数据
接下来N行为石子数
输出格式：
每组数据一个数，若必胜，则输出最少步数，否则输出-1
输入输出样例
输入样例#1：
3
8
9
16
输出样例#1：
1
-1
3
说明
石子数≤20000，N≤10
Solution
NIm 游戏的质数版 思路基本和原版一致 即每一个必胜状态都由上一次必败的状态转过来.然后需要先一个筛法筛出20000以内的质数. 然后照Nim 游戏的动规方程 即可.不过这里的状态要多加一维用于加上场数这个信息的保存. 这里用的是
f[i][0] 代表场数
f[i][1] 代表
1 --> 必胜
-1 --> 必败
细节就是质数枚举的时候要倒着从大的开始 否则会有鬼.
代码 :
#include<bits/stdc++.h>
using namespace std;
int n,f[][]={},a[];
int p[],maxn=-,sum; int v[];
void pre()
{
for(int i=;i<=;i++)
{
if(v[i]==)
{
p[++sum]=i;
for(int j=;j*i<=;j++)
v[i*j]++;
}
}
} void solve()
{
f[][]=-;f[][]=;
f[][]=-;f[][]=;
f[][]=;f[][]=;
f[][]=;f[][]=;//初始化几个点
for(int i=;i<=maxn;++i)
for(int j=sum;j>=;--j)
if(p[j]<=i)
{
if(f[i-p[j]][]==-) //前驱为必败
if(f[i][]==||f[i][]==-)//尚未判定状态
{
f[i][]=;
f[i][]=f[i-p[j]][]+;
}
else
f[i][]=min(f[i][],f[i-p[j]][]+);//选取场数最小值
if(f[i-p[j]][]==)//前驱为必胜
if(f[i][]==)
{
f[i][]=-;
f[i][]=f[i-p[j]][]+;
}
else if(f[i][]==-)
f[i][]=max(f[i][],f[i-p[j]][]+); //败了久选最大值.
}
return;
} int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
maxn=max(a[i],maxn);
}
pre();
solve();
for(int i=;i<=n;i++)
if(f[a[i]][]==-)
printf("-1\n");
else printf("%d\n",f[a[i]][]);
return ;
}