NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. HINT
  • 题解
    1. 0.1. Step1:
    2. 0.2. Step2:
      1. 0.2.1. 感性证明
  • Description

    有一个古老的游戏叫做Green Hackenbush,游戏是这样进行的:两个人轮流在一棵树上删边,每次删边后不与根联通的子树直接被ignore,不能删边的游戏者输。Alice和Bob也在玩这个游戏,不过他们面对的是n棵树,第i棵树是含有a[i]个节点的二叉树。先手的Alice想知道自己有多大的概率获胜(假设我们的Alice和Bob同学都是无限聪明的)。

    Input

    第一行一个数n。
    接下来每行一个数a[i]。

    Output

    一个保留6位小数的实数ans。

    Sample Input

    1
    2
    1
    2

    Sample Output

    1
    1.000000

    HINT

    对于100%的数据,n<=100,a[i]<=100

    题解

    首先我们考虑正常的Green Hackenbush游戏

    Step1:

    让我们先从最简单的开始
    假设树退化为一条链
    那么我们会发现这好像就是一个Nim游戏
    那么我们可以通过异或来解决这个问题

    Step2:

    再让我们考虑一颗树
    那么根据Colon Principle原理
    一个点的SG函数值为它的所有的子树的SG+1的异或和
    举个例子
    从网上找的一张图

    1344074319_7883.jpg
    大家可以自己算一下

    感性证明

    首先不考虑这个点以下的部分(我们一会再去管他) , 在这个点以上的部分先不考虑链接这个点的那些边。
    那么他上面可以看做是几个子游戏。 我们可以递归的计算他们是SG值
    把他们等效成一条链, 然后加上链接这个点的那些边, 及SG+1
    根据Nim 的结论, 我们可以将他们异或起来。


    现在让我们考虑下面的部分
    假设一个任意固定的图G,一个任意节点x,让H1和H2为任意的树,且拥有相同的SG值。考虑这样两个图G1=Gx:H1和G2=Gx:H2,Gx:Hi表示该图是把树Hi连接图的x节点。
    则我们需要证明G1与G2的SG值相等
    G1、G2拥有相同的SG值意味着两个游戏的总SG值为0,G1+G2的和是一个P局面,也就是必败
    先手一旦在其中一幅图中取走任意一条边,后手即可在另一幅图中取走相对应的一条边。轮流下去,最后肯定是后手获胜。

    然后我们搞定了正常的Green Hackenbush游戏

    现在让我们来看这道题
    对应$x$个点去建一颗二叉树有多少种方法?
    分别考虑左右子树
    我们有
    $$h[x] = \sum_{i = 0}^{n - 1}{h[i] * h[n - i - 1]}$$
    这好像就是卡特兰数。
    然后我们设$g[i][j]$为有$i$个点的树SG值为$j$的概率

    得DP方程为

    $$g[n][(x + 1) ^ (y + 1)] = \sum_{i = 0}^{n - 1}{ h[i] * g[i][x] * h[n - 1 - i] * g[n - 1 - i][y]}$$

    f[i][j]表示的是前i颗子树异或值为j的概率

    $$f[i][j ^ k]=f[i-1][j] * g[a[i]][k]$$

    搞定
    $ans = 1-f[n][0]$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    inline int read()
    {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }
    int a[105];
    double h[150];
    double g[350][350], f[350][350];
    int main()
    {
    int n = read(), m = 0;
    for (int i = 1; i <= n; i++)
    a[i] = read(), m = max(m, a[i]);
    h[0] = 1;
    for (int i = 1; i <= m; i++)
    h[i] = h[i - 1] * (4 * i - 2) / (i + 1);
    g[1][0] = 1;
    for (int i = 2; i <= m; i++)
    {
    for (int j = 0; j <= 127; j++) g[i][j + 1] += h[i - 1] * 2 * g[i - 1][j];
    for (int j = 1; j < i - 1; j++)
    {
    int k = i - j - 1;
    for (int x = 0; x <= 127; x++)
    for (int y = 0; y <= 127; y++)
    g[i][(x + 1) ^ (y + 1)] += h[j] * g[j][x] * h[k] * g[k][y];
    }
    for (int j = 0; j <= n - 1; j++) g[i][j] /= h[i];
    }
    for (int i = 0; i <= 127; i++) f[1][i] = g[a[1]][i];
    for (int i = 2; i <= n; i++)
    for (int j = 0; j <= 127; j++)
    for (int k = 0; k <= 127; k++)
    f[i][j ^ k] += f[i - 1][j] * g[a[i]][k];
    printf ("%.6f\n", 1.0 - f[n][0]);
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2018/01/18/125/

    本文最后更新于 天前,文中所描述的信息可能已发生改变