SAST软研2018招新题 选作部分第8题 解答

题目是这样的。

张老板和乔波最近迷上了女装,可是竹席团只买了一件女装。于是他们准备玩一个游戏,谁赢就能拿那件女装。
大活101目前共有n个瓶子,乔波已经提前贴上了编号1~n。现在,每个瓶子里的石子数量已知,张老板和乔波两个人轮流取石子。每一轮每人首先选择瓶子a,取走其中的一颗石子,随后另外选择两个瓶子b、c各放入一颗石子。当然,在操作的时候必须保证 a < b , b ≤ c,并且取之前a瓶子里至少有一颗石子。如果轮到某人而他无法按规则取石子,那么他将输掉比赛。另一方就算胜利啦。
两人抛硬币后,决定由张老板先取石子。为了能够得到最终的女装,张老板自然希望赢得比赛获得女装,所以他和乔波也都会做出最优决策。张老板思索片刻,发现好像在有的情况下,先拿石子的人一定有办法取胜,但是他不知道对于其他情况是否有必胜策略,更不知道第一步该如何取。
张老板很想女装。他想知道,在给定每个瓶子中的最初石子数后,是否能让自己得到竹席团的女装。他还想知道,为了能必胜,第一步能有多少种取法。
(1)假如有3个瓶子,里面分别有0个,0个,1个石子,请问答案是?
(2)假如有4个瓶子,里面分别有1个,0个,1个,5000个石子,请问答案是?
(3)对于其他情况呢,聪明睿智兼具颜值情商而又不失沉稳端庄的你,有没有什么思路呢?说一说你的思路,或者试着用代码实现一下吧。不然乔波就要把张老板的女装给抢走了哟~

题目理解上出了一些偏差,abc表示的是瓶子编号,然后“分别”就是说,第一个瓶子里多少……第二个多少……第三个多少……

Solution 0.1
没有可行的情况 methods=0

Solution 0.2
a=1 b=3 c=4 methods=1

Solution 0.3
这里只要枚举讨论一些必胜态我们就给分了,这题评分很宽松的,所以我们最后这问有两个人得了2分……三四个人得了1分……

这题其实一个Nim博弈,首先,我们发现当石子个数为偶数的时候后手可以把先手抵消掉。

这样的话整个游戏实际就变成了一串01序列,瓶子的状态只和奇偶有关。然后考虑本题,实际上就是一个Multi-Nim。

因为处理的时候需要用到后面的SG函数,所以用记忆化搜索。

以上是判断我能不能拿到女装,关于第一步输出方案的话,只要暴力枚举第一个的位置,然后用异或的性质判断一下,即ans^SG[i]^SG[j]^SG[k]==0,此时会留给对手必败局势。

#include<bits\stdc++.h>

const int MAXN=1001;

inline char nc()
{
    static char buf[MAXN*100],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN*100,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}

int N,S[MAXN],SG[MAXN];
int a[MAXN];

int dfs(int now)
{
    if(SG[now]!=-1) return SG[now];
    memset(S,0,sizeof(S));
    for(int i=now+1;i<=N;i++)
        for(int j=i;j<=N;j++)
            S[ (dfs(i)^dfs(j)) ] = 1;
    for(int i=0;;i++) if(!S[i]) {SG[now]=i;break;}
    return SG[now];
} 

int main()
{
    memset(SG,-1,sizeof(SG));
    N=read();
    for(int i=1;i<=N;i++) a[i]=read();
    for(int i=1;i<=N;i++) if(a[i]&1) dfs(i);    
    int ans=0,tot=0;
    for(int i=1;i<=N;i++) if(a[i]&1)ans=(ans^dfs(i));
    for(int i=1;i<=N;i++)
    {
        for(int j=i+1;j<=N;j++)
        {
            for(int k=j;k<=N;k++)
            {
                if( (ans^dfs(i)^dfs(j)^dfs(k) )!=0) continue;
                tot++;
                if(tot==1) printf("a=%d b=%d c=%d\n",i,j,k);
            }
        }
    }
    if(tot==0) printf("无解\n");
    else printf("%d个解\n",tot);
    return 0;
}

只有 1 条评论, 不如再加一个评论?

留下你的评论呗...

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