YZOJ P2050 [FJOI2013]圆形游戏

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)\) 。

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注