Problem Description
There are n circles on a infinitely large table.With every two circle, either one contains another or isolates from the other.They are never crossed nor tangent.
Alice and Bob are playing a game concerning these circles.They take turn to play,Alice goes first:
1、Pick out a certain circle A,then delete A and every circle that is inside of A.
2、Failling to find a deletable circle within one round will lost the game.
Now,Alice and Bob are both smart guys,who will win the game,output the winner’s name.
Input
The first line include a positive integer T
Output
If Alice won,output “Alice”,else output “Bob”
Sample Input
Sample Output
Author
FZUACM
Source
显然圆的包括关系能够构成一片森林，然后问题就能够转化为：每一步能够删除森林的一棵树或者某树的一棵子树。不能删者输。
这样。问题就变成经典的树上删边游戏了。
树上删边游戏有一个非常重要的结论：叶子节点的SG值为0，中间节点的SG值为它的全部子节点的SG值加1后的异或和。(证明详见贾志豪论文《组合游戏略述——浅谈SG游戏的若干拓展及变形》)
然后逐个处理时间点。用set维护全部圆。每遇到一个进入时间。分情况讨论圆的位置关系。然后把这个圆插入set中。每遇到一个离开时间，从set中删除这个圆。
#include#include #include #include #include #include #include #define F(i,j,n) for(int i=j;i=n;i--) #define ll long long #define maxn 20010 using namespace std; int t,n,cnt,tt,tmp; int head[maxn],fa[maxn]; struct cir{int x,y,r;}a[maxn]; struct edge_type{int next,to;}e[maxn*2]; struct bor { int x,f,id; friend bool operator < (bor a,bor b) { if (a.x==b.x) return a.f s; set ;>::iterator it; inline int read() { int x=0,f=1;char ch=getchar(); while (ch'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&chopt==1) add_edge(it->id,q[i].id); else if (fa[it->id]) add_edge(fa[it->id],q[i].id); } s.insert(pos(q[i].id,1)); s.insert(pos(q[i].id,-1)); } else { s.erase(pos(q[i].id,1)); s.erase(pos(q[i].id,-1)); } } ll sum=0; F(i,1,n) if (!fa[i]) sum=sum^get(i); puts(sum?"Alice":"Bob"); } }
Original: https://www.cnblogs.com/cynchanpin/p/8270264.html
Author: cynchanpin
Title: hdu5299 Circles Game
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/551497/
转载文章受原作者版权保护。转载请注明原作者出处！