[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多校联赛补题]hdu5371 Hotaru's problem


下一篇:[2015hdu多校联赛补题]hdu5378 Leader in Tree Land