圆圈游戏 - 博弈论

60 阅读 0 评论 40 点赞

我是靠谱客的博主尊敬花生，最近开发中收集的这篇文章主要介绍圆圈游戏 - 博弈论，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意：给你n个不相交也不重合也不相切的圆，两个人玩游戏每次每人删掉一个圆及被这个圆包含的圆。不能动的人输。问谁赢。
题解：圆的异或并然后树上删边游戏。
前者set实现的时候维护当前横坐标和两个半圆。比较的时候根据其上面一个上上半圆还是下半圆判定当前这个半圆的fa。
后者结论是每个点的sg是所有子结点的(sg+1)的异或和。


#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<cmath>
#define lint long long
#define gc getchar()
#define db double
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 20010
#define clr(a,n) memset(a,0,sizeof(int)*((n)+1))
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
inline int inn()
{
    int x=0,ch,s=1;while(((ch=gc)<'0'||ch>'9')&&ch!='-');
    if(ch^'-') x=ch^'0';else s=-1;
    while((ch=gc)>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');
    return s*x;
}
inline lint squ(int x) { return (lint)x*x; }
struct C{
    int x,y,r;
    inline bool operator<(const C &c)const{ return x-r<c.x-c.r; }
}c[N];
struct P{
    int pos,id,kd;P(int p=0,int i=0,int k=0) { pos=p,id=i,kd=k; }
    inline bool operator<(const P &p)const{ return (pos==p.pos)?kd>p.kd:(pos<p.pos); }
}p[N<<1];
int Curx;
struct S{
    int id,sgn;S(int _i=0,int _s=0) { id=_i,sgn=_s; }
    inline bool operator<(const S &s)const
    {
        int a=id,b=s.id;if(a==b) return sgn<s.sgn;
        db ya=c[a].y+  sgn*sqrt(squ(c[a].r)-squ(Curx-c[a].x));
        db yb=c[b].y+s.sgn*sqrt(squ(c[b].r)-squ(Curx-c[b].x));
        return ya<yb;
    }
};set<S> s;
struct edges{
    int to,pre;
}e[N];int h[N],etop,fa[N];
inline int add_edge(int u,int v) { return e[++etop].to=v,e[etop].pre=h[u],h[u]=etop; }
int sg(int x,int res=0) { for(int i=h[x];i;i=e[i].pre) res^=sg(e[i].to)+1;return res; }
int main()
{
    for(int T=inn();T;T--)
    {
        int n=inn(),pc=0,ans=0;s.clear(),clr(h,n),etop=0;
        rep(i,1,n) c[i].x=inn(),c[i].y=inn(),c[i].r=inn();sort(c+1,c+n+1);
        rep(i,1,n) p[++pc]=P(c[i].x-c[i].r,i,1),p[++pc]=P(c[i].x+c[i].r,i,-1);
        sort(p+1,p+pc+1);
        rep(i,1,pc)
            if(p[i].kd>0)
            {
                Curx=p[i].pos;
                set<S>::iterator it=s.upper_bound(S(p[i].id,1));
                if(it==s.end()) fa[p[i].id]=0;
                else if(it->sgn<0) fa[p[i].id]=fa[it->id];
                else fa[p[i].id]=it->id;
                s.insert(S(p[i].id,1)),s.insert(S(p[i].id,-1));
            }
            else Curx=p[i].pos,s.erase(S(p[i].id,1)),s.erase(S(p[i].id,-1));
//      rep(i,1,n) debug(i)sp,debug(c[i].x)sp,debug(c[i].y)sp,debug(c[i].r)sp,debug(fa[i])ln;
        rep(i,1,n) if(fa[i]) add_edge(fa[i],i);
        rep(i,1,n) if(!fa[i]) ans^=sg(i)+1;
        printf(ans?"Alicen":"Bobn");
    }
    return 0;
}