《博弈 - 整理》
2021/5/23 10:28:29
本文主要是介绍《博弈 - 整理》,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
green博弈:
模型:对于一棵树,两个人A和B每次可以选定一个点删去,同时这个点的子树也会被删去。
考虑必胜态和必败态的判断。
首先如果是一条链,那么就可以看成取一堆石子。
那么,从根上再延伸出一条链,那么就可以看成取两堆石子,那么就是标准的NIM博弈。
我们知道NIM博弈的答案就是SG函数值,也就是多个堆的异或和。
那么这里我们就可以推出根的SG函数值就是它的子树的SG函数的异或和。
也由上面推导可见,我们根的SG函数和自身没关系,所以对于每个节点的SG函数,初始值应该为0。
在处理子树的时候,再和每个子树加上1。
https://ac.nowcoder.com/acm/contest/16832/J
![](/images/baidian.png)
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e6 + 5; const int M = 1e5 + 5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e9 #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; vector<int> G[N]; int sg[N]; void dfs(int u,int fa) { sg[u] = 0; for(auto v : G[u]) { if(v == fa) continue; dfs(v,u); sg[u] ^= (sg[v] + 1); } } int main() { int ca;ca = read(); while(ca--) { int n;n = read(); for(int i = 1;i <= n;++i) G[i].clear(); for(int i = 1;i < n;++i) { int x,y;x = read(),y = read(); G[x].push_back(y); G[y].push_back(x); } dfs(1,0); printf("%s\n",sg[1] ? "NO" : "YES"); } // system("pause"); return 0; }View Code
这篇关于《博弈 - 整理》的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)