[关闭]
@ysner 2018-07-30T16:21:01.000000Z 字数 1242 阅读 1607

[HDU3094]A tree game

博弈论


题面

一棵个点的有根树,两个人轮流操作。一次操作是选择一条边,删除此边以及删掉边后和根不连通的部分。询问谁有必胜策略。

解析

可以把这棵树看成一堆石子,每个点(或它的父边)看成一个石子。
这就很像游戏了。

有个结论
原来想把子树根结点各儿子的根单独的求个异或和,来得到该子树的值。
后来发现自己似乎不知道根单独的值。。。
所以应把子树根结点各儿子的,把它们包括的情况延伸到子树根节点,再进行异或,才能得到整个子树的值。

根节点的值就是整个游戏的值。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define max(a,b) ((a)>(b)?(a):(b))
  11. #define min(a,b) ((a)<(b)?(a):(b))
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=1e5+100;
  16. struct Edge{int to,nxt;}e[N<<1];
  17. int n,m,h[N],cnt;
  18. ll ans;
  19. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  20. il ll gi()
  21. {
  22. re ll x=0,t=1;
  23. re char ch=getchar();
  24. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  25. if(ch=='-') t=-1,ch=getchar();
  26. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  27. return x*t;
  28. }
  29. il int dfs(re int u,re int fa)
  30. {
  31. re int SG=0;
  32. for(re int i=h[u];i+1;i=e[i].nxt)
  33. {
  34. re int v=e[i].to;
  35. if(v==fa) continue;
  36. SG^=(dfs(v,u)+1);
  37. }
  38. return SG;
  39. }
  40. int main()
  41. {
  42. ios::sync_with_stdio(false);
  43. re int T=gi();
  44. while(T--)
  45. {
  46. n=gi();cnt=0;memset(h,-1,sizeof(h));
  47. fp(i,1,n-1)
  48. {
  49. re int u=gi(),v=gi();
  50. add(u,v);add(v,u);
  51. }
  52. puts(dfs(1,0)?"Alice":"Bob");
  53. }
  54. return 0;
  55. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注