首页 > 代码库 > HDU5996:dingyeye loves stone
HDU5996:dingyeye loves stone
题目链接：dingyeye loves stone
题意：给出一棵树，树上的每个节点都有石子若干，
两人博弈，每次操作都可以把任意节点的任意石子数转移到它的父亲节点，
若无法操作则输，给出树上的节点及石子数，问先手是否能赢
分析：“阶梯博弈”，若深度为偶数的节点，对方移多少石子，我们就移多少。故偶数节点可忽略不计
接下来只要异或深度为奇数的节点石子数即可
感想：深度不会求，dfs不会写，我真菜
第一种方法.
记录每个节点的子节点，dfs遍历所有节点，若深度为奇则异或
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<vector> 6 using namespace std; 7 8 typedef long long ll; 9 int t,n,x,value[100010],dep[100010];10 11 ll ans;12 13 vector<int>g[100010];14 void dfs(int i,int d)15 {16 if(d) ans^=value[i];17 for(int j=0;j<g[i].size();++j) dfs(g[i][j],d^1);18 }19 20 int main()21 {22 for(scanf("%d",&t);t--;)23 {24 scanf("%d",&n);25 for(int i=0;i<n;++i) g[i].clear();26 for(int i=1;i<n;++i)27 {28 scanf("%d",&x);29 g[x].push_back(i);30 }31 //memset(censhu,0,sizeof(censhu));32 //fa[0]=0;33 for(int i=0;i<n;++i) scanf("%d",value+i);ans=0;34 dfs(0,0);35 if(ans) puts("win");else puts("lose");36 }37 return 0;38 }39 40 /*41 int main()42 {43 for(scanf("%d",&t);t--;)44 {45 scanf("%d",&n);46 memset(dep,0,sizeof(dep));47 for(int i=1;i<n;++i)48 {49 scanf("%d",&x);50 dep[i]=dep[x]+1;51 }52 //memset(censhu,0,sizeof(censhu));53 //fa[0]=0;54 ans=0;55 for(int i=0;i<n;++i) {scanf("%d",value+i);if(dep[i]&1) ans^=value[i];}56 if(ans) puts("win");else puts("lose");57 }58 return 0;59 }60 */
第二种方法.
读入每个节点的父亲时，记录深度，题目保证父亲出现在子节点前
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<vector> 6 using namespace std; 7 8 typedef long long ll; 9 int t,n,x,value[100010],dep[100010];10 11 ll ans;12 /*13 vector<int>g[100010];14 void dfs(int i,int d)15 {16 if(d) ans^=value[i];17 for(int j=0;j<g[i].size();++j) dfs(g[i][j],d^1);18 }19 20 int main()21 {22 for(scanf("%d",&t);t--;)23 {24 scanf("%d",&n);25 for(int i=0;i<n;++i) g[i].clear();26 for(int i=1;i<n;++i)27 {28 scanf("%d",&x);29 g[x].push_back(i);30 }31 //memset(censhu,0,sizeof(censhu));32 //fa[0]=0;33 for(int i=0;i<n;++i) scanf("%d",value+i);ans=0;34 dfs(0,0);35 if(ans) puts("win");else puts("lose");36 }37 return 0;38 }39 */40 41 int main()42 {43 for(scanf("%d",&t);t--;)44 {45 scanf("%d",&n);46 memset(dep,0,sizeof(dep));47 for(int i=1;i<n;++i)48 {49 scanf("%d",&x);50 dep[i]=dep[x]+1;51 }52 //memset(censhu,0,sizeof(censhu));53 //fa[0]=0;54 ans=0;55 for(int i=0;i<n;++i) {scanf("%d",value+i);if(dep[i]&1) ans^=value[i];}56 if(ans) puts("win");else puts("lose");57 }58 return 0;59 }
HDU5996:dingyeye loves stone
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。