取石子游戏

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

70分思路

设\(f[i][j][k]\)表示三堆石子分别为\(i,j,k\)个石子时先手必胜还是先手必败\(1\)为必胜\(0\)为必败
由于石子的位置没有影响，所以\(f[i][j][k]=f[i][k][j]=f[j][i][k]=f[j][k][i]=f[k][i][j]=f[k][j][i]\)
当一种状态可以转移成先手必败态时，该状态是先手必胜态
很明显，只要转移到先手必败态，那么对面就比败了
所以我们枚举后继状态然后看能不能转移到先手必败态，如能即为必胜态，否则就是必败态
再加点优化什么的
若\(f[i][j][k]\)是必败态，那么\(f[i][j][k+a]　(a>0)\)就是必胜态（当然\(a<0\)也都是比败态，但是对算法没什么处）
证明，若\(a>0\)，先手可以对\(k\)拿走\(a\)个石子就转移到必败态
那么我们先全部赋值为必胜态，然后当我们找到一个比必败态后即可\(break\)
用一个f[i][j]表示有没有两堆石子数为\(i,j\)的必败态，如枚举到的包含了\(i,j\)即可\(break\)
另外，可对包含一个为\(0\)的数据特殊对待，下面没有给出代码
下面是主要代码

int f[303][303];
int g[303][303][303];
memset(f,1,sizeof(f));
f[0][0][0]=0,g[0][0]=1;
for (int i=0;i<=100;++i)
    for (int j=i;j<=100;++j){
        if (!g[i][j]){
            for (int k=j;k<=100;++k){
                if (i+j+k<3)    continue;
                if (!g[i][k]&&!g[j][k]){
                    f[i][j][k]=0;
                    for (int p=1;(p<=i||p<=j||p<=k)&&!f[i][j][k];++p){
                        if (p<=i)   f[i][j][k]|=!f[i-p][j][k];
                        if (p<=j)   f[i][j][k]|=!f[i][j-p][k];
                        if (p<=k)   f[i][j][k]|=!f[i][j][k-p];
                        if (p<=i&&p<=j) f[i][j][k]|=!f[i-p][j-p][k];
                        if (p<=i&&p<=k) f[i][j][k]|=!f[i-p][j][k-p];
                        if (p<=j&&p<=k) f[i][j][k]|=!f[i][j-p][k-p];
                        if (p<=i&&p<=j&&p<=k)   f[i][j][k]|=!f[i-p][j-p][k-p];
                    }
                    f[i][k][j]=f[j][i][k]=f[j][k][i]=f[k][i][j]=f[k][j][i]=f[i][j][k];
                    if (!f[i][j][k]){
                        g[i][j]=g[j][i]=g[i][k]=g[k][i]=g[j][k]=g[k][j]=1;
                        break;
                    }
                }
            }
        }
    }

100分思路

上面的复杂度是\(O(n^4)\)，因为去枚举后继状态会枚举到非常多的重复状态，所以我们考虑由必败态反推必胜态
这样重复的状态就大大减少了，复杂度为\(O(n^3)\)多一点

/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年06月10日 星期一 09时35分36秒
*******************************/
#include <cstdio>
#include <fstream>
#include <cstring>
using namespace std;
const int maxn = 303;
//{{{cin
struct IO{
    template<typename T>
    IO & operator>>(T&res){
        res=0;
        bool flag=false;
        char ch;
        while((ch=getchar())>'9'||ch<'0')    flag|=ch=='-';
        while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^'0'),ch=getchar();
        if (flag)    res=~res+1;
        return *this;
    }
}cin;
//}}}
int T,x,y,z;
bool f[maxn][maxn][maxn];
inline void update (int a,int b,int c) { f[a][c][b]=f[b][a][c]=f[b][c][a]=f[c][a][b]=f[c][b][a]=f[a][b][c]; }
int main()
{
    cin>>T;
    f[0][0][0]=0;
    for (int i=0;i<=300;++i)
        for (int j=i;j<=300;++j)
            for (int k=j;k<=300;++k)
                if (!f[i][j][k])
                    for (int p=1;i+p<=300||j+p<=300||k+p<=300;++p){
                        if (i+p<=300)   f[i+p][j][k]=true,update(i+p,j,k);
                        if (j+p<=300)   f[i][j+p][k]=true,update(i,j+p,k);
                        if (k+p<=300)   f[i][j][k+p]=true,update(i,j,k+p);
                        if (i+p<=300&&j+p<=300) f[i+p][j+p][k]=true,update(i+p,j+p,k);
                        if (i+p<=300&&k+p<=300) f[i+p][j][k+p]=true,update(i+p,j,k+p);
                        if (j+p<=300&&k+p<=300) f[i][j+p][k+p]=true,update(i,j+p,k+p);
                        if (i+p<=300&&j+p<=300&&k+p<=300)   f[i+p][j+p][k+p]=true,update(i+p,j+p,k+p);
                    }
    while (T--){
        cin>>x>>y>>z;
        if (f[x][y][z]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

取石子游戏

原文：https://www.cnblogs.com/Morning-Glory/p/10999513.html