题解 T4【1+1】

critnos · 2021-01-14 21:20:19 · 个人记录

不知道大家用的是什么玄学做法。。赛时一位 AC 的神仙 qq1010903229 的做法没有看懂，另一位神仙 墨染空 的 6.67KB 代码同样玄学。

测试点 1

枚举走的四步，那个能赢就打哪个。

测试点 2

没准有点智（sui）能（ji）的就能过了。

测试点 3\sim 10

这里提供 std 的做法。

深搜，第 deep 层子树给一个 \dfrac 1 {2^{deep}} 的权。设当前 dfs 的状态为 \{pl,cp\}，如果：

• 轮到 pl（即自己）走，如果走的四步中的一步可以获胜就直接走这一步获胜，这时候可以获得这棵子树的权，不用继续往下递归了。

• 轮到 cp 走，如果走的四步中的一步可以获胜就直接走这一步获胜，这时候这棵子树的权为 0，不用继续往下递归了。

这样还是不够智能，只能获得 60 pts 左右。“如果走的四步中的一步可以获胜就直接走这一步获胜”可以更新为“这步一定可以获胜”。

啥叫“一定可以获胜”呢？就是说这步选择一步走，对方无论怎样走，都会再次进入一个“一定可以获胜”的局面。递归定义的。显然，若自己可以直接获胜是一个必胜的局面，对方可以直接获胜不是一个必胜的局面。在最开始预处理即可。

说句闲话这个游戏还挺好玩的

另外谁打赢了最后几个测试点请一定私信 mcyl35 orz orz

有一部分是 19 年写的所以可能比较奇怪233

#include<bits/stdc++.h>
#define write cout<<"player:\n"<<pl[0]<<' '<<pl[1]<<"\ncomputer:\n"<<cp[0]<<' '<<cp[1]<<'\n'<<'\n'
using namespace std;
const int w=8;
int sum;
int dp[10][10][10][10];
int lx(int a[2])
{
    int b[2];
    b[0]=a[0],b[1]=a[1];
    if(b[0]>b[1]) swap(b[0],b[1]);
    if(b[0]==3&&b[1]==3||b[0]==3&&b[1]==5||b[0]==1&&b[1]==6) return 1;
    if(b[0]==1&&b[1]==9) return 2;
    if(b[0]==1&&b[1]==5) return -1;
    if(b[0]==5&&b[1]==5) return -2;
    return 0;
}
int jm(int a[2],int b[2])
{
    if(lx(a)<=0) return 0;
    if(lx(a)+lx(b)>0) return 1;
    if(lx(a)==1)
    {
        if(lx(b)==-1) b[0]=b[1]=1;
        else b[0]=5,b[1]=1;
    }
    else b[0]=b[1]=1;
    return 0;
}
void dfs(int c,int a[2],int b[2],int f)
{
    int ca[2],cb[2],i,j;
    ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
    if(c==w) return;
    if(c%2==0) 
    {
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                cb[i]=(cb[i]+ca[j])%10;
                if(dp[ca[0]][ca[1]][cb[0]][cb[1]]) return;
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            }
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                cb[i]=(cb[i]+ca[j])%10;
                jm(cb,ca);
                dfs(c+1,ca,cb,f/4);
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            }
    }
    else
    {
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                ca[i]=(ca[i]+cb[j])%10;
                if(dp[cb[0]][cb[1]][ca[0]][ca[1]])
                {
                    sum+=f;
                    return; 
                }
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            }
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                ca[i]=(ca[i]+cb[j])%10;
                jm(ca,cb);
                dfs(c+1,ca,cb,f/4);
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            }
    }
}
bool ask(int a[2],int b[2],int deep)
{
    //cout<<a[0]<<' '<<a[1]<<' '<<b[0]<<' '<<b[1]<<' '<<deep%2<<endl;
    if(deep%2&&jm(b,a)) return 1;
    if(deep%2==0&&jm(a,b)) return 0;
    if(deep>8) return 0;
    //if(dp[a[0]][a[1]][b[0]][b[1]]!=-1) return dp[a[0]][a[1]][b[0]][b[1]];
    int ca[2],cb[2],i,j;
    if(deep%2)
    {
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
                ca[i]=(ca[i]+cb[j])%10;
                //jm(ca,cb);
                if(ask(ca,cb,deep+1)==0) return 0;
            }
        return 1;
    }
    else
    {
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
                cb[i]=(cb[i]+ca[j])%10;
               // jm(cb,ca);
               if(ask(ca,cb,deep+1)==1) return 1;   
            }
        return 0;
    }
}
void jfca(int a[2],int b[2])
{
    int ca[2],cb[2],s=0,mx=-1073741825,x,y,i,j;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        {
            ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            ca[i]=(ca[i]+cb[j])%10;
            if(jm(ca,cb))
            {
                a[i]=(a[i]+b[j])%10;
                cout<<i<<' '<<j<<endl;
                return;
            }       
        }
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        {
            ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            ca[i]=(ca[i]+cb[j])%10;
            jm(ca,cb);
            sum=0;
            dfs(0,ca,cb,1073741824);
            if(sum>mx)
            {
                mx=sum;
                x=i,y=j;
            }
        }
    cout<<x<<' '<<y<<endl;
    a[x]=(a[x]+b[y])%10;
}
void init()
{
    memset(dp,-1,sizeof(dp));
    int i,j,k,l,a[2]={6,9},b[2]={0,1},sum=0;
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            for(k=0;k<10;k++)
                for(l=0;l<10;l++)
                {
                    a[0]=i;
                    a[1]=j;
                    b[0]=k;
                    b[1]=l;
                    dp[i][j][k][l]=ask(a,b,1);
                //  sum+=dp[i][j][k][l]==1;
                } 
    //cout<<sum;
}
int main()
{
    init();
    int pl[2],cp[2],P,x,y;
    cin>>pl[0]>>pl[1]>>cp[0]>>cp[1]>>P;
    for(;;)
    {
        jfca(pl,cp),jm(pl,cp);
        if(cin>>x>>y)
        cp[x]=(cp[x]+pl[y])%10,jm(cp,pl);
        else return 0;
    }
}

交互库：

#include"testlib.h"
#include<bits/stdc++.h>
using namespace std;
int w=10;
int sum;
int dp[10][10][10][10];
int lx(int a[2])
{
    int b[2];
    b[0]=a[0],b[1]=a[1];
    if(b[0]>b[1]) swap(b[0],b[1]);
    if(b[0]==3&&b[1]==3||b[0]==3&&b[1]==5||b[0]==1&&b[1]==6) return 1;
    if(b[0]==1&&b[1]==9) return 2;
    if(b[0]==1&&b[1]==5) return -1;
    if(b[0]==5&&b[1]==5) return -2;
    return 0;
}
int jm(int a[2],int b[2])
{
    if(lx(a)<=0) return 0;
    if(lx(a)+lx(b)>0) return 1;
    if(lx(a)==1)
    {
        if(lx(b)==-1) b[0]=b[1]=1;
        else b[0]=5,b[1]=1;
    }
    else b[0]=b[1]=1;
    return 0;
}
void dfs(int c,int a[2],int b[2],int f)
{
    int ca[2],cb[2],i,j;
    ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
    if(c==w) return;
    if(c%2==0) 
    {
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                cb[i]=(cb[i]+ca[j])%10;
                if(dp[ca[0]][ca[1]][cb[0]][cb[1]]) return;
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            }
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                cb[i]=(cb[i]+ca[j])%10;
                jm(cb,ca);
                dfs(c+1,ca,cb,f/4);
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            }
    }
    else
    {
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                ca[i]=(ca[i]+cb[j])%10;
                if(dp[cb[0]][cb[1]][ca[0]][ca[1]])
                {
                    sum+=f;
                    return; 
                }
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            }
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                ca[i]=(ca[i]+cb[j])%10;
                jm(ca,cb);
                dfs(c+1,ca,cb,f/4);
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            }
    }
}
bool ask(int a[2],int b[2],int deep)
{
    //cout<<a[0]<<' '<<a[1]<<' '<<b[0]<<' '<<b[1]<<' '<<deep%2<<endl;
    if(deep%2&&jm(b,a)) return 1;
    if(deep%2==0&&jm(a,b)) return 0;
    if(deep>w) return 0;
    //if(dp[a[0]][a[1]][b[0]][b[1]]!=-1) return dp[a[0]][a[1]][b[0]][b[1]];
    int ca[2],cb[2],i,j;
    if(deep%2)
    {
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
                ca[i]=(ca[i]+cb[j])%10;
                //jm(ca,cb);
                if(ask(ca,cb,deep+1)==0) return 0;
            }
        return 1;
    }
    else
    {
        for(i=0;i<2;i++)
            for(j=0;j<2;j++)
            {
                ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
                cb[i]=(cb[i]+ca[j])%10;
               // jm(cb,ca);
               if(ask(ca,cb,deep+1)==1) return 1;   
            }
        return 0;
    }
}
unsigned seed=26535;
int rndkkk()
{
    return seed=seed*114514+1919810;
}
void jfca(int a[2],int b[2])
{
    int ca[2],cb[2],s=0,mx=-1073741825,x,y,i,j;
    if(w==2)
    {
        x=rndkkk()%2;
        y=rndkkk()%2;
        goto bre;
    }
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        {
            ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            ca[i]=(ca[i]+cb[j])%10;
            if(jm(ca,cb))
            {
                a[i]=(a[i]+b[j])%10;
                cout<<i<<' '<<j<<endl;
                cout.flush();
                return;
            }       
        }
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        {
            ca[0]=a[0],ca[1]=a[1],cb[0]=b[0],cb[1]=b[1];
            ca[i]=(ca[i]+cb[j])%10;
            jm(ca,cb);
            sum=0;
            dfs(0,ca,cb,1073741824);
            if(sum>mx)
            {
                mx=sum;
                x=i,y=j;
            }
        }
    bre:;
    cout<<x<<' '<<y<<endl;
    cout.flush();
    a[x]=(a[x]+b[y])%10;
}
void init()
{
    memset(dp,-1,sizeof(dp));
    int i,j,k,l,a[2]={6,9},b[2]={0,1},sum=0;
    for(i=0;i<10;i++)
        for(j=0;j<10;j++)
            for(k=0;k<10;k++)
                for(l=0;l<10;l++)
                {
                    a[0]=i;
                    a[1]=j;
                    b[0]=k;
                    b[1]=l;
                    dp[i][j][k][l]=ask(a,b,1);
                //  sum+=dp[i][j][k][l]==1;
                } 
    //cout<<sum;
}
int main(int argc,char* argv[])
{
    registerInteraction(argc,argv);
    init();
    int pl[2],cp[2],P,st=0,x,y;
    pl[0]=inf.readInt();
    pl[1]=inf.readInt();
    cp[0]=inf.readInt();
    cp[1]=inf.readInt();
    P=inf.readInt();
    cout.flush();
    cout<<pl[0]<<' '<<pl[1]<<' '<<cp[0]<<' '<<cp[1]<<' '<<P<<endl;
    cout.flush();
    w=P;
    for(;st<100;st++)
    {
        x=ouf.readInt(0,1);
        y=ouf.readInt(0,1);
        cout.flush();
        pl[x]=(pl[x]+cp[y])%10;
        if(jm(pl,cp))
        {
            quitf(_ok,"Win on step %d!",st);
            return 0;
        }
        jfca(cp,pl);
        if(jm(cp,pl))
        {
            quitp(st/10*10/100.0,"Lose on step %d.",st);
            return 0; 
        }
    }
    quitf(_ok,"Keep for at least 100 steps.");
    return 0;
}