bzoj 3164: [Heoi2013]Eden的博弈问题博弈论+树形dp题意分析代码

162 阅读 0 评论 107 点赞

我是靠谱客的博主怕黑百褶裙，这篇文章主要介绍bzoj 3164: [Heoi2013]Eden的博弈问题博弈论+树形dp题意分析代码，现在分享给大家，希望可以做个参考。

题意

对于有两个玩家的，状态透明且状态转移确定的博弈游戏，博弈树是常用的分析工具。博弈树是一棵有根树，其中的节点为游戏的状态。若节点B的父亲是A，则说明状态A能通过一次决策转移到状态B。每个状态都有一个唯一的决策方，即这个状态下应该由哪一方做出决策。我们规定双方在任何时候都是轮流做出决策的，即树上相邻节点的决策方总是不相同的。在这个问题中，我们只关心两个玩家的胜负情况，且规定游戏不会出现平局。我们称两个玩家分别为黑方和白方，其中根节点的决策方为黑方。显然每个节点只有两个状态：黑方胜和白方胜。若某内节点（即存在后继节点的节点）的决策方为黑方，则该节点为黑方胜的充要条件为它的儿子中存在黑方胜的节点，反之亦然。求解博弈树即为判明博弈树根节点的状态。如果我们得知了所有叶节点（即无后继节点的节点）的状态，那么博弈树就很容易求解了。但是现在的情况是所有叶节点的状态均为未知的，需要进一步的计算。对于一个由叶节点构成的集合S，如果S中的节点均被判明为黑方胜，就可以断言根节点为黑方胜的话，则称 S为一个黑方胜集合。对于黑方胜集合 S，
如果对于任意的黑方胜集合 S’均满足|S| ≤ |S’ |（|S|表示集合S中的元素数目），
则称S为一个最小黑方胜集合。同样地，也可以定义白方胜集合和最小白方胜集合。
Eden最近在研究博弈树问题。他发现，如果一个叶节点既属于某一个最小黑方胜集合，又属于一个最小白方胜集合，那么求解这个节点的状态显然最有益于求解根节点的状态。像这样的叶节点就称之为关键叶节点。对于一棵给定的博弈树，Eden想要知道哪些叶节点是关键叶节点。
1 ≤ n ≤ 200,000

分析

题目很长，不过是道水题。
先看黑关键点怎么求，白点同理。
设f[i]表示点i为黑必胜时最少需要把多少叶节点染黑。
按照深度分类转移即可。

代码

复制代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;
const int inf=1000000000;

int n,dep[N],cnt,last[N],f[N],tag[N];
struct edge{int to,next;}e[N];

void addedge(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}

void dp1(int x,int fa)
{
    dep[x]=dep[fa]+1;
    for (int i=last[x];i;i=e[i].next) dp1(e[i].to,x);
    if (!last[x]) {f[x]=1;return;}
    if (dep[x]&1)
    {
        f[x]=inf;
        for (int i=last[x];i;i=e[i].next)
            if (f[x]=min(f[x],f[e[i].to]));
    }
    else
    {
        f[x]=0;
        for (int i=last[x];i;i=e[i].next) f[x]+=f[e[i].to];
    }
}

void work1(int x)
{
    if (!last[x]) tag[x]++;
    if (dep[x]&1)
    {
        for (int i=last[x];i;i=e[i].next)
            if (f[e[i].to]==f[x]) work1(e[i].to);
    }
    else
    {
        for (int i=last[x];i;i=e[i].next) work1(e[i].to);
    }
}

void dp2(int x)
{
    for (int i=last[x];i;i=e[i].next) dp2(e[i].to);
    if (!last[x]) {f[x]=1;return;}
    if (dep[x]&1)
    {
        f[x]=0;
        for (int i=last[x];i;i=e[i].next) f[x]+=f[e[i].to];
    }
    else
    {
        f[x]=inf;
        for (int i=last[x];i;i=e[i].next)
            if (f[x]=min(f[x],f[e[i].to]));
    }
}

void work2(int x)
{
    if (!last[x]) tag[x]++;
    if (dep[x]&1)
    {
        for (int i=last[x];i;i=e[i].next) work2(e[i].to);
    }
    else
    {
        for (int i=last[x];i;i=e[i].next)
            if (f[e[i].to]==f[x]) work2(e[i].to);
    }
}

int main()
{
    scanf("%d",&n);
    for (int i=2,x;i<=n;i++) scanf("%d",&x),addedge(x,i);
    dp1(1,0);work1(1);
    dp2(1);work2(1);
    int s1=0,s2=0;
    for (int i=1;i<=n;i++) if (tag[i]==2) {printf("%d ",i);break;}
    for (int i=1;i<=n;i++) if (tag[i]==2) s1++,s2^=i;
    printf("%d %d",s1,s2);
    return 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200005;
const int inf=1000000000;

int n,dep[N],cnt,last[N],f[N],tag[N];
struct edge{int to,next;}e[N];

void addedge(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}

void dp1(int x,int fa)
{
    dep[x]=dep[fa]+1;
    for (int i=last[x];i;i=e[i].next) dp1(e[i].to,x);
    if (!last[x]) {f[x]=1;return;}
    if (dep[x]&1)
    {
        f[x]=inf;
        for (int i=last[x];i;i=e[i].next)
            if (f[x]=min(f[x],f[e[i].to]));
    }
    else
    {
        f[x]=0;
        for (int i=last[x];i;i=e[i].next) f[x]+=f[e[i].to];
    }
}

void work1(int x)
{
    if (!last[x]) tag[x]++;
    if (dep[x]&1)
    {
        for (int i=last[x];i;i=e[i].next)
            if (f[e[i].to]==f[x]) work1(e[i].to);
    }
    else
    {
        for (int i=last[x];i;i=e[i].next) work1(e[i].to);
    }
}

void dp2(int x)
{
    for (int i=last[x];i;i=e[i].next) dp2(e[i].to);
    if (!last[x]) {f[x]=1;return;}
    if (dep[x]&1)
    {
        f[x]=0;
        for (int i=last[x];i;i=e[i].next) f[x]+=f[e[i].to];
    }
    else
    {
        f[x]=inf;
        for (int i=last[x];i;i=e[i].next)
            if (f[x]=min(f[x],f[e[i].to]));
    }
}

void work2(int x)
{
    if (!last[x]) tag[x]++;
    if (dep[x]&1)
    {
        for (int i=last[x];i;i=e[i].next) work2(e[i].to);
    }
    else
    {
        for (int i=last[x];i;i=e[i].next)
            if (f[e[i].to]==f[x]) work2(e[i].to);
    }
}

int main()
{
    scanf("%d",&n);
    for (int i=2,x;i<=n;i++) scanf("%d",&x),addedge(x,i);
    dp1(1,0);work1(1);
    dp2(1);work2(1);
    int s1=0,s2=0;
    for (int i=1;i<=n;i++) if (tag[i]==2) {printf("%d ",i);break;}
    for (int i=1;i<=n;i++) if (tag[i]==2) s1++,s2^=i;
    printf("%d %d",s1,s2);
    return 0;
}