题解 P1857 【质数取石子】

· · 题解

这题是一道非常复杂的博弈论题

首先 通过近似线性筛的筛法 预处理出所有的质数

我们设SG函数为此游戏胜负的状态 sg[i]=0为负 1为正 表示当石子数=i时，当前操作的人必败/胜

用一个队列对所有sg函数进行预处理 所有必败状态加上一个质数必然为必胜状态 因为当石子数=必败状态的石子数+质数的时候，当前操作的人仅需取走这个质数的石子便可以获胜

别以为知道这些就能A掉了

电脑不像你想象的那么沙雕 每当电脑觉得他要输的时候 电脑会想方设法拖延你获胜的步伐 同理 当你要赢的时候 你总是想快一点胜利

那么最重要的一点要来了

我们需要在适当的时候取最大或最小值

枚举所有位置和当前位置可扩展的位置，我们且令f[x]为石子数=x时的最小步数

如果扩展到的位置没被扩展过，那么当前位置就给他一个初始值=f[l]+1 如果！！！上一个状态为必胜状态并且当前状态为必胜状态，那么扩展了这个节点毫无意义，直接跳过这个点；

如果上一个扩展而来的状态是必胜状态，当前点却是必败状态，如果你是人，你怕判断这个吗？？？直接-1就可以了，关键是要考虑对手的感受，对手不愿意让你输，他会竭尽所能找你麻烦，步数要取max啦。如果上一个扩展而来的状态是必败状态，当前点却是必胜状态。

同样想一想，如果你是你的对手，你要赢了，你怕判断这个吗？？？直接-1掉了，但是你是你，你要速战速决，你要用最少的步数解决这个无聊的游戏，所以在这里f去的是min。到这里最关键的地方就结束了。

好了O(1)的查询 此题AC了（本人写了七个小时）蒟蒻勿喷

#include <bits/stdc++.h>
#define maxn 20000
using namespace std;
int f[20010];
int prime[20010];
int pd[20010];
int q[1000010];
int sg[20010];
int hsh[20010]; 
int lose[100010];
int n,x,l,r,standard=0,cnt=0,last,losenum;
inline void build_prime()
{
    pd[1]=1;
    for (int i=2;i<=maxn;i++)
    {
        int j=i;
        if (pd[i]) continue;
        while (j<=maxn)
        {
            j+=i;
            pd[j]=1;
        }
    }
    for (int i=2;i<=maxn;i++)
    {
        if (!pd[i])
          prime[++cnt]=i;
    }
}
void prepare()
{
    while (l<=r)
    {
      for (int i=1;i<=cnt;i++)
      {
        int next=prime[i]+q[l];
        if(next>maxn) continue; 
        int last=q[l];
        if (!sg[q[l]])
          sg[next]=1;
      }
      if (l==r) {
            for (int i=last+1;i<=maxn;i++)
            {
                if (sg[i]==0)
                {
                    last=i;
                    lose[i]=1;
                    q[++r]=i;
                    break;
                }
            }
                 }
      l++;

    }
}
inline void dp()
{
    while (l<=maxn)
    {
        for (int i=1;i<=cnt;i++)
        {
            int next=prime[i]+l;
            int lasti=l;
            int num=f[l]+1;
            if (next>maxn) continue;
            if (sg[l]&&sg[next]) continue;
            if (!lose[next]&&lose[l])
            {
                if (!f[next]) f[next]=num;
                else f[next]=min(f[next],num);
            }
            if (lose[next]&!lose[l])
            {
                if (!f[next]) f[next]=num;
                else f[next]=max(f[next],num);
        }
        l++;
    }
}
int main()
{   
    memset(hsh,0,sizeof(hsh));
    memset(pd,0,sizeof(pd));
    build_prime();
    l=1;r=2;
    memset(q,0,sizeof(q));
    memset(sg,0,sizeof(sg));
    //sg[i]=1 win sg[i]=0 lose
    for (int i=1;i<=20009;i++)
    {
        f[i]=standard;
    }
    sg[0]=0;sg[1]=0;sg[2]=1;sg[3]=1;
    q[1]=0;q[2]=1;
    f[0]=0;f[1]=0;
    hsh[0]=1;hsh[1]=1;
    last=1;
    memset(lose,0,sizeof(lose));
    prepare();
    lose[1]=1;lose[0]=1;//其实lose数组没什么必要
    //就是sg函数为0的情况
    memset(q,0,sizeof(q));
    q[1]=0;q[2]=1;
    f[0]=0;f[1]=0;
    l=0;r=2;
    dp();
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        if (sg[x]==0) cout<< -1 <<endl;
        else cout<<f[x]<<endl;
    }
}