首页 > 代码库 > HDU 5996 博弈
HDU 5996 博弈
http://acm.hdu.edu.cn/showproblem.php?pid=5996
博弈论待补。
这题变化了一下,因为注意到奇数层的东西(层数从1开始),对手可以模仿地动,那就相当于没动。
比如从第5层,我选择去了第4,他去第3,我去2,他去1,结果还是到我。所以只需要把偶数层的东西,拿出来,
就是n个石头的博弈了。
异或起来,判断是否等于0,就可以了。博弈论好差,寒假补。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 300000 + 20; int first[maxn]; struct node { int u, v; int tonext; }e[maxn * 2]; int num; int a[maxn]; void add(int u, int v) { ++num; e[num].u = u; e[num].v = v; e[num].tonext = first[u]; first[u] = num; } vector<int>gg; int vis[maxn]; int DFN; void dfs(int cur, int deep) { if (deep % 2 == 0) { gg.push_back(a[cur]); } for (int i = first[cur]; i; i = e[i].tonext) { int v = e[i].v; if (vis[v] == DFN) continue; vis[v] = DFN; dfs(v, !deep); } } void work() { DFN++; gg.clear(); num = 0; memset(first, 0, sizeof first); int n; scanf("%d", &n); for (int i = 1; i <= n - 1; ++i) { int fa; scanf("%d", &fa); add(fa, i); add(i, fa); } for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); } if (n == 1) { printf("lose\n"); return; } vis[0] = DFN; dfs(0, 1); LL ans = gg[0]; for (int i = 1; i < gg.size(); ++i) { ans ^= gg[i]; } if (ans != 0) { printf("win\n"); } else printf("lose\n"); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
HDU 5996 博弈
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。