当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6347:点集划分

题目描述
度度熊发现平面上有 $2n$ 个点,满足任意两点不重合、任意三点不共线。现在度度熊要将这 $2n$ 个点划分进两个集合 $A$ 和 $B$ 中,使得 $|A|=|B|=n$,也就是两个集合中的元素个数均为 $n$,并且存在平面上不经过任意一个给定点的直线,使得 $A$ 中的所有点在直线的同侧、$B$ 中的所有点也在直线的同侧,但是 $A$ 中的点和 $B$ 中的点在直线的异侧。

一个划分方案可以用一个长度为 $2n$ 的字符串表示,第 $i$ 个位置是 'A' 表示第 $i$ 个点属于集合 $A$、 是 'B' 则表示第 $i$ 个点属于集合 $B$,两个划分方案不同当且仅当存在一个点在两个方案中属于不同的集合,也就是两个划分方案对应的字符串不同。你需要帮度度熊求出满足条件的划分方案数,并给出一个字典序最小的划分方案。

由于方案数可能很大,同时也是为了 ruin the legend,你只需要输出方案数对 $1000000007(=10^9+7)$ 取模后的值。

记 $|S|$ 为字符串 $S$ 的长度,对于两个字符串 $S$ 和 $T$ ,定义 $S$ 的字典序比 $T$ 小,当且仅当存在非负整数 $k(\leq \min(|S|,|T|))$ 使得 $S$ 的前 $k$ 个字符与 $T$ 的前 $k$ 个字符对应相同,并且要么满足 $|S| = k$ 且 $|T| > k$,要么满足 $k < \min(|S|,|T|)$ 且 $S$ 的第 $k+1$ 个字符比 $T$ 的第 $k+1$ 个字符小。例如 "AA" 的字典序比 "AAA" 小,"AB" 的字典序比 "BA" 小。

请注意,本题时限较紧,你需要尽可能优化算法的实现.
输入解释
第一行包含一个整数 $T$,表示有 $T$ 组测试数据。

接下来依次描述 $T$ 组测试数据。对于每组测试数据:

第一行包含一个整数 $n$,表示要划分出的两个集合的大小。

接下来 $2n$ 行,每行包含两个整数 $x_i, y_i$,表示第 $i$ 个点的坐标。

保证 $ 1 \leq T \leq 10$,$1 \leq n \leq 10^3$,$-10^4 \leq x_i, y_i \leq 10^4$。
输出解释
对于每组测试数据,输出一行信息 "Case #x: y T"(不含引号),其中 x 表示这是第 $x$ 组测试数据,y 表示满足条件的划分方案数对 $1000000007(=10^9+7)$ 取模后的值,T 表示字典序最小的划分方案,相邻两个字符之间不要有多余空格,行末不要有多余空格。
输入样例
2
2
0 0
1 1
0 1
1 0
2
0 0
1 1
3 0
0 3
输出样例
Case #1: 4 ABAB
Case #2: 6 AABB
来自杭电HDUOJ的附加信息
Recommend chendu

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-6347

最后修改于 2020-10-25T23:30:31+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2500/2000MS(Java/Others) 262144/262144K(Java/Others)