前言

浅浅复习 （我想说，国家队论文yyds😍） 之前学的一点博弈论的皮毛，然后又上某谷练习了一下 （切了几个水题，感觉全靠直觉/_ \） ，我觉得我可以进一步学习博弈论的知识了（双击助力蒟蒻助力Alice薄纱Bob🌹） 。

树上删边游戏

问题描述：

给出一个有 N个点的树，有一个点作为树的根节点。游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。谁无法移动谁输.

结论

叶子节点的SG值为0；中间节点的SG值为它所有子节点的SG值加1后的异或和 。

分析

克朗原理

当树枝在一个顶点上时，用一个非树枝的杆的长度来替代，相当于他们的n异或之和 。

Game

Problem Description

Flynn and oooccc1 are playing game some day. The game is played on a rooted graph which is an undirected graph with every edge attached by some path to a special vertex called the root or the ground. The ground is denoted in the figure that follows by a dotted line. You could see it from the figure. On each step, one player could chop out one edge, and removing that edge and anything not connected to the ground. The one who have nothing to chop with fails. Flynn is the one who is going to move. Help him by telling him if it is possible to win by carefully choose the edge to chop with. 。

Input

There are a few cases. Process to the end of file Each case starts with N (1 <= N <= 1000) stand for the number of points. The next line give N numbers, the i-th (i = 0 … N-1) of which represents its father nodes. The root nodes was the one with value -1. 。

Output

Print “YES” if could win if play optimally, and “NO” otherwise. 。

Sample Input

8 -1 1 2 2 -1 5 6 6 。

Sample Output

NO 。

Author

ZSTU 。

我的代码

                        
                          #include <bits/stdc++.h>
#define int long long
const int N = 1e3 + 5;
std::vector<int> u[N];
int dfs(int v,int fa){
    int result = 0;
    for(auto son:u[v]){
        if(son == fa) continue;
        result = result ^ (dfs(son,v) + 1);
    }
    return result;
}
signed main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);
    int n,sum = 0;
    while (std::cin>>n){
        for(int i = 0;i <= n;i ++){
            u[i].clear();
        }
        std::vector<int> root;
        for(int i = 0;i < n;i ++){
            int t;
            std::cin>>t;
            if(t == -1){//根节点
                root.push_back(i);
            }else{
                u[t].push_back(i);
            }
        }
        sum = 0;
        for(auto i:root){
            sum = sum ^ dfs(i,-1);
        }
        if(sum) std::cout<<"YES\n";
        else std::cout<<"NO\n";
    }
}

                        
                      

就是根据定理来算出每棵树根节点的SG值，再通过局势加（XOR），判断局势。还是比较好理解的，我就不过多描述了😊 绝对不是因为懒 。

图的删边游戏

通过上面的讨论 （对神犇blog的借鉴和学习(～￣(OO)￣)ブ） ，我们现在已经知道如何将一个树上删边游戏转化为nim游戏。 众所周知 树是连通无回路的无向图，那我们不妨将题目的条件修改一下 。

问题描述：

给定一个无向连通图，有一个点作为图的根。两人轮流操作，每人每次可以从图中选择一条边删去，不与根节点相连的部分将被移走。无法操作者输.

分析

费森原理

（环上的点可以融合，且不改变图的SG值。） 一般来说，我们可以把一个带有奇数边的环等价成一个端点和一条边，而偶数边的环等价于一个点.

Christmas Game

Description

Harry and Sally were playing games at Christmas Eve. They drew some Christmas trees on a paper

Then they took turns to cut a branch of a tree, and removed the part of the tree which had already not connected with the root. A step shows as follows

Sally always moved first. Who removed the last part of the trees would win the game. 。

After a while, they all figured out the best strategy and thought the game was too simple for them. Harry said, “The Christmas trees should have some gifts in them!” So Sally drew some gifts (simple polygons) in the initial trees

You may assume the initial picture is a tree with some simple polygons, in which each edge is involved in at most one polygon. We also know that every polygon has only one node involved in the main tree (the hanging point of the giftJ) .In every sub-tree (connected subgraph), there was one and only one node representing the “root”. According to these assumptions, following graphs will never appear

Sally and Harry took turns (Sally was always the first person to move), to cut an edge in the graph, and removed the part of the tree that no longer connected to the root. The person who cannot make a move lost the game. 。

Your job is to decide who will finally win the game if both of them use the best strategy. 。

Input

The input file contains multiply test cases. The first line of each test case is an integer N (N<100), which represents the number of sub-trees. The following lines show the structure of the trees. The first line of the description of a tree is the number of the nodes m (m<100) and the number of the edges k (k<500). The nodes of a tree are numbered from 1 to m. Each of following lines contains 2 integers a and b representing an edge <a, b>. Node 1 is always the root. 。

Output

For each test case, output the name of the winner. 。

Sample Input

2 2 1 1 2 4 4 1 2 2 3 2 4 3 4 。

Sample Output

Sally 。

蒟蒻还不会缩点QAQ，先放着，后面再填坑 。

后记

用到的两个公理没有给出证明，绝对 不 是因为我不会，这里给出我看到的引用在我这篇随笔并且质量比较高的资料的链接或者名称（文档放不了链接啊QAQ） 。

注：我建议按顺序阅读，神犇随意 这个感觉是神犇学习之后，总结的精华 https://blog.csdn.net/wu_tongtong/article/details/79311284 这个是神犇的参考资料（也是本蒟蒻的参考资料） https://wenku.baidu.com/view/379e8baaa58da0116d174924.html? wkts =1690806601160 这个是《Game Theory》的部分译文 https://blog.sina.com.cn/s/blog_8f06da990101252l.html 最后是一篇论文 《组合游戏略述——浅谈 SG 游戏的若干拓展及变形》 石家庄二中 贾志豪 。

最后插个题外话，虽然但是，这个博主真的超级宝藏！！！！总结了IOI国家集训队的部分论文集，还有超多高质量的blog，狠狠泪目😭 。

https://blog.csdn.net/weixin_45697774/article/details/104837003?spm=1001.2014.3001.5506 。

最后此篇关于学不会的博弈论——进阶篇的文章就讲到这里了,如果你想了解更多关于学不会的博弈论——进阶篇的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。