[2015hdu多校联赛补题]hdu5299 Circles Game

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5299

题意：

在欧几里得平面上有n个圆，圆之间不会相交也不会相切，现在Alice和Bob玩游戏，两人轮流选择一个圆删除它和它包含的所有圆（Alice先手），在自己的轮次无圆可删判输，问你谁会赢得比赛

解：先将圆之间的关系抽象，转化为一个树图，然后套SG定理（WoW，我可不知道什么是SG定理

想详细了解的话，这里是和SG函数相关的东西：http://www.cnblogs.com/shjwudp/articles/4715439.html

然后又有SG定理（感觉不想关啊喂：

我们有如下定理:

[定理]

叶子节点的 SG 值为 0;

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

将圆关系抽象这个问题具体就是要查找，每个圆直接包含的圆，看了网上的题解，基本都是O(n^2)，（有看起来是O(n logn)的

具体的请看代码理解吧：

 /*

  * Problem:

  * Author:  SHJWUDP

  * Created Time:  2015/8/8 星期六 15:06:48

  * File Name: 1006.cpp

  * State:

  * Memo:

  */

 #include <iostream>

 #include <cstdio>

 #include <vector>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int DIMENSION=;

 struct Point {

     long long x[DIMENSION];

 };

 struct Circle {

     Point o;

     int r;

 };

 struct Edge {

     int u, v;

     Edge(int u, int v):u(u), v(v) {}

 };

 int n;

 vector<Circle> arr;

 vector<Edge> edges;

 vector<vector<int> > G;

 bool cmp(const Circle & a, const Circle & b) {

     return a.r>b.r;

 }

 void init() {

     edges.clear();

     G.assign(n+, vector<int>());

 }

 void addEdge(int u, int v) {

     edges.push_back(Edge(u, v));

     G[u].push_back(edges.size()-);

 }

 template<class T> T sqr(T x) { return x * x; }

 bool judge(int a, int b) {

     if(a==n || b==n) return ;

     int d=;

     for(int k=; k<DIMENSION; k++) {

         d+=sqr(arr[a].o.x[k]-arr[b].o.x[k]);

     }

     int r=max(arr[a].r, arr[b].r);

     return r*r>=d;

 }

 void fin(int u, int x) {

     for(int i : G[u]) {

         Edge & e=edges[i];

         if(judge(x, e.v)) {

             fin(e.v, x);

             return;

         }

     }

     addEdge(u, x);

 }

 int dfs(int u) {

     int res=;

     for(int i : G[u]) {

         Edge & e=edges[i];

         res^=+dfs(e.v);

     }

     return res;

 }

 int main() {

 #ifndef ONLINE_JUDGE

     freopen("in", "r", stdin);

     //freopen("out", "w", stdout);

 #endif

     int T;

     scanf("%d", &T);

     while(T--) {

         scanf("%d", &n);

         arr.resize(n);

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

             Circle & c=arr[i];

             for(int k=; k<DIMENSION; k++) {

                 scanf("%I64d", &c.o.x[k]);

             }

             scanf("%d", &c.r);

         }

         sort(arr.begin(), arr.end(), cmp);

         init();

         for(int i=; i<n; i++) fin(n, i);

         puts(dfs(n)?"Alice":"Bob");

     }

     return ;

 }

hdu5299

巴特西

[2015hdu多校联赛补题]hdu5299 Circles Game

最新文章

热门文章