YZOJ P2050 [FJOI2013]圆形游戏

时间限制：8000MS      内存限制：262144KB

难度：$8.0$

• 题目描述

在一个无穷大的桌面上有 $n$ 个圆形，保证任意两个圆相离或者相含，不存在相切或相交。现在 Alice 和 Bob 在玩一个圆形游戏，以 Alice 为先手，双方以如下步骤轮流游戏：

1，选定一个圆 $A$，把 $A$ 以及所有完全在 $A$ 内部的圆都删除；

2，如果在自己回合无法找到可删除的圆，则输掉比赛。

假设 Alice 和 Bob 都非常聪明，请问最终谁能够取得胜利？请编程输出最终获胜的人。

• 输入格式

输入数据的第一行为一个正整数 $T$，表示数据组数。

接下来 $T$ 组数据，对于每组数据，第一行包含 $1$ 个正整数 $n$，表示圆形的个数。

之后 $n$ 行，每行为 $3$ 个整数 $x$、$y$ 和 $r$ ，分别表示圆形的圆心坐标以及圆的半径。

• 输出格式

假设 Alice 最后获胜，则输出一行 “Alice”（不包括引号），否则输出 “Bob” 。

• 样例输入

• 样例输出

• 数据规模与约定

$100\%$ 的数据满足 $T \leq 100$，$n \leq m20000$，$\left|x\right|, \left|y\right|, r \leq 10^8$ 。

 

 

 

---

 

 

 

三·原题套在一起wwwww

首先把 $n$ 个圆按照半径从小到大排序，那么对于第 $i$ 个圆，在半径比它大的圆中找到第一个包含它的圆 $j$ ，$i \rightarrow$ 连边，那么此时会连成一个森林。

若再添加一个 $x=0, y=0, r=\infty$ 的 $0$ 号圆，那么此时会连成一棵以 $0$ 为根节点的树。

然后就是一个 SG函数 啦，在上面 DP 一下，有 $f_o = (f_{s_1}+1) \oplus (f_{s_2}+1) \oplus \cdots$ ，若 $o$ 为叶子结点则 $f_o=0$ 。（其实我也不知道为什么

这样转移是 $O(n)$ 的，但是建树却是 $O(n^2)$ 的，想办法优化。

其实可以使用扫描线维护这些圆的位置关系。

把圆拆成两个事件，$x-r$ 插入且 $x+r$ 弹出，并且把这个圆拆成上半圆和下半圆，近似看成右括号和左括号，那么其实就是要动态维护一个括号序列。

并且在 插入/弹出 前圆的位置关系都是不会发生改变的。

这样，例如 (())就是包含关系，()()就是相离关系。

要找出当前圆被哪一个圆完全包含，就是找当前左括号的前驱：若为左括号则被其包含，若为右括号则它们同时被另一个圆包含。

发现可以使用平衡树维护括号序列，时间复杂度 $O(n \log n)$ 。