bzoj 2688: Green Hackenbush （概率DP+博弈）

2688: Green Hackenbush

Time Limit: 10 Sec   Memory Limit: 128 MB Submit: 39   Solved: 14 [ Submit][ Status][ Discuss]

Description

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

Input

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

Output

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

Sample Input

1 2

Sample Output

1.000000

HINT

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

Source

CodeCraft09

[ Submit][ Status][ Discuss]

题解：概率DP+博弈

树形删边博弈：一棵树的异或值等于他所有（子节点的异或值+1）的异或和。那么对于一片森林来说，异或值就是所有树的异或和。如果异或和为0，那么先手必败，否则先手必胜。

我们考虑一颗i个节点的二叉树有多少种形态，左右子树分开考虑。

h[n]=sigma(i=0..n-1)h[i]*h[n-i-1] 如果对于卡特兰数够熟悉的话，可以发现h[i]就是卡特兰数。

g[i][j]表示一颗i节点的二叉树，异或值为j的概率。

还是需要利用左右子树分开考虑来做。

g[n][(x+1)^(y+1)]=sigma(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]

最后的答案就是说1-f[n][0]

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define N 130 using namespace std; double g[N][N],f[N][N],h[N]; int n,a[N],m; int main() { freopen("a.in","r",stdin); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]),m=max(m,a[i]); h[1]=1.0; h[0]=1.0; for (int i=2;i<=m;i++) for (int j=0;j<=i-1;j++) h[i]+=h[j]*h[i-1-j]; // for (int i=1;i<=m;i++) cout<<h[i]<<" "; //cout<<endl; g[1][0]=1.0; 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-1-j; 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<=i-1;j++) g[i][j]/=(double)h[i]; } for (int i=0;i<=127;i++) f[1][i]=g[a[1]][i]; //for (int i=0;i<=127;i++) cout<<f[1][i]<<" "; //cout<<endl; 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("%.6lf\n",1.0-f[n][0]); }