hdu 5299——Circles Game

题意:

给定n个嵌套的圆，每次可以删除圆以及该圆包含的所有圆，不能删除者输。

思路：

把每个圆看成一个点，把圆的包含关系看成一条单向边，那么就化成了一棵树。
然后就是裸的树上删边游戏模型了。
对于树上删边游戏：
1. 叶子节点的sg为0
2. 中间节点的sg为所有儿子节点的sg+1的异或和

实际上该题目为树上删边游戏的变形。

#include <bits/stdc++.h> using namespace std;typedef long long ll; const int N=20005; int head[N],to[N],nt[N],cnt; struct circle {int x,y,r;void read(){scanf("%d%d%d",&x,&y,&r);} }c[N]; ll pp(ll p){return p*p; } bool ok(circle A,circle B){return pp(A.x-B.x)+pp(A.y-B.y)<pp(A.r-B.r); } bool cmp(circle A,circle B){if (A.r!=B.r) return A.r>B.r;return A.x<B.x; } void addedge(int u,int v){to[++cnt]=v;nt[cnt]=head[u];head[u]=cnt; } int dfs(int u){//printf("%d\n", u);int ans=0;for (int i=head[u];i;i=nt[i]){ans^=(dfs(to[i])+1);}return ans; } void init(){memset(head,0,sizeof(head));memset(nt,-1,sizeof(nt));cnt=0; } int main(int argc, char const *argv[]) {int T,n;scanf("%d",&T);while (T--){scanf("%d",&n);init();for (int i=0;i<n;i++) c[i].read();sort(c,c+n,cmp);int rt=n;for (int i=n-1;i>0;i--){bool ff=0;for (int j=i-1;j>=0;j--){if (ok(c[i],c[j])) {ff=1;addedge(j,i);break;}}if (!ff) addedge(rt,i);}addedge(rt,0);if (dfs(rt)) puts("Alice");else puts("Bob");}return 0; }

总结

以上是生活随笔为你收集整理的hdu 5299——Circles Game的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。