Circles Game

题目连接：

http://acm.hdu.edu.cn/showproblem.php?pid=5299

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

2

1

0 0 1

6

-100 0 90

-50 0 1

-20 0 1

100 0 90

47 0 1

23 0 1

Sample Output

Alice

Bob

Hint

题意

有一个平面，平面上有n个圆，圆与圆之间只有相离和包含的关系。

然后他们开始跑博弈论。

每个人可以拿圆和他所包含的圆。

如果谁不能拿了的话，那就输了。

问你谁能赢。

题解：

很显然，包含和相离关系，那么就是一个森林之间的关系。

然后把这个森林需要建立出来，这个就直接暴力就好了。

然后后面的博弈是一个很经典的东西。

叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值加1 后的异或和。

然后直接跑就好了。

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+6;

vector<int> E[maxn];

struct node

{

    int x,y,r;

};

node a[maxn];

int dp[maxn];

bool cmp(node A,node B)

{

    return A.r>B.r;

}

int fa[maxn];

bool check(node A,node B)

{

    long long k = 1ll*(A.x-B.x)*(A.x-B.x)+1ll*(A.y-B.y)*(A.y-B.y);

    return k<=1ll*A.r*A.r;

}

void init()

{

    memset(a,0,sizeof(a));

    memset(fa,0,sizeof(fa));

    memset(dp,0,sizeof(dp));

    for(int i=0;i<maxn;i++)E[i].clear();

}

void dfs(int x,int fa)

{

    dp[x]=0;

    for(int j=0;j<E[x].size();j++)

    {

        int v = E[x][j];

        if(v==fa)continue;

        dfs(v,x);

        dp[x]^=(dp[v]+1);

    }

}

void solve()

{

    init();

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].r);

    node k;

    a[0].x=0,a[0].y=0,a[0].r=4e4+6;

    sort(a+1,a+1+n,cmp);

    for(int i=1;i<=n;i++)

    {

        for(int j=i-1;j>=0;j--)

            if(check(a[j],a[i]))

            {

                fa[i]=j;

                E[j].push_back(i);

                break;

            }

    }

    dfs(0,-1);

    if(dp[0])cout<<"Alice"<<endl;

    else cout<<"Bob"<<endl;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)solve();

}

巴特西

HDU 5299 Circles Game 博弈论暴力

Circles Game

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

巴特西

HDU 5299 Circles Game 博弈论 暴力

Circles Game

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

HDU 5299 Circles Game 博弈论暴力