本文纯属原创，转载注明出处，谢谢。
传送门：?pid=5299
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
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<=20,indicating the total group number of the statistic.As for the following T groups of statistic,the first line of every group must include a positive integer n to define the number of the circles.And the following lines,each line consists of 3 integers x,y and r,stating the coordinate of the circle center and radius of the circle respectively.n≤20000，|x|≤20000，|y|≤20000，r≤20000。
Output
If Alice won,output “Alice”,else output “Bob”
Sample Input
210 0 16-100 0 90-50 0 1-20 0 1100 0 9047 0 123 0 1
Sample Output
AliceBob
2015多校1的一道非常棒的题。
题意是有n个圆，相互之间的关系要么是包含，要么是相离。现在每次可以选择一个圆取走，取掉这个圆的时候，被它包含的所有圆都会被一并取走。现在Alice和Bob轮流以最佳策略取圆，谁取完谁赢。
那么拿到这个题，，首先第一反应就是博弈。然后去博弈的模型里面找，发现“奇异局势”的“取石子游戏”模型跟这个似乎非常相似。确实，如果这个题所有包含的圆都是一个套一个的话，就跟取石子游戏的模型一模一样了。可以直接把所有堆的数字异或起来就行。
但是这个题不同的地方在于可能一个圆包含着两个相离的圆，而这样就与之前的模型有一定的区别了。
这个时候我们可以想象一下，最初的跟取石子游戏相同的那个圆的模型，其实可以相当于最最外层有一个非常非常大的圆把他们套在一起，那么这样就能联想到把同层相离的若干个圆先做一次异或，就能将其转化为一个圆套圆的模型了，这么逐步向外计算下去，就能得到最后的结果了。
而到了这里，就是这个题最后的一个难点了：建树。
这些圆一个套一个的模型，就像是树。被包含的圆是包含它的圆的子节点，而同一层相离的圆则互为兄弟节点，进行上面的运算的时候，就将这个节点所有子节点先异或起来就好。
下面贴代码。
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <string>#include <queue>#include <queue>#include <map>#include <stack>#include <set>#include <cmath>#include <vector>#define INF 0x3f#define eps 1e-6using namespace std;struct ss{long long x;long long y;long long r;}a[20000+100];bool cmp(ss x,ss y){return x.r>y.r;}int judge(int x,int y)//判断两圆位置关系，内含返回1，相离返回0{if((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y)<(a[x].r+a[y].r)*(a[x].r+a[y].r))return 1;return 0;}vector<int> b[20000+100];//b[i]存第i个圆的子节点void fi(int y,int x)//找到当前圆应该存在的地方{for(int i=0;i<b[x].size();i++){if(a[y].r==a[b[x][i]].r)break;if(fuck(y,b[x][i])==1){fi(y,b[x][i]);return;}}b[x].push_back(y);}int play(int x)//执行异或操作{int ans=0;for(int i=0;i<b[x].size();i++)ans^=play(b[x][i]);return ans+1;}int main(){int T;cin>>T;while(T–){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y>>a[i].r;for(int i=0;i<=n;i++)b[i].clear();sort(a+1,a+n+1,cmp);//排序，按半径从大到小，保证后面的圆一定不会包含前面的圆for(int i=1;i<=n;i++)fi(i,0);int ans=play(0);ans-=1;if(ans!=0)cout<<"Alice"<<endl;elsecout<<"Bob"<<endl;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
即使是不成熟的尝试，也胜于胎死腹中的策略。
