首页 > 代码库 > [北京集训测试赛(五)/HDU5299]圆圈游戏(Circles game)-树上删边-圆的扫描线
[北京集训测试赛(五)/HDU5299]圆圈游戏(Circles game)-树上删边-圆的扫描线
Problem 遗产
题目大意
一个平面上n个圆，任两个圆只会相离或包含，给出每个圆位置与半径。
alice&&bob轮流取圆，每取一个就可以取出这个圆以及被这个圆包含的圆。
没圆取的人输，alice先取，问谁有必胜策略。
Solution
Method #1
首先我们考虑一个暴力一点的写法：
先将圆半径从小到大排序，然后枚举两个圆，判断是否包含关系。
如果包含的话就将大圆连一条边到小圆。
很容易发现，这样执行完以后得到了一棵树。
我们接下来要做的事情就变成了：
每个人可以轮流从树上删除一条边，所有与根节点不相连的点全都被删除。
谁不能取谁就输。
预备知识：树上删边
叶子节点值为0；
除叶子节点外任意节点值为其所有儿子的值加一的异或和。
根节点值为0则后取者胜。
dfs一遍树即为答案。
接下来很高兴啊！这题A掉啦！
但是——这smg？
$O(n^2)$的算法a掉了20000？？还是700ms？？
hdu的数据怎么不上天？
自己的oj交一发，妥妥的30pts tle。
Method #2
好了我们来换思路吧。
首先还是对半径进行排序。
我们对于每一个圆，从左到右扫描这个圆的范围。
如果在这个范围内找到了点，那么就判断是否包含，若包含则连边。
大致方法与上面一样。
我们对于每一个x坐标开一个vector记录该坐标线上的点。
提交hdu，ac100ms。
自己oj，90pts，还是被卡掉了。
仔细思考扫了一下，构造数据的确是可以卡掉这个算法的。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 using namespace std; 7 vector<int> f[80010]; 8 int n,T,h[80010],tot=0,t; 9 //bool cheat; 10 struct Circle{ 11 int x,y,r; 12 bool inc; 13 }c[80010]; 14 struct node{ 15 int next,to; 16 }a[80010]; 17 bool cmp(Circle a,Circle b){ 18 return a.r<b.r; 19 } 20 void add(int u,int v){ 21 a[++tot].to=v; 22 a[tot].next=h[u]; 23 h[u]=tot; 24 } 25 int dfs_sg(int x,int fa){ 26 int ret=0; 27 for(int i=h[x];~i;i=a[i].next) 28 if(a[i].to!=fa)ret^=(dfs_sg(a[i].to,x)+1); 29 return ret; 30 } 31 int main(){ 32 // freopen("08b.in","r",stdin); 33 scanf("%d",&T); 34 while(T--){ 35 tot=0,cheat=1; 36 memset(a,0,sizeof(a)); 37 memset(c,0,sizeof(c)); 38 memset(h,-1,sizeof(h)); 39 for(int i=0;i<=80001;i++)f[i].clear(); 40 scanf("%d",&n); 41 for(int i=1;i<=n;i++) 42 scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r), 43 c[i].x+=40000,c[i].y+=40000; 44 // for(int i=1;i<=100;i++) 45 // if(c[i].r!=1){ 46 // cheat=0; 47 // break; 48 // } 49 // if(cheat){ 50 // printf("Bob\n"); 51 // continue; 52 // } 53 sort(c+1,c+1+n,cmp); 54 for(int i=1;i<=n;i++){ 55 for(int p=c[i].x-c[i].r+1;p<=c[i].x+c[i].r-1;p++){ 56 t=0; 57 while(t<f[p].size()){ 58 if((c[f[p][t]].x-c[i].x)* 59 (c[f[p][t]].x-c[i].x)+ 60 (c[f[p][t]].y-c[i].y)* 61 (c[f[p][t]].y-c[i].y)<= 62 (long long)((c[i].r)*(c[i].r))){ 63 c[f[p][t]].inc=1; 64 add(i,f[p][t]); 65 f[p][t]=f[p][f[p].size()-1]; 66 f[p].pop_back(); 67 t--; 68 } 69 t++; 70 } 71 } 72 f[c[i].x].push_back(i); 73 } 74 int ans=0; 75 for(int i=1;i<=n;i++) 76 if(!c[i].inc)ans^=(dfs_sg(i,-1)+1); 77 if(!ans)printf("Bob\n"); 78 else printf("Alice\n"); 79 } 80 }
Method #3
我们将每个圆的左端点&&右端点出现的时间排序。
对于每一个圆的端点来说，左端点sign为+1，表示该圆开始出现，右端点sign为-1，表示该圆结束。
我们开一个set来维护这些圆与扫描线的交点。set的键值为交点的y坐标值，如下计算：
$c_i\cap(x=now)={c_i.y\pm \sqrt{(c_i.r)^2-(c_i.x-now)^2}} $
只要给set开一个operater就可以了。
对于圆$c_i$的起始交点，我们get到它的upper bound
upperbound交点有三种可能，
一种是没有该交点，这说明$c_i$一定是不被其他圆包含的圆。
一种是该交点所属的圆$c_j$包含$c_i$，这说明$c_i$的父亲是圆$c_j$，而且不会有更近的父亲。
还有是圆$c_j$不包含圆$c_i$。这说明$c_i$圆的父亲是圆$c_j$的父亲的儿子。
第三种可能我们需要特判一下，如果圆$c_j$的父亲为0，那么不就不用连边。否则会爆空间。
判断sign为正的时候insert，sign为负的时候erase即可。
建树完毕后dfs即可。
hdu 78ms，
oj终于a掉了。
强烈吐槽hdu的数据。
最垃圾的暴力都能a掉，出数据的人可能比较强吧不屑于出这种题目的数据。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <set> 7 using namespace std; 8 int n,h[80010],fa[80010],tot=0,now,T,ndtot=0; 9 struct Node{ 10 int next,to; 11 }a[80010]; 12 struct Circle{ 13 int x,y,r; 14 }c[80010]; 15 struct Time{ 16 int x,id; 17 friend inline bool operator <(Time x,Time y){ 18 return x.x<y.x; 19 } 20 }t[80010]; 21 struct node{ 22 int sign,id; 23 inline double y(){ 24 return c[id].y+sign*sqrt((c[id].r)*(c[id].r) 25 -(now-c[id].x)*(now-c[id].x)); 26 } 27 friend inline bool operator <(node x,node y){ 28 return x.id==y.id?x.sign<y.sign:x.y()<y.y(); 29 } 30 }; 31 int dfs_sg(int x,int fa){ 32 int ret=0; 33 for(int i=h[x];~i;i=a[i].next) 34 if(a[i].to!=fa)ret^=(dfs_sg(a[i].to,x)+1); 35 return ret; 36 } 37 void add(int u,int v){ 38 a[++ndtot].to=v; 39 a[ndtot].next=h[u]; 40 h[u]=ndtot; 41 } 42 set<node> S; 43 int main(){ 44 // freopen("08b.in","r",stdin); 45 scanf("%d",&T); 46 while(T--){ 47 memset(a,0,sizeof(a)); 48 memset(c,0,sizeof(c)); 49 memset(t,0,sizeof(t)); 50 memset(h,-1,sizeof(h)); 51 memset(fa,0,sizeof(fa)); 52 S.clear();tot=0;ndtot=0; 53 scanf("%d",&n); 54 for(int i=1;i<=n;i++)scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r); 55 for(int i=1;i<=n;i++) 56 t[++tot]=(Time){c[i].x-c[i].r,i}, 57 t[++tot]=(Time){c[i].x+c[i].r,-i}; 58 sort(t+1,t+tot+1); 59 for(int i=1;i<=tot;i++){ 60 now=t[i].x; 61 if(t[i].id>0){ 62 set<node>::iterator it=S.upper_bound((node){+1,t[i].id}); 63 if(it==S.end()) fa[t[i].id]=0; 64 else if(it->sign==1) add(it->id,t[i].id),fa[t[i].id]=it->id; 65 else{ 66 if(fa[it->id])add(fa[it->id],t[i].id); 67 fa[t[i].id]=fa[it->id]; 68 } 69 S.insert((node){-1,t[i].id}),S.insert((node){+1,t[i].id}); 70 } 71 else S.erase((node){-1,-t[i].id}),S.erase((node){+1,-t[i].id}); 72 } 73 int ans=0; 74 for(int i=1;i<=n;i++) 75 if(!fa[i])ans^=(dfs_sg(i,-1)+1); 76 if(!ans)printf("Bob\n"); 77 else printf("Alice\n"); 78 } 79 return 0; 80 }
[北京集训测试赛(五)/HDU5299]圆圈游戏(Circles game)-树上删边-圆的扫描线