[NOIP 2016 提高组] 愤怒的小鸟

GitHub 跳转原题关系图返回列表

枚举两只小猪反推出一条合法下凹抛物线，把每条抛物线离散成一个覆盖集合，再做最少集合覆盖的状压 DP。

OJ: luogu

题目 ID: P2831

难度:提高+/省选-

标签:状态压缩动态规划几何最小覆盖

日期: 2026-06-21 05:36

题意

每次可以发射一只沿着 y = ax^2 + bx（且 a<0）飞行的小鸟。

如果轨迹经过某只小猪，这只小猪就会被消灭。问最少需要多少只小鸟才能消灭所有小猪。

思路

先看一个小数据回溯：

cpp

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
76
77
78
79
80
81#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-8;

int T;
int n, m_dummy;
double x[20], y[20];
int cover[20][20];
int ans;

bool equal_double(double a, double b) {
    return fabs(a - b) < EPS;
}

void dfs(int mask, int used) {
    if (used >= ans) {
        return;
    }
    if (mask == (1 << n) - 1) {
        ans = min(ans, used);
        return;
    }

    int first = 0;
    while (mask & (1 << first)) {
        first++;
    }

    dfs(mask | (1 << first), used + 1);
    for (int j = 0; j < n; j++) {
        if (cover[first][j]) {
            dfs(mask | cover[first][j], used + 1);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据回溯选下一条抛物线。
    cin >> T;
    while (T--) {
        cin >> n >> m_dummy;
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i];
        }

        for (int i = 0; i < n; i++) {
            cover[i][i] = 1 << i;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                cover[i][j] = 0;
                if (equal_double(x[i], x[j])) {
                    continue;
                }
                double a = (y[i] / x[i] - y[j] / x[j]) / (x[i] - x[j]);
                if (a >= -EPS) {
                    continue;
                }
                double b = y[i] / x[i] - a * x[i];
                int mask = 0;
                for (int k = 0; k < n; k++) {
                    double yy = a * x[k] * x[k] + b * x[k];
                    if (equal_double(yy, y[k])) {
                        mask |= 1 << k;
                    }
                }
                cover[i][j] = mask;
            }
        }

        ans = n;
        dfs(0, 0);
        cout << ans << '\n';
    }
    return 0;
}

正解的关键不是直接搜索抛物线，而是先把“有意义的抛物线”离散出来。

注意到一条过原点的二次函数 y=ax^2+bx，只要再给出两只小猪，就能唯一确定 a,b。

所以可以枚举两只小猪 i,j：

解出对应的 a,b
若 a<0，说明这是一条合法轨迹
再检查这条轨迹还能经过哪些小猪

这样每条合法抛物线都会对应到一个覆盖集合 cover[i][j]。

接下来就是状压 DP：

dp[mask] 表示消灭 mask 这些小猪最少需要多少只小鸟

DP 转移方程

设 cover[first][j] 表示一条经过 first 和 j 的合法抛物线能消灭的小猪集合，则：

dp[mask \mid cover[first][j]] =\min(dp[mask \mid cover[first][j]],\ dp[mask]+1)

如果只单独打一只 first，就把 cover[first][j] 换成 1<<first。

转移时，找到第一只还没被打掉的猪 first：

可以单独打一只它
或者枚举另一只猪 j，用 cover[first][j] 一次打一批

因为任意最优方案中的一条抛物线，只要能打一只以上的猪，就一定会在某个 cover[i][j] 中出现，所以不会漏解。

代码

cpp

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
76
77
78
79
80
81
82
83
84
85
86
87#include <bits/stdc++.h>
using namespace std;

const double EPS = 1e-8;

int T;
int n, m_dummy;
double x[20], y[20];
int cover[20][20];
int dp[1 << 18];

bool equal_double(double a, double b) {
    return fabs(a - b) < EPS;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> m_dummy;
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> y[i];
        }

        for (int i = 0; i < n; i++) {
            cover[i][i] = 1 << i;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                cover[i][j] = 0;
                if (equal_double(x[i], x[j])) {
                    continue;
                }

                double a = (y[i] / x[i] - y[j] / x[j]) / (x[i] - x[j]);
                if (a >= -EPS) {
                    continue;
                }
                double b = y[i] / x[i] - a * x[i];

                int mask = 0;
                for (int k = 0; k < n; k++) {
                    double yy = a * x[k] * x[k] + b * x[k];
                    if (equal_double(yy, y[k])) {
                        mask |= 1 << k;
                    }
                }
                cover[i][j] = mask;
            }
        }

        int full = 1 << n;
        for (int mask = 0; mask < full; mask++) {
            dp[mask] = n;
        }
        dp[0] = 0;

        for (int mask = 0; mask < full; mask++) {
            if (dp[mask] >= n) {
                continue;
            }
            int first = -1;
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i))) {
                    first = i;
                    break;
                }
            }
            if (first == -1) {
                continue;
            }

            dp[mask | (1 << first)] = min(dp[mask | (1 << first)], dp[mask] + 1);
            for (int j = 0; j < n; j++) {
                if (cover[first][j]) {
                    dp[mask | cover[first][j]] = min(dp[mask | cover[first][j]], dp[mask] + 1);
                }
            }
        }

        cout << dp[full - 1] << '\n';
    }
    return 0;
}

复杂度

预处理 $O(n^3)$ ，状压 DP 约 $O(n 2^n)$ 。

总结

这题的核心是把几何问题离散化成集合覆盖问题。一旦把抛物线预处理成覆盖集合，后面的部分就是标准状压 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P2831 [NOIP 2016 提高组] 愤怒的小鸟

题目背景

NOIP2016 提高组 D2T3

题目描述

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$ 。

输出格式

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

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

输入输出样例 #1

输入 #1

text

输出 #1

text

1
21
1

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

输出 #3

text

说明/提示

【样例解释1】

这组数据中一共有两个关卡。

第一个关卡与【问题描述】中的情形相同， $2$ 只小猪分别位于 $(1.00,3.00)$ 和 $(3.00,3.00)$ ，只需发射一只飞行轨迹为 $y = -x^2 + 4x$ 的小鸟即可消灭它们。

第二个关卡中有 $5$ 只小猪，但经过观察我们可以发现它们的坐标都在抛物线 $y = -x^2 + 6x$ 上，故 Kiana 只需要发射一只小鸟即可消灭所有小猪。

【数据范围】

测试点编号	$n\leqslant$	$m=$	$T\leqslant$
$1$	$2$	$0$	$10$
$2$	$2$	$0$	$30$
$3$	$3$	$0$	$10$
$4$	$3$	$0$	$30$
$5$	$4$	$0$	$10$
$6$	$4$	$0$	$30$
$7$	$5$	$0$	$10$
$8$	$6$	$0$	$10$
$9$	$7$	$0$	$10$
$10$	$8$	$0$	$10$
$11$	$9$	$0$	$30$
$12$	$10$	$0$	$30$
$13$	$12$	$1$	$30$
$14$	$12$	$2$	$30$
$15$	$15$	$0$	$15$
$16$	$15$	$1$	$15$
$17$	$15$	$2$	$15$
$18$	$18$	$0$	$5$
$19$	$18$	$1$	$5$
$20$	$18$	$2$	$5$

[NOIP 2016 提高组] 愤怒的小鸟

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析