P4279 [SHOI2008]小约翰的游戏 题解


以下题解仅供学习参考使用。

抄袭、复制题解,以达到刷AC率/AC数量或其他目的的行为,在洛谷是严格禁止的。

洛谷非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看洛谷社区规则

评论

  • 还没有评论
作者: SuperJvRuo 更新时间: 2018-03-13 11:43  在Ta的博客查看 举报    5  

显然,奇数个1是必败态。我们应该想办法把局面转换成这种必败态。

当“超过1颗石子”的堆数大于1的时候,按照Nim的方法走。直到“超过1颗石子”的堆数等于1,这时将这堆石子全部取掉或剩1颗,保证非空(剩下1颗石子)的堆数为奇数即可胜利。

#include<cstdio>
int main()
{
    int a,t,N;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&N);
        int ans=0,sum=0;
        for(int i=0;i<N;i++)
        {
            scanf("%d",&a);
            ans^=a;
            sum+=a;
        }
        if(sum==N)
        {
            printf("%s\n",sum&1?"Brother":"John");
        }
        else
        {
            if(ans)
                printf("John\n");
            else
                printf("Brother\n");
        }
    }
    return 0;
}

评论

  • ButterflyDew
    够严谨,不过“第二种情况呢”后面一段应该是存在一个SG(T)=0的T吧
  • Lskkkno1
    Orz
  • GNAQ
    Dew 说的是对的……我懒得改了,大家注意下
作者: GNAQ 更新时间: 2018-12-12 21:03  在Ta的博客查看 举报    3  

本文首发于 随便搞搞 ICG (公平组合游戏) 和其余的博弈 (第五页) 欢迎围观

扩展 SG 博弈 - Anti-SG

简单的 Anti-Nim 游戏

我们定义 Anti-Nim 游戏:

有 $n$ 堆石子,双方轮流取石子。

  • 每次能从其中一堆取出任意数目的石子,不能不取。

  • 取走最后一颗石子者败。

不管别的我们先定义:

如果某堆中只有 $1$ 个石子,则称为孤单堆,否则称为充裕堆。

直接给出结论:先手必胜当且仅当

  • 只有偶数个孤单堆;

  • 存在充裕堆且游戏的 $\mathrm{SG}$ 值不为 $0$ 。

那么接下来要证明结论:

首先第一种情况比较显然,每人每次能做的操作只有拿走一堆石子。

第二种情况呢?

首先考虑当存在多于一个充裕堆时的情况,设当前的局面为 $\mathrm{S}$ ,这时从结论可知 $\mathrm{SG} \ne 0$ ,那么根据 $\mathrm{SG}$ 函数的定义, $ \exists \mathrm{T} \text{ s.t. } \mathrm{S} \rightarrow \mathrm{T} \,,\, \mathrm{SG(T)} \ne 0 $ 。

那么先手让 $\mathrm{S}$ 变为 $\mathrm{T}$ 即可。( 又因为每次只能操作一堆,比较显然地, $\mathrm{T}$ 中一定存在充裕堆。 )

如果当前局面里只有一堆充裕堆,首先根据 Nim 的异或判定方法,显然此时的 $\mathrm{SG}$ 值不会为 $0$ ,其次,先手总可以把状态变为只有奇数个孤单堆,所以先手必胜。

另外我们还必须说明当存在充裕堆且 $\mathrm{SG}$ 为 $0$ 的时候是先手必败的,那么:

首先至少存在两堆充裕堆。因为按照 Nim 的异或判定方法,充裕堆会影响异或和的高位。所以必然有两堆以上的充裕堆使得高位异或和为 $0$ 。

那么无论先手如何决策, $\mathrm{T}$ 中必然存在一堆以上的充裕堆,根据上文可知此时另一位玩家必胜。

更加复杂的结论 - Anti-SG

给出 Anti-SG 游戏的定义:

  • Anti-SG 游戏规定,决策集合为 $\oslash$ 的游戏者赢。

  • Anti-SG 游戏其他规则与 SG 游戏相同。

对于 Anti-SG 游戏,我们也是先给出定理,再尝试证明。那么这次的定理名字叫做 Sprague Grundy - Jia Zhihao 定理,简称 SJ 定理,它说的是:

对于任意一个 Anti-SG 游戏,如果规定当局面中所有单一游戏的 $\mathrm{SG}$ 值都为 $0$ 时游戏结束,那么先手必胜当且仅当:

  1. 游戏的 $\mathrm{SG}$ 不为 $0$ 且 $\exists G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) > 1 $ 。

  2. 游戏的 $\mathrm{SG} = 0 $ 且 $\forall G_i \in \mathbb{G} \,,\, \mathrm{SG}(G_i) \leqslant 1 $ 。 证明:

我们还是只需要证明以下三点:

Anti-SG 的结束局面为 P-position ; 能转移到 P-position 的局面是 N-position ; 所有合法转移都是 N-position 的局面是 P-position 。 那么我们设当前的局面为 $\mathrm{S}$ ,证明如下:

[1] 局面的 $\mathrm{SG} = 0 $ 且 $\exists G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) > 1 $ 。 首先由 SG 定理我们可以知道的是此时存在至少两个单一游戏,他们的 $\mathrm{SG} > 1$ ;

又因为每次只能对一个单一游戏操作,那么$\forall \mathrm{T} \in N(\mathrm{S}) $ , $\mathrm{T} $ 中存在至少一个单一游戏其 $\mathrm{SG} > 1 $ 。

然后根据 SG 函数的性质, $\forall \mathrm{T} \in N(\mathrm{S}) \,,\, \mathrm{SG(T)} \ne 0 $ 。

所以我们证明了在先手的任意操作之后,局面都转移至 SJ 定理中的 $(1)$ ,先手必败。

[2] 局面的 $\mathrm{SG} \ne 0 $ 且 $\forall G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) \leqslant 1$ 。 根据 SG 定理,显然只有奇数个单一游戏其 $\mathrm{SG} =1 $ 且其余单一游戏的 $\mathrm{SG} =0 $ 。

首先,如果将某个单一游戏的 $\mathrm{SG}$ 值改为大于 $1$ 的数,我们可知

游戏的 $\mathrm{SG} \ne 0$ 。 有且仅有一个单一游戏其 $\mathrm{SG} > 1$ 在先手操作之后,游戏转移至 SJ 定理中的 $(1)$ ,先手必败。

其次,将某个单一游戏的 $\mathrm{SG}$ 值改为 $0$ 或 $1$ :

仅有偶数个单一游戏其 $\mathrm{SG} = 1$ ,且其余的单一游戏其 $\mathrm{SG} =0$ ,既局面的 $\mathrm{SG} = 0$ ; 对于所有的单一游戏其 $\mathrm{SG} \leqslant 1$ 。 在先手的任意操作操作之后,局面都转移至 SJ 定理中的 $(2)$ ,先手必败。

[3] 局面的 $\mathrm{SG} \ne 0 $ 且 $\exists G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) > 1 $ 。  首先,如果只有一个单一游戏其 $\mathrm{SG} > 1$ :

先手选择更改此单一游戏,选择将其更改为 $\mathrm{SG} = 0$ 或 $\mathrm{SG} = 1 $ 的单一游戏,使得局面中有只有奇数个 $\mathrm{SG} = 1$ 的单一游戏。

此时 (操作完成后) 根据 SG 函数的定义,为 P-position 。所以先手必胜。

其次,如果有超过一个单一游戏其 $\mathrm{SG} > 1$ :

根据 SG 函数的性质, $\exists \mathrm{T} \in N(\mathrm{S}) \text{ s.t. } \mathrm{SG(T)} = 0$ ;

因为每次最多对一个单一游戏操作,所以 $\exists G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) > 1 $ 。

此时 (操作完成后) 情况到了刚刚讨论过的 [1] , 所以先手必胜。

[4] 局面的 $\mathrm{SG} = 0 $ 且 $\forall G_i \in \mathbb{G} \text{ s.t. } \mathrm{SG}(G_i) \leqslant 1$ 。 首先如果 $\forall G_i \in \mathbb{G} \,,\, \mathrm{SG}(G_i) = 0 $ ,那么游戏结束了,先手必胜。

其次显然局面中有偶数个 $\mathrm{SG} = 0 $ 的单一游戏。先手选择任一将其 $\mathrm{SG}$ 变为 $0$ ,那么游戏出现奇数个 $\mathrm{SG} = 1 $ 的单一游戏,为 P-positon , 先手必胜。

综上, SJ 定理证毕。


于是这题目就是板题了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define ll long long
using namespace std;

int T,n,seq[5010],ans;

template<typename int_t>
void readx(int_t& x)
{
    x=0; int_t k=1; char ch=0;
    while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    x*=k;
}

int main()
{
    readx(T);
    while (T--)
    {
        readx(n);
        for (int i=1;i<=n;i++) readx(seq[i]);
        int lonely=0,full=0; ans=0;
        for (int i=1;i<=n;i++) 
        {
            if (seq[i]==1) lonely++;
            else full++;
            ans^=seq[i];
        }
        if (!full)
        {
            if (lonely%2) printf("Brother\n");
            else printf("John\n");
        }
        else
        {
            if (!ans) printf("Brother\n");
            else printf("John\n");
        }
    }
}

评论

  • bztMinamoto
    gtx太强啦%%%
作者: YWZX__GTX 更新时间: 2018-11-18 16:10  在Ta的博客查看 举报    1  

一道博弈论的入门题吧

首先说说博弈论是什么:

博弈论又被称为对策论(Game Theory),既是现代数学的一个新分支,也是运筹学的一个重要学科。 博弈论主要研究公式化了的激励结构间的相互作用,是研究具有斗争或竞争性质现象的数学理论和方法。 博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。(以上摘自百度百科)

其中,博弈论最经典的题目就是取石子问题啦,而本题则又是一道基础的取石子题目

题目大意

两个人在n堆石子中轮流取,每次最少一个,最多取完这堆,取走最后一颗石子的人为负,问谁会胜利

如果不知道博弈论的人,估计深搜啊什么神奇的东西弄一弄,也就弄不出来的(不排除某些大佬)。实际上我们判断胜负只需要判断能否达到必胜态(必败态),然后逐渐往这两个状态去靠近,直到达到某个状态,判定出胜负为止。

在本题,关于必胜态和必败态有两个结论

John必胜:a1^a2^......^an=1

John必败:a1^a2^.......^an!=0

一般只需要知道这两个公式再加上特判就可以轻松做出本题啦

代码

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();}
    return flag?-x:x;
}
int t=read(),n,ans,flag;
int main()
{
    while(t--)
    {
        n=read(),flag=1,ans=0;
        for(int i=1;i<=n;++i) 
        {
            int x=read();
            if(x!=1) flag=0;
            ans^=x;
        }
        if(flag) if(n&1) printf("Brother\n");else printf("John\n");
        else if(ans) printf("John\n");else printf("Brother\n");
    }
}

但是我们学习不能只是为了切掉某一题,那么我下面给出证明:

对于某个局面(a1,a2,...,an),若a1^a2^...^an!=0,一定存在某个合法的移动,将ai改变成aii后满足a1^a2^...^ai'^...^an=0。不妨设a1^a2^...^an=x,则一定存在某个ai使得ai^x<ai一定成立。则如果我们可以将ai改变成aii=ai^x,此时a1^a2^...^aii^...^an=a1^a2^...^an^x=0。

对于某个局面(a1,a2,...,an),若a1^a2^...^an=0,一定不存在某个合法的移动,将ai改变成aii后满足a1^a2^...^ai'^...^an=0。因为异或运算性质,由a1^a2^...^an=a1^a2^...^aii^...^an可以得到ai=aii。所以将ai改变成aii不是一个合法的移动

所以在这道题中如果当前是必胜的话,那么就要下一个移动的人必败,所以就要改变一个ai变成aii使得原本的a1^...ai^...^an!=0变成a1^...aii...^an=0

证明完毕

呃我差不多讲完了,如果对于博弈论还想有更多了解的话,我推荐下面几个博客(不是我的)

斐波那契博弈(Fibonacci Nim)

威佐夫博弈

稍微综合版博弈论

以上的博客都是我随便找的,才不是因为我自己没写过博弈论的博客

评论

  • 还没有评论
作者: Ark_ 更新时间: 2019-03-18 12:00  在Ta的博客查看 举报    0  

题意

反Nim游戏,两人轮流选一堆石子拿,拿到最后一个的输.问先手是否必胜.

分析

怎么说,分类讨论?

  • 情形1:首先考虑最简单的情况,所有石子数都为1.那么奇数堆石子为必败,偶数为必胜

  • 情形2:然后考虑只有一堆石子>1.那么先手一定可以通过拿完这一堆石子或者是留下一个石子,使得剩下的全部是1.而这两种操作后的局面一种是奇数个1,一种是偶数个1.所以先手一定可以留给后手奇数个1的局面,从而让后手必败,先手必胜.

  • 情形3:那么如果有多堆石子>1呢?可以发现,不管怎么拿,因为石子数在减少,一定会有某个人在某个时刻面临情况2(只有一堆石子大于1),那么他就必胜了.那我们来看看这种情况有什么特征.

    于是这就是常见的Nim游戏套路,将所有石子数异或起来后,情形2得到的值一定>0.因为>1的那一堆石子在二进制中除去末位一定还至少有一个1.所以说这时只要异或和>0就表示必胜.

    由于异或和为0的情况任意取都会变成异或和>0的情况,而异或和>0的情况一定有一种取石子方案使得异或和为0.那么异或和为0就表示了必败状态,而>0就表示必胜状态.

所以这道题首先特判一下情形1,然后只用异或起来看等不等于0就行了.

(我在想Anti-SG是不是可以看作两个人都希望对方赢而斗智斗勇的普通SG...)

CODE

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>void read(T &num) {
    char ch; int flg=1;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
    num*=flg;
}
int n, x;
int main() {
    int T; read(T);
    while(T--) {
        read(n);
        int ans = 0, sum = 0;
        for(int i = 1; i <= n; ++i) {
            read(x), ans ^= x;
            sum += (x==1);
        }
        if(sum == n) puts((n&1) ? "Brother" : "John");
        else puts(ans ? "John" : "Brother");
    }
}

评论

  • 还没有评论
作者: DQYdqy 更新时间: 2019-01-03 21:06  在Ta的博客查看 举报    0  

dalao们讲的都太数学了,蒟蒻表示自己真的是太弱了

安利一发博客:ヾ(≧∇≦*)ゝ

Solution

在普通的Nim游戏当中,若各堆石子数异或和不为0,则先手必胜

然而在本题中,取走最后的那颗石子人输

我们来分情况讨论

1.若当前每堆石子数都为1,且石子堆数为奇数,则先手必败,为偶数,先手必胜

2.若某一堆石子数>1且各堆石子异或和不为0,则先手必胜

为什么呢?(~不知道......) 我们来推导一下

结论1是很显然的,我们就不再做出赘述,如何来证明结论2呢

根据普通的Nim游戏可以知道,在先手必胜的情况下,总是有某种策略可以让局势重新转换为先手必胜的局势(先后手在不断变换),而先手必败的局势是只能通向先手必胜的。

又由于我是先手,则在双方都采取先手必胜->先手必胜的策略的情况下,最后输的总是我。

那么转换到本题,在满足2条件的情况下,最后赢得肯定是我。

得证。

Code:

#include<bits/stdc++.h>
#define N 101
using namespace std;
int n,a[N];
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    int Case=read();
    begin:Case--;
    if(Case<0)return 0;
    n=read();memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++){
        a[i]=read();
        a[0]^=a[i];
    }
    sort(a+1,a+n+1);
    if((a[n]==1&&!a[0])||(a[0]&&a[n]>1))puts("John");
    else puts("Brother");
    goto begin;
}
 
反馈
如果你认为某个题解有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。