题解 P1857 【质数取石子】

O2人 · 2020-11-17 20:46:42 · 题解

应该算是DP题，难度一般吧。

一、简化问题

我们先假装这题只是让我们求解先手必胜还是必负

我的思路是先用求出vis[i]=0/1（vis[i]表示当有i颗石子时，先手取石子是必胜还是必败）。

很简单：

//P数组存储的是素数
for (int i=2;i<N;i++){
    bool flg=false;
    for (int j=1;j<=len&&i-P[j]>=0;j++) flg|=1-vis[i-P[j]];
   //只要接下来的对方面临的状态有一个是必败的，那么我们先手就是必胜的
    vis[i]=flg;
}

求出了这个我们就可以开心地求出-1的情况啦。

二、求解问题

接下来是求F[i]（F[i]表示当有i颗石子时，先手取石子需要几步能取完）

很显然的是，如果先手必胜，我们要尽量加快获胜，如果先手必败，我们要减缓失败！

所以可以得出转移方程：

for (int j=1;j<=len&&i-P[j]>=0;j++)
if (vis[i]) F[i]=min(F[i],vis[i-P[j]]?1<<30:F[i-P[j]])+1;
       else F[i]=max(F[i],F[i-P[j]])+1;

注意这里有一个细节，因为我们如果是必胜的，我们绝对不能往失败的方向走——我们不是傻子！所以当vis[i]==1时，答案只能从vis[i-P[j]]==0的F[i-P[j]]转移过来。

样例可以检测出来这个问题，刚开始我傻了没注意，还好样例点醒我，使我一遍A了这题（要是比赛样例也这么给力就好了QAQ）。

全部代码：

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
inline int read(){
    int red=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') red=(red<<3)+(red<<1)+ch-'0',ch=getchar();
    return red*f;
}
const int N=20005;
int F[N],P[N],len,T;
bool vis[N];
void Make(){
    for (int i=2;i<N;i++){
        if (!vis[i]) P[++len]=i;
        for (int j=1;j<=len&&i*P[j]<N;j++){
            vis[i*P[j]]=true;
            if (i%P[j]==0) break;
        }
    }
}
int main(){
    freopen("text.in","r",stdin);
    freopen("text.out","w",stdout);
    Make();
    for (int i=2;i<N;i++){
        bool flg=false;
        for (int j=1;j<=len&&i-P[j]>=0;j++) flg|=1-vis[i-P[j]];
        vis[i]=flg;
    }
    for (int i=2;i<N;i++){
        int res=vis[i]?(1<<30):-(1<<30);
        for (int j=1;j<=len&&i-P[j]>=0;j++)
        if (vis[i]) res=min(res,vis[i-P[j]]?1<<30:F[i-P[j]]);else res=max(res,F[i-P[j]]);
        F[i]=res+1;
    }
    T=read();
    while (T--){
        int x=read();
        if (!vis[x]) printf("-1\n");
        else printf("%d\n",F[x]);
    }
    return 0;
}