首页 > 代码库 > HDU 5996 dingyeye loves stone ---BestCoder Round #90
HDU 5996 dingyeye loves stone ---BestCoder Round #90
题目链接
设根节点的深度为0,将所有深度为奇数的节点的石子数目xor起来,则先手必胜当且仅当这个xor和不为0。 证明同阶梯博弈。对于偶深度的点上的石子,若对手移动它们,则可模仿操作;对于奇深度上的石子,移动一次即进入偶深度的点。 时空复杂度O(n)。
用vector存搜一下就行。
#include <cstdio> #include <iostream> #include <vector> #include <cstring> using namespace std; vector<int> v[100050]; int num[100050]; int ans; void dfs(int i,int d) { if(d&1) ans=ans^num[i]; for(int j=0;j<v[i].size();j++) dfs(v[i][j],d+1); } int main() { int t,n,x; scanf("%d",&t); while(t--) { ans=0; scanf("%d",&n); memset(num,0,sizeof(num)); for(int i=0;i<n;i++) v[i].clear(); for(int i=1;i<n;i++) { scanf("%d",&x); v[x].push_back(i); } for(int i=0;i<n;i++) scanf("%d",&num[i]); dfs(0,0); if(ans) puts("win"); else puts("lose"); } return 0; }
HDU 5996 dingyeye loves stone ---BestCoder Round #90
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。