P2831 愤怒的小鸟

题目链接

题目描述

Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说,这款游戏是在一个平面上进行的。

有一架弹弓位于 $(0,0)$ 处,每次 Kiana 可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 $y=ax^2+bx$ 的曲线,其中 $a,b$ 是 Kiana 指定的参数,且必须满足 $a < 0$,$a,b$ 都是实数。

当小鸟落回地面(即 $x$ 轴)时,它就会瞬间消失。

在游戏的某个关卡里,平面的第一象限中有 $n$ 只绿色的小猪,其中第 $i$ 只小猪所在的坐标为 $\left(x_i,y_i \right)$。

如果某只小鸟的飞行轨迹经过了 $\left( x_i, y_i \right)$,那么第 $i$ 只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;

如果一只小鸟的飞行轨迹没有经过 $\left( x_i, y_i \right)$,那么这只小鸟飞行的全过程就不会对第 $i$ 只小猪产生任何影响。

例如,若两只小猪分别位于 $(1,3)$ 和 $(3,3)$,Kiana 可以选择发射一只飞行轨迹为 $y=-x^2+4x$ 的小鸟,这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana来说都很难,所以Kiana还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有 $T$ 个关卡,现在 Kiana想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

输入格式

第一行包含一个正整数 $T$,表示游戏的关卡总数。

下面依次输入这 $T$ 个关卡的信息。每个关卡第一行包含两个非负整数 $n,m$,分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 $n$ 行中,第 $i$ 行包含两个正实数 $x_i,y_i$,表示第 $i$ 只小猪坐标为 $(x_i,y_i)$。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果 $m=0$,表示 Kiana 输入了一个没有任何作用的指令。

如果 $m=1$,则这个关卡将会满足:至多用 $\lceil n/3 + 1 \rceil$ 只小鸟即可消灭所有小猪。

如果 $m=2$,则这个关卡将会满足:一定存在一种最优解,其中有一只小鸟消灭了至少 $\lfloor n/3 \rfloor$ 只小猪。

保证 $1\leq n \leq 18$,$0\leq m \leq 2$,$0 < x_i,y_i < 10$,输入中的实数均保留到小数点后两位。

上文中,符号 $\lceil c \rceil$ 和 $\lfloor c \rfloor$ 分别表示对 $c$ 向上取整和向下取整,例如:$\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。

输出格式

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数,表示相应的关卡中,消灭所有小猪最少需要的小鸟数量。

题解

这是一道十足的搜索好题,可以用于练习 bfs。

首先做简单的数学推导,推出经过 $(x_1,y_1)$,$(x_2,y_2)$ 的抛物线

用二进制表示第 $i$ 个猪是否被打到(状态压缩)

每次通过极角序排序每个点,作为枚举顺序,最后 $\mathcal{O}(2^n)$ 枚举 $\mathcal{O}(n^2)$ 查询,最终时间复杂度 $\mathcal{O}(2^nn^2)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 18;
const int MAXP = (1 << MAXN) + 20;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
struct Point {
db x, y;
Point(db _x = 0, db _y = 0) : x(_x), y(_y) {}
bool operator<(const Point &rhs) const { return y * rhs.x < rhs.y * x; }
};
int n, m, _;
int d[MAXP];
Point pigs[MAXN];
inline void solve(db &a, db &b, db x1, db y1, db x2, db y2) {
b = (y1 * x2 * x2 - y2 * x1 * x1) / x1 / x2 / (x2 - x1);
a = (y1 - b * x1) / x1 / x1;
}
int q[MAXP], qhead = 0, qtail = 0;
// bfs 加入新的状态
inline void extend(int u, int v) {
if (d[v] == INF) {
d[v] = d[u] + 1;
q[qtail++] = v;
}
}
inline int bfs(int s) {
d[s] = 0;
qhead = qtail = 0;
q[qtail++] = s;
while (qhead != qtail) {
int now = q[qhead++];
if (now == (1 << n) - 1)
return d[now];
int p0 = 0; // 当前第一只没有被打到的猪
for (int t = now; t & 1; t >>= 1) p0++;
extend(now, now | (1 << p0));
for (int i = p0 + 1; i < n; i++) {
db a, b;
// 极角排序后不能打出向上的曲线
if (pigs[i].x + 0.0001 > pigs[p0].x)
continue;
// 也不能是一条直线
if (fabs(pigs[i].x / pigs[i].y - pigs[p0].x / pigs[p0].y) < eps)
continue;
solve(a, b, pigs[p0].x, pigs[p0].y, pigs[i].x, pigs[i].y);
// p0 和 i 代表的猪我们都打到了
int to = now | (1 << p0) | (1 << i);
// 找一找有没有恰好也被我们打到的猪
for (int j = i + 1; j < n; j++) {
db delta = fabs(a * pigs[j].x * pigs[j].x + b * pigs[j].x - pigs[j].y);
if (delta < eps) {
to |= 1 << j;
}
}
extend(now, to);
}
}
}
int main() {
for (scanf("%d", &_); _; _--) {
scanf("%d%d", &n, &m);
memset(d, 0x3f, sizeof(d));
for (int i = 0; i < n; i++) {
db x, y;
scanf("%lf%lf", &x, &y);
pigs[i] = Point(x, y);
}
sort(pigs, pigs + n);
printf("%d\n", bfs(0));
}
return 0;
}

注意

  1. 抛物线不能是上凸的
  2. 抛物线不能是一条直线
  3. 要检查是否有本身不准备打但是最后经过了的猪

  4. 多组数据要清空

文章作者: answerend42
文章链接: http://answerend42.github.io/2020/11/15/lg2831/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 answerend42的Blog