NOIP2016 愤怒的小鸟

\(f[i]\) 表示将$ i $集合中所有小鸟都弄掉用的最少抛物线

\(g[i][j]\) 表示在 \(i\)、\(j\)小鸟(由于\(c = 0\),两点确定一条抛物线)建立一条抛物线,可以射掉的集合。

这个\(x\)可以在未射掉的集合中随便找,因为有可能重复枚举,可以规定\(x\)为第一个未射掉的集合,这样就可以做到不重不漏了。

\(f[i\ |\ g[x][j]] = min\{f[i] + 1\}\)

初始状态: \(f[0] = 0\),其余为正无穷。

答案 : \(f[(1 << n) - 1]\)


二次函数复习\(QAQ\):

已知两点\((x_1, y_1), (x_2, y_2)\)在抛物线\(y = ax ^ 2 + bx\),求\(a, b\)的值

先带入:

\(y_1 = ax_1 ^ 2+ bx_1\)

$y_2 = ax_2 ^ 2+ bx_2 $

暴力一点,先移动过去:

$ax_1 ^ 2 = bx_1 - y_1 $①

$ax_2 ^ 2 = bx_2 - y_2 $②

然后对两个式子分别除以\(x_1, x_2\),式子就变成了:

$ax_1 = \frac{y_1}{x_1} - b $①

$ax_2 = \frac{y_2}{x_2} - b $②

然后由② $- $ ①,\(b\)就被我们消掉了:

$a(x_2 - x_1) = \frac{y_2}{x_2} - \frac{y_1}{x_1} $

然后\(a\)就出来了:

\(a = (\frac{y_2}{x_2} - \frac{y_1}{x_1} )/ (x_2 - x_1)\)

\(b\) 就用 ① 带入找就行啦...

\(b = (y_1 - ax_1^2) / x_1\)

不得不说计算机好麻烦\(qwq\)


#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 18, M = 1 << N;
const double eps = 1e-6;
int n, m;
double x[N], y[N];
int f[M], g[N][N];
bool cmp(double a, double b){
    return fabs(a - b) < eps;
}
int main(){
    int T; scanf("%d", &T);
    while(T--){
        memset(f, 0x3f, sizeof f);
        memset(g, 0, sizeof g);
        f[0] = 0;
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%lf%lf", x + i, y + i);
        for(int i = 0; i < n; i++){
            g[i][i] = 1 << i;
            for(int j = 0; j < n; j++){
                if(cmp(x[i], x[j])) continue;
                double a, b;
                a = (y[j] / x[j] - y[i] / x[i]) / (x[j] - x[i]);
                b = (y[i] - a * x[i] * x[i]) / x[i];
                if(a >= 0) continue;
                for(int k = 0; k < n; k++){
                    if(cmp(a * x[k] * x[k] + b * x[k], y[k]))
                        g[i][j] |= 1 << k;
                }
            }
        }
        for(int i = 0; i + 1 < (1 << n); i++){
            int x = 0;
            for(int j = 0; j < n; j++)
                if(!(i >> j & 1)) { x = j; break; }
            
            for(int j = 0; j < n; j++){
                f[i | g[x][j]] = min(f[i | g[x][j]], f[i] + 1);
            }
        }
        printf("%d\n", f[(1 << n) - 1]);
    }
    
    return 0;
}
上一篇:王爽《汇编》检测9.1(1) | 若要使程序中的jmp指令执行后,CS:IP指向程序的第一条指令,在data段中应该定义哪些数据?


下一篇:JZOJ3492数数&&GDOI2018超级异或绵羊——位&&类欧几里得