@dxbdly 2021-03-03T14:46:57.000000Z 字数 4463 阅读 261

G2020 19寒假集训Day2

信息学——19寒假集训

G2020 19寒假集训Day2

今天是G2020寒假集训Day2，主要学习博弈论,并且是组合游戏型。

一.组合游戏

组合游戏满足以下特点：

1.必须是两个人轮流来。
2.一个局面的下一步能到达的状态必须只跟局面本身有关。
3.玩家之间没有差别。
4.可以在有限步内结束。
5.不能操作的人为败者。

二.必胜点与必败点

解决组合游戏问题时，我们常常将问题抽象成图。

对于一个组合游戏，我们可以将它抽象成一个有向无环图(DAG)。

图上的点对应游戏中的状态，边对应一个状态到另一个状态的合法操作。

而这张图有一个特殊的性质：

图中的点要么为必胜点(又称P点，即走到这个状态的人必胜）
要么为必败点（又称N点，即走到这个状态的人必败）

（PS：以下均简写为P点，N点）

P点与N点满足以下性质：

1所有的终结点都是必败点
2.从任何P点操作，至少有一种方式进入N点
3.无论如何操作， 从N点都只能进入P点.

如果我们能将所有必胜点与必败点求出，即可轻易得出答案。

三. $SG$ 函数

刚才讲到如果我们能确定出必胜点与必败点，即可轻易得出答案。

但有些题模型复杂，操作繁琐，这时便很难直接分析题目得到必胜，必败点。

所以我们必须引进一种非常强大 ~~(恶心)~~ 的东西—— $SG$ 函数

先给出两个定义：

Nim和： 所有数的异或和。
mex(minimal excludant)运算：这是一个集合运算，表示最小的不属于当前集合的非负整数。

接下来，我们好好分析以下 $SG$ 函数

$1^o$ 定义与本质

SG函数的定义：

对于任意状态 x ， 定义 SG(x) = mex(S),其中 S是 x 后继状态的SG函数值的集合。

emmm……是不是感觉有点懵

下面我们来分析一下 $SG$ 函数的本质。

刚才讲过了 $SG$ 函数是用来求P点，N点的,换句话说，他其实是P点，N点的另一种表示形式。

所以说 $SG$ 函数会满足P点，N点的所有性质

我们可以注意到关于P点，N点的这两条性质

1.从任何P点操作，至少有一种方式进入N点
2.无论如何操作， 从N点都只能进入P点.

再对比一下这句话：

定义 SG(x) = mex(S),其中 S是 x 后继状态的SG函数值的集合。

你会发现：

所谓x 后继状态的SG函数值的集合其实就是节点x所连向的所有出点！
又由P点，N点性质可得：
SG(x) = mex(S)其实就是从终结点逆推，将所有P点，N点求出的递推式！

当 $SG(x)>0$ 时为P点，当 $SG(x)=0$ 时为N点。

求出 $SG$ 函数，就能得到原问题的解。

$2^o$ SG函数求法

递推方程： $SG(x)=mex(S)$ 是求 $SG$ 函数的通解，在此方程中，最重要的是 $mex(S)$ 这个运算如何求解。

由于此递推方程是逆推，我们一般将其转换为顺推求解

即将图反向，且求解顺序颠倒，原来是最终状态--->初始状态，变为初始状态--->最终状态。

那么对于求解每一个 $SG(x)$ 时，我们开一个标记数组，标记状态 $1$ ~ $x-1$ 到状态 $x$ 的转移方式（游戏的操作）。

然后找到第一个没被标记的点即可。
模板代码：

inline void get_SG()
{
//  sg[1]必为N点，初值为0，不用考虑
//  f[]为标记数组
    for (register int i=2;i<=n;++i)
        {
        memset(f,0,sizeof(f));
        for (register int j=1;j<i;++j)              
                f[j->i的转移操作]=1;
        for (register int j=0;;++j)
            if (!f[j])
               {
               sg[i]=j;
               break;
               }
        }
}

$3^o$ SG定理

对于某一些较为复杂，不好确定 $SG$ 函数的题目：

我们可以尝试采用分治思想：
将游戏分解为多个类似的子游戏
通过计算子游戏的SG函数，来推出原题的SG函数。

SG定理就是用来解决如何由子游戏的 $SG$ 函数推出原题的 $SG$ 函数。

定理内容：

题目所求游戏的SG函数等于各个子游戏SG函数的Nim和(异或和)。

有了这一定理，我们便能将原问题分解为多个子问题，然后分而治之，将原问题简化。

PS：将原问题划分为子问题时，子问题必须要相似且独立

四.例题

$1^o$ P2197 【模板】nim游戏

题面

解法：

一共有n堆石子，不好处理，我们将每一堆石子看作一个子游戏

我们容易得到子游戏的 $SG$ 函数： $SG(x)=x$ ，由此可推出全局 $SG$ 函数。

AC代码:

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int t,n,ans;
int main(){
    t=read();
    while (t--)
          {
          ans=0,n=read();
          for (register int i=1;i<=n;++i)
              {
              int x=read();
              ans^=x;
              }
          ans?printf("Yes\n"):printf("No\n");
          }
    return 0;
}

$2^o$ P3185 [HNOI2007]分裂游戏

题面

此题显然需要划分子游戏，利用 $SG$ 函数处理。

我们从最终状态出发，发现最终状态一定是所有糖果都在最后一个花瓶内

接下来划分子游戏

在划分子游戏时存在一种常见的错误划分方法：

以每个瓶子为一个子游戏。
错误在哪呢？
我们会发现，此题的转移方式是在三个瓶子中进行的
也就是说，当前这个子游戏会受到其他子游戏的影响！
所以说此划分方法不满足子问题的独立性！！！

正确的划分方法为：每个糖果为一个子游戏。

则题目转化为：

将这个糖果从第i个位置移动到第n个位置，其实也就是一堆个数为n−i的石子等你来取。

则可以使用 $SG$ 函数求解。

此题还要求第一步如何走，利用异或的逆运算可知：

设：全局SG值为ans
则若三个瓶子i,j,k为第一步
则满足
ans^sg(n-i+1)^sg(n-j+1)^sg(n-k+1)=0

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int t,n;
int a[25],sg[25];
int ans,tot;
bool f[10005];
inline void get_SG()
{
    for (register int i=2;i<=21;++i)
        {
        memset(f,0,sizeof(f));
        for (register int j=1;j<i;++j)
            for (register int k=j;k<i;++k)
                f[sg[j]^sg[k]]=1;
        for (register int j=0;;++j)
            if (!f[j])
               {
               sg[i]=j;
               break;              
               }
        }
}
int main(){
    t=read();
    get_SG();
    while (t--)
          {
          n=read();
          ans=tot=0;
          for (register int i=1;i<=n;++i)
              {
              a[i]=read();
              if (a[i]&1)
                 ans^=sg[n-i+1];
              }
          for (register int i=1;i<=n;++i)
              for (register int j=i+1;j<=n;++j)
                  for (register int k=j;k<=n;++k)
                      if (!(ans^sg[n-i+1]^sg[n-j+1]^sg[n-k+1])) 
                         {
                         tot++;
                         if (tot==1)
                            printf("%d %d %d\n",i-1,j-1,k-1);
                         }
          !tot?printf("-1 -1 -1\n0\n"):printf("%d\n",tot);
          }
    return 0;
}

$3^o$ P3480 [POI2009]KAM-Pebbles

题面

此题需要先对题目本身进行分析,将原问题转化，并得出一些性质

再根据性质划分子游戏，使用 $SG$ 函数解决

题目有如下限制条件。

每堆石子个数都不少于前一堆的石子个数

可以将其转化为：

任意一堆石子个数-前一堆石子个数>=0

题目的操作方式为：

两人轮流操作每次操作可以从一堆石子中移走任意多石子。

思考拿走石子之后的变化会发现：

拿走x个石子后，当前堆与后一堆石子之差增加x

所以可将操作对象从每一堆石子变为两堆石子的差

即限制与操作可转化为：

限制：n个差(包含1到0)均>=0
操作：将第i个差取出x个，放到第i+1个差中

分析此题性质：

可以发现必胜策略只跟奇数堆有关，与偶数堆无关(可手推)

则限制与操作进一步转化为：

限制：所有差均>=0
操作：将第i个差取出x个石子

所以我们会发现，现在就是我们最开始分析的Nim游戏！！！

所以可以直接用 $SG$ 函数解决！

通过对题目的不断转换，以及对性质的挖掘，我们成功将此题变成了我们最熟悉的Nim游戏。

而此题的模型就是Nim游戏的变形：阶梯Nim游戏

更多的Nim游戏变形推荐洛谷日报

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int t;
int a[1005],ans,cha[1005];
int main(){
    t=read();
    while (t--) 
          {
          ans=0;
          int n=read();
          for (register int i=1;i<=n;++i)
              a[i]=read();
          for (register int i=1;i<=n;++i)
              cha[i]=a[i]-a[i-1];
          for (register int i=n;i>=1;i-=2)
              ans^=cha[i];
          ans?printf("TAK\n"):printf("NIE\n");
          }
    return 0;
}

五.总结

要想独立的解决 $SG$ 函数的博弈论题，需要时刻记住以下几个关键:

1.SG函数的本质(P，N点表达方式）
2.对于原题目不断进行转化以及推导性质
3.将原问题正确的划分为子问题（相似性，独立性）
4.对于所有子问题使用SG函数
5.将所有SG函数合并，得到原问题的解，并根据题目特殊要求特殊处理。

G2020 19寒假集训Day2

一.组合游戏

二.必胜点与必败点

三. SG函数

1^o定义与本质

2^oSG函数求法

3^oSG定理

四.例题

1^o P2197 【模板】nim游戏

2^o P3185 [HNOI2007]分裂游戏

3^o P3480 [POI2009]KAM-Pebbles