参考文献

浅谈算法——博弈论（从零开始的博弈论）

公平组合游戏

  • 双玩家交替行动

  • 与玩家无关只与状态有关

  • 不能行动的玩家判负

注意：NIM 是公平组合游戏，但是围棋绝对不是，不满足后两个条件。

有向图博弈

定义 PP 态为表示当前状态对于上一个玩家是必胜的，即接手到当前局面的玩家是必败的。（简单说就是必败态）

定义 NN 态为表示当前状态对于下一个玩家（就是要执行还未执行操作的这种局面下的玩家）是必胜的，即接手到当前局面的玩家是必胜的。（简单说就是必胜态）

PP 态在绝大博弈游戏种都是终止状态。

重要结论：

  • 对于任意的 PP 态他要么是一个终止状态，要么他的所有后继状态都是 NN 态。

  • 对于任意的 NN 态，他至少有一个后继状态是 PP 态。

也就是 PP 态能反推上一个状态，而 NN 态是不行的。

P6560 [SBCOI2020] 时光的流逝

这题我们考虑拓扑排序。

有环平局。

剩下的从终止状态建反图，求得所有已知的局面。

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
read(st),read(ed);
        for(int i=1;i<=n;i++){
            in[i]=bufin[i];
            state[i]=0;
            if(!in[i]){
                state[i]=-1;
                que.push(i);
            }
        }
        if(!state[ed]){
            state[ed]=-1;//P态必败态
            que.push(ed);
        }
        while(que.size()){
            int u=que.front();
            que.pop();
            for(int i=h[u];~i;i=ne[i]){
                int v=e[i];
                if(state[v]) continue;//已经确定状态不管
                --in[v];
                if(state[u]==-1){
                    state[v]=1;
                    que.push(v);
                }
                else if(!in[v]){
                    //如果后继节点不存在必败态，那么此时更新
                    //更新为必败态
                    if(state[v]!=1){
                        state[v]=-1;
                    }
                    que.push(v);
                }
                //环上由于拓扑结构，永远无法访问，那么是平局态
            }
        }
        write(state[st]),putchar('\n');

结论：PP 态必能推出 NN 态，当该点的所有后继状态都无法唯一确定自己，那么此时自己绝对是必败态，即意味着后继节点都是必胜态。

[AGC010F] Tree Game

经典：后继存在必败态则说明当前是必胜态，后继全部为必胜则是必败态。

性质：

一个点不可能取走比他更大或等于的点，这样会把他自己耗死，即考虑 22 点情况。

那么叶子叶子如果是最小则是必败态。

求一遍 sgsg 出答案。

[AGC010E] Rearranging

高桥君会把整个序列任意排列，然后青木君可以进行任意次操作，每次选择两个相邻的互质的数交换位置。

高桥君希望最终序列的字典序尽量小，而青木君希望字典序尽量大。求最终序列。

从一方入手，先考虑操作，操作是对二元组操作，考虑图上问题，不可以交换的连无相边，那么会形成若干个连通块。

那么答案就成了给边定向。

后手的操作肯定是选择拓扑序最大的，那么先手就应该最小化它，考虑性质，对于连边的相对位置是不变的。

那么我们就对原若干个连通块构建最小的字典序关系，每次都选最小，选一个点，则断边，分治考虑即可。

最后按后手最有求一遍答案，因为先手已经做出最佳决策。

__END__