[比赛][博弈论][SG表] 2018 ICPC徐州网络赛 B BE, GE or NE

赛后过题,心塞。

这题搞明白以后就是一个暴力打SG表的过程,-1表示bad,0表示normal,1表示good,从最后一轮开始,分奇偶轮,如果是奇数轮也就是先手轮,那就尽可能往1,也就是往大了转移,如果是偶数轮,也就是后手轮,那就往小了转移。真的是服了,这么简单当时就是没想到,唉。

因为n只有1000,每次的状态也最多只有200,(妈的限制上下界不就是为了可以暴力打表或者暴搜吗。。这么明显的特征没看出来我也是呵呵)想到这儿的时候直接明白了,为什么比赛时候那么多人过还那么高的通过率,呵呵呵呵呵,当时脑子真是短路。心情复杂。思考。

 

#include 

using namespace std;
typedef long long LL;
const int maxn=1e3+5;

int ops[maxn][4];
int st[maxn][205];
int main()
{
    int n,m,k,l;
    scanf("%d%d%d%d",&n,&m,&k,&l);
    k+=100;l+=100;m+=100;
    for (int i=1;i<=n;i++)
        scanf("%d%d%d",&ops[i][1],&ops[i][2],&ops[i][3]);
    for (int i=0;i<=200;i++)
    {
        if(i<=l)
            st[n+1][i]=-1;
        else if(i>=k)
            st[n+1][i]=1;
        else
            st[n+1][i]=0;
    }
    for (int i=n;i>0;i--)
    {
        for (int j=0;j<=200;j++)
        {
            int a=-1,b=1;
            if(ops[i][1])
            {
                a=max(a,st[i+1][min(200,j+ops[i][1])]);
                b=min(b,st[i+1][min(200,j+ops[i][1])]);
            }
            if(ops[i][2])
            {
                a=max(a,st[i+1][max(0,j-ops[i][2])]);
                b=min(b,st[i+1][max(0,j-ops[i][2])]);
            }
            if(ops[i][3])
            {
                a=max(a,st[i+1][200-j]);
                b=min(b,st[i+1][200-j]);
            }
            if(i%2)//error
                st[i][j]=a;
            else
                st[i][j]=b;
        }
    }
    if(st[1][m]==1)
        cout<<"Good Ending\n";
    else if(st[1][m]==-1)
        cout<<"Bad Ending\n";
    else
        cout<<"Normal Ending\n";
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据