最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【环球速看料】[NOIP2016提高组] 愤怒的小鸟

来源：博客园


(资料图)

洛谷传送门AcWing

解题思路

\(\qquad\)这题可以转化为一个重复覆盖问题，由于三个点可以确定一条抛物线，而这里的抛物线必定经过原点，所以可以用不是原点的两个点确定一条抛物线。

\(\qquad\)对于一个覆盖情况我们可以用一个二进制数 state表示，其中从右往左从 \(0\) 开始编号，第 \(i\) 位是 \(1\) 的时候表示打中了，反之没打中。\(\qquad\)然后我们可以爆搜所有状态，知道一个状态全部为 \(1\)，也就是 \((1 << n) - 1\)，表示所有的猪都被打中了。对于一个非终点状态，我们找到第一个为 \(0\) 的数，然后枚举所有经过这个点的抛物线，从中间取出一个最小的答案就可以了。

\(\qquad\)为此我们可以进行一些预处理：定义path[i][j]为经过i,j两点的抛物线状态，也是同样用二进制压缩，和state类似，第 \(i\) 位是 \(1\)代表经过，反之没经过。

\(\qquad\)有了path数组之后，我们对于每个状态的转移枚举图上的所有点，新状态也就是老状态和path[x][i]作或运算，就可以很容易地进行转移了。

\(\qquad\)这里提供两种实现方式：爆搜+剪枝和记忆化搜索

爆搜

#include #include #include #include using namespace std;const int N = 20, M = 1 << 18;int n, m, T, res, path[N][N], f[M];struct Point { double x, y; } p[N];int cmp(double a, double b) {if (fabs(a - b) <= 1e-6) return 0; // =return 1;}void calc(int i, int j) {    if (path[i][j]) return ;double r1 = p[i].x, c1 = p[i].y;double r2 = p[j].x, c2 = p[j].y;double a = (c1 / r1 - c2 / r2) / (r1 - r2);double b = c1 / r1 - a * r1;if (a >= 0) return ; // 开口不朝下if (!cmp(r1, r2)) return ; // 垂直点对for (int k = 0; k < n; k ++ ) {double rk = p[k].x, ck = p[k].y;double t = rk * rk * a + b * rk;if (!cmp(t, ck)) path[i][j] |= 1 << k;}path[j][i] = path[i][j];}void dfs(int st, int cnt){    if (f[st] <= cnt) return ;    if (st == (1 << n) - 1) return void (res = min(res, cnt));if (cnt >= res - 1) return ;int x;for (x = 0; x < n; x ++ )if (!(st >> x & 1)) break;for (int i = 0; i < n; i ++ ) if (path[x][i] && cnt + 1 < res) dfs(st | path[x][i], cnt + 1);f[st] = min(f[st], cnt);}void solve() {memset(f, 0x3f, sizeof f);    memset(path, 0, sizeof path);    res = 2e9;scanf("%d%d", &n, &m); // m 是无用条件for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &p[i].x, &p[i].y);for (int i = 0; i < n; i ++ ) {path[i][i] = 1 << i;for (int j = i + 1; j < n; j ++ ) calc(i, j);}dfs(0, 0);printf("%d\n", res);}int main() {scanf("%d", &T);while (T -- ) solve();return 0;}

记忆化搜索

#include #include #include #include #define x first#define y secondusing namespace std;using PDD = pair ;const int N = 20, M = 1 << 18;int n, m, T, res, path[N][N];PDD p[N];int cmp(double a, double b) {return fabs(a - b) > 1e-6; }void calc(int i, int j) {    if (path[i][j]) return ;double r1 = p[i].x, c1 = p[i].y;double r2 = p[j].x, c2 = p[j].y;double a = (c1 / r1 - c2 / r2) / (r1 - r2);double b = c1 / r1 - a * r1;if (a >= 0) return ; // 开口不朝下if (!cmp(r1, r2)) return ; // 垂直点对for (int k = 0; k < n; k ++ ) {double rk = p[k].x, ck = p[k].y;double t = rk * rk * a + b * rk;if (!cmp(t, ck)) path[i][j] |= 1 << k;}path[j][i] = path[i][j];}int dfs(int st, vector &f) {     int &v = f[st];    if (st == (1 << n) - 1)  return 0;    if (v) return v;    int x;    for (x = 0; x < n; x ++ )        if ((st >> x & 1) == 0) break ;            int res = 2e9;    for (int i = 0; i < n; i ++ )         if (path[x][i]) res = min(dfs(st | path[x][i], f) + 1, res) ;            return v = res;}void solve() {res = 2e9;vector f(M, 0);scanf("%d%d", &n, &m); // m 是无用条件for (int i = 0; i < n; i ++ ) scanf("%lf%lf", &p[i].x, &p[i].y);for (int i = 0; i < n; i ++ ) {path[i][i] = 1 << i;for (int j = i + 1; j < n; j ++ ) calc(i, j);}printf("%d\n", dfs(0, f));    memset(path, 0, sizeof path);}int main() {scanf("%d", &T);while (T -- ) solve();return 0;}

个人实测爆搜会快一点，只要 \(81ms\)

关键词： 二进制数 愤怒的小鸟 也是同样