题解 P2831 【愤怒的小鸟】

juruo_zjc · 2019-10-13 17:04:54 · 题解

write 题解 makes me 快乐

这道题狠友疑似，索易我酒赖血以偏题解。

（这道题很有意思，所以我就来写一篇题解）

题目内容很简单，用一些抛物线来覆盖题目给出的一些点。题目中还提到一点，那就是van这个游戏的van家还可以用一些指令，但是，你略一思索就会发现，我们是奔着正解而去的，但我们不是为了骗分！这些指令根本没有啥么用。

首先，我们知道，如果我们知道了一个抛物线上的两个点，那么我们一定可以确定这条抛物线，对吧？

我们先考虑这一点。

设抛物线上的一点为x_i,y_i，另外一点为x_j,y_j。

那我们于是列出方程：

我们先在第一个等式两边各乘上x_j，第二个等式两边各乘上x_i。

我们于是显然地发现，等式两边变得very lovely，都有公共项bx_jx_i，所以我们将两个等式相减。

于是我们将(x_j^2-x_ix_j^2)除到左式，得：

我们求出了a！那么我们以同样方式求出b：

首先我们先要将a的项消掉，第一个等式乘上x_j^2，第二个等式两边各乘上x_i^2：

两式相减：

于是，我们只要知道抛物线上的两个点，我们必然能够求出抛物线方程y=ax^2+by中a,b的值。

那么程序下面给出：

void equation(double &a,double &b,int i,int j){
    a=-(y[i]*x[j]-y[j]*x[i])/(x[j]*x[j]*x[i]-x[i]*x[i]*x[j]);
    b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*x[j]-x[j]*x[i]*x[i]);
}

上面是比较偏数学的部分了，下面我们讲一些偏计算机的内容吧！

首先，我们明确一下目标，我们做这道题的方法是状态压缩，什么意思呢？比如说：

我们以11这个数为例，

先将其分解成2进制：000000000000001011

那么他表示什么呢？

他表示我们将1,2,4这几只小pig打掉，因为第1,2,4的位置上，11这个数的这些二进制位是1。我们用1表示这只小猪被打掉。这就是我们的状态压缩思路。

现在我们来看这个程序中的一个奇妙的初始化。

for(int i=0;i<(1<<18);i++){
    int j=1;
    for(;j<=18&&i&(1<<(j-1));j++);
    start[i]=j;
}

可以理解吗？首先我们穷举每一个状态，从000000000000000000到111111111111111111

对于每一个状态，我们从他的第一位开始穷举，i&(1<<(j-1))意思就是i这个状态的第j头pig是否被打掉。于是start[i]的意思就是i这个状态内第一个0的位置，也就是我们做dp的起始位置。

这个优化节省了我们很多时间复杂度。

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++){
        if(fabs(x[i]-x[j])<eps) continue;
            double a,b;
            equation(a,b,i,j);
            if(a>-eps) continue;
            for(int k=1;k<=n;k++)
                if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps)
                curve[i][j]|=(1<<(k-1));
            }

这段程序我们来讲一讲。

首先我们穷举每两个点，然后运用我们一开始讲的通过两个抛物线上点求抛物线a,b参数方程的方法，求出a和b，如果a大于我们的eps（eps是精度，10^{-8})其实也就是大于0，那么抛物线的开口方向就是向上的。

想想，要是这个样子的话，牛老爷（牛顿）估计都要从棺材里跑出来了！

然后我们穷举每个点，然后看看这个点是否会在这一条抛物线中被打掉。那么我们的判断条件是怎么来的呢？

若y=ax^2+bx那么移项后：ax_i^2+bx-y=0如果这个等式成立，这个点就是可以被打掉的。我们将它存在curve[i][j]中，curve[i][j]表示经过i，j的抛物线能够打掉的状态。

for(int i=0;i<(1<<n);i++){
    int j=start[i];
    dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1); 
    for(int k=1;k<=n;k++)
        dp[i|lines[j][k]]=min(dp[i|lines[j][k]],dp[i]+1); 
}

首先，我们开始操作的点是start[i]，我们先将它预先转移一下，就是j这头猪被打掉的状态等于他被打掉的状态的最小抛物线数，和目前状态的最小抛物线数量加上一条打下次头pig。

然后穷举1~n每一头猪，然后后转移这头猪打掉他的最小抛物线数量。

printf("%d\n",dp[(1<<n)-1]);

最后输出所有猪被打掉的情况的最小抛物线数量。

最后给一个标程吧！

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
int T,n,m,lines[19][19],start[1<<19],dp[1<<19];
double x[19],y[19];
void equation(double &a,double &b,int i,int j){
    a=-(y[i]*x[j]-y[j]*x[i])/(x[j]*x[j]*x[i]-x[i]*x[i]*x[j]);
    b=(y[i]*x[j]*x[j]-y[j]*x[i]*x[i])/(x[i]*x[j]*x[j]-x[j]*x[i]*x[i]);
}
int main(){
    for(int i=0;i<(1<<18);i++){
        int j=1;
        for(;j<=18 && i&(1<<(j-1));j++);
        start[i]=j;
    }
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        memset(lines,0,sizeof(lines));
        memset(dp,1,sizeof(dp));
        dp[0]=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lf%lf",x[i],y[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(fabs(x[i]-x[j])<eps) continue;
                double a,b;
                equation(a,b,i,j);
                if(a>-eps) continue;
                for(int k=1;k<=n;k++)
                    if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps)
                        lines[i][j]|=(1<<(k-1));
            }
        for(int i=0;i<(1<<n);i++){
            int j=start[i];
            dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1); 
            for(int k=1;k<=n;k++)
                dp[i|lines[j][k]]=min(dp[i|lines[j][k]],dp[i]+1); 
        }
        printf("%d\n",dp[(1<<n)-1]);
    }
    return 0;
}

不要抄袭哦 欢迎copy

最后弱弱地希望大家给个赞，顶一顶，这一篇题解写的比较仔细哦！