OJ-atcoder|AGC017D Game on Tree [博弈论]
【OJ-atcoder|AGC017D Game on Tree [博弈论]】Description:
树上删边游戏。
Solution:
具体见程序。
#include
using namespace std;
const int maxn = 1e5 + 5;
int n;
int sg[maxn];
vector G[maxn];
void dfs(int u, int last) {
for(int i = 0;
i < G[u].size();
++i) {
int v = G[u][i];
if(v == last) {
continue;
}
dfs(v, u);
sg[u] ^= sg[v] + 1;
}
}
int main() {
scanf("%d", &n);
for(int i = 1;
i < n;
++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
puts(sg[1] ? "Alice" : "Bob");
return 0;
}
推荐阅读
- 游戏开发|pygame小游戏开发 - 冰雪英雄会
- PyGame每日一练——五子棋小游戏
- hdu|2016 Multi-University Training Contest 1 C Game(hdu 5725)
- POJ 1027 The Same Game 模拟题
- 比赛题解|2020 杭电多校9 1007 Game (平衡树)
- ZOJ-3447---Doraemon's Number Game (贪心+大数)
- 【组合计数】ARC061F Card Game for Three
- codeforces|Codeforces Round #643 (Div. 2) D. Game With Array (思维,贪心)
- CodeForces - 245C Game with Coins
- 刷题|C - Game With Array CodeForces - 1355D