题目大意：第一象限上有 $n$ 只小猪，第 $i$ 只小猪的坐标为 $(x_i,y_i)$，每一只小鸟的起点为 $(0,0)$，飞行路线为 $a_ix^2+b_ix$，其中 $a_i,b_i$ 是自定义的参数，且 $a_i<0$，每一只小鸟会消灭所有在它飞行路线上的小猪，问消灭全部的小猪最少使用多少只小鸟？$n \leq 18, 0 <x_i,y_i<10$
$O(\sum\limits_{i=1}^{n}S(n,i))$
$dfs$ 每个元素所在的集合，即枚举当前元素在前面的哪一个集合里，并判断在不在该集合元素组成的抛物线上，或者自己单独新开一个集合，$n=12$ 时，复杂度最多为 $O(4213597)$，期望得分 $70$。
$O(2^nn^2)$
预处理出任意两个点与原点所构成的抛物线，因为我们所用到的飞行路线只可能在这些抛物线中产生，设 $g[i]$ 表示第 $i$ 条抛物线经过了哪几头猪。
然后 $1 \cdots 2^n$ 枚举打下的猪的状态，设 $f[i]$ 表示打下状态 $i$ 的猪最少需要多少只鸟，有状态转移方程：
即 $f[i]$ 最多再用一只鸟就可以转移到 $f[i|g[j]]$。
实现需要注意以下几点：
- 预处理任意两点的抛物线时，如果两点的横坐标相等，应直接 $continue$，不然就会整数被零除然后RE
- 对于不能与其他任何点在同一抛物线上的点，最后不要忘记单独一个抛物线加到 $g$ 数组里
- 多组数据注意初始化
#include <cstdio>
#include <cstring>
struct Node {
double x, y;
} c[20];
int f[262150], g[400], vis[20], n, m;
int min(int x, int y) {
return x < y ? x : y;
}
int dcmp(double x, double y) {
if (x - y >= 0.00000001) return 1;
if (y - x >= 0.00000001) return -1;
return 0;
}
void calc(double x1, double y1, double x2, double y2) {
double a = (x2 * y1 - x1 * y2) / (x1 * x2 * (x1 - x2));
if (a >= 0) return;
double b = y1 / x1 - a * x1; ++g[0];
for (int i = 1; i <= n; ++i)
if (dcmp(a * c[i].x * c[i].x + b * c[i].x, c[i].y) == 0)
g[g[0]] |= 1 << i - 1, vis[i] = 1;
}
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lf%lf", &c[i].x, &c[i].y);
memset(g, 0, sizeof g); //不要忘记memset
memset(vis, 0, sizeof vis);
for (int i = 1; i < n; ++i) //预处理抛物线
for (int j = i + 1; j <= n; ++j)
if (c[i].x != c[j].x) calc(c[i].x, c[i].y, c[j].x, c[j].y); //横坐标相等直接判掉
for (int i = 1; i <= n; ++i) //一个点单独一个抛物线的情况
if (!vis[i]) g[++g[0]] = 1 << i - 1;
int tot = (1 << n) - 1;
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 0; i <= tot; ++i) //枚举状态
for (int j = 1; j <= g[0]; ++j) //枚举抛物线
f[i|g[j]] = min(f[i|g[j]], f[i] + 1);
printf("%d\n", f[tot]);
}
return 0;
}
$O(2^nn)$
由于我们只想得到 $f[2^n-1]$ 的值，因此中间状态的结果是无所谓的，比如下面的转移：
我们只关心 $f[7]$ 的值，因此上面两种转移任选一种即可。
设 $g[i][j]$ 表示第 $i,j$ 只猪与原点构成的抛物线经过了哪些猪，那么每次转移 $f[i]$ 的时候，找到第一只状态 $i$ 不包含的猪 $j$，只进行 $f[i|g[j][k]]=\min(f[i|g[j][k]],f[i]+1)$ 的转移即可，其中 $k=j \cdots n$。
这样转移的正确性在于它满足了以下两种条件：
- 必要性：当前状态至少多扩展 $1$ 只猪，那么就要把这只猪的所有可能的抛物线都转移一次，因此 $k=j \cdots n$
- 充分性：由于扩展完一只猪后，扩展后的状态还会继续扩展，因此只扩展一只猪就足够
比上面的写法整整快了 $4$ 倍多。
#include <cstdio>
#include <cstring>
struct Node {
double x, y;
} c[20];
int f[262150], g[20][20], n, m;
int min(int x, int y) {
return x < y ? x : y;
}
int dcmp(double x, double y) {
if (x - y >= 0.00000001) return 1;
if (y - x >= 0.00000001) return -1;
return 0;
}
void calc(int p, int q, double x1, double y1, double x2, double y2) {
double a = (x2 * y1 - x1 * y2) / (x1 * x2 * (x1 - x2));
if (a >= 0) return;
double b = y1 / x1 - a * x1;
for (int i = 1; i <= n; ++i)
if (dcmp(a * c[i].x * c[i].x + b * c[i].x, c[i].y) == 0)
g[p][q] |= 1 << i - 1;
}
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lf%lf", &c[i].x, &c[i].y);
memset(g, 0, sizeof g);
for (int i = 1; i < n; ++i) //预处理抛物线
for (int j = i + 1; j <= n; ++j)
if (c[i].x != c[j].x) calc(i, j, c[i].x, c[i].y, c[j].x, c[j].y);
for (int i = 1; i <= n; ++i) //一个点单独一个抛物线的情况
g[i][i] = 1 << i - 1;
int tot = (1 << n) - 1;
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 0; i <= tot; ++i) //枚举状态
for (int j = 1; j <= n; ++j) //枚举第一个不包含的点
if (!(i & (1 << j - 1))) {
for (int k = j; k <= n; ++k)
f[i|g[j][k]] = min(f[i|g[j][k]], f[i] + 1);
break;
}
printf("%d\n", f[tot]);
}
return 0;
}
$random\text{_}shuffle$
$random\text{_}shuffle$ 太NB了……过了 $95$ 分!!! QAQ
思路：$random\text{_}shuffle$ 所有猪的编号，每次尝试把第 $r[i]$ 只猪与第 $r[i-1]$ 只猪放到一个抛物线上，如果不能放就让 $r[i]$ 新开一个抛物线。
需要注意，本题是多组数据，$n$ 不同，因此每次都要初始化一遍 $random$ 数组
#include <cstdio>
#include <algorithm>
#include <ctime>
const int maxn = 2e7, inf = 0x3f3f3f3f;
struct Node {
double x, y;
} c[20];
double a[20], b[20];
int r[20];
int min(int x, int y) {
if (x <= y) return x; return y;
}
int dcmp(double x, double y) {
if (x - y >= 0.00000001 || y - x >= 0.00000001) return 1;
return 0;
}
int calc(int p, double x1, double y1, double x2, double y2) {
if (x1 == x2) return 0;
if (a[p]) {
if (dcmp(a[p] * x2 * x2 + b[p] * x2, y2) == 0) return 1;
return 0;
}
a[p] = (x2 * y1 - x1 * y2) / (x1 * x2 * (x1 - x2));
if (a[p] >= 0) return 0;
b[p] = y1 / x1 - a[p] * x1;
return 1;
}
int main() {
srand(time(0));
int T; scanf("%d", &T);
for (int t = 1; t <= T; ++t) {
int n, m, ans = inf;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) r[i] = i; //不要忘记初始化random数组
for (int i = 1; i <= n; ++i) scanf("%lf%lf", &c[i].x, &c[i].y);
int times = maxn / T / n;
while (times--) {
std::random_shuffle(r + 1, r + n + 1);
int fa[20] = {}, cnt = 0;
fa[1] = cnt = 1;
for (int i = 1; i <= n; ++i) a[i] = b[i] = 0;
for (int i = 2; i <= n; ++i) {
if (calc(fa[i-1], c[r[i-1]].x, c[r[i-1]].y, c[r[i]].x, c[r[i]].y))
fa[i] = fa[i-1];
else fa[i] = i, ++cnt;
}
ans = min(ans, cnt);
}
printf("%d\n", ans);
}
return 0;
}