题解【P2831】 愤怒的小鸟

· · 题解

愤怒的小鸟 题解

1. 考场上的思路：

对于给出的任意一点(x,y)，我们可以把它代入到关系式中ax^2+bx=y，即x^2 a+xb-y=0，化成一条直线，在这条直线的坐标系中，横轴表示a，纵轴表示b。

那么我们如果把所有的这些直线全部画出来，那么把取(a,b)为这些直线的交点之一，再把所有的这些符合a<0的点全部列出来，优先挑选那些有更多直线经过的点（选中这些点能够一次性消灭更多小猪）即可。

然而这个贪心算法只适用于n\le3的情况，于是只有20分……

#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN=20;
int t,n,m,ans;
double x[MAXN],y[MAXN],z[MAXN];
bool b[MAXN];
struct Point{
    pair<double,double> p;
    int cnt;
};
bool operator < (Point a,Point b)
{
    return a.cnt<b.cnt;
}
set<pair<double,double> > s;
map<pair<double,double>,int> cp;
map<pair<double,double>,vector<pair<int,int> > > lp;
map<int,vector<pair<int,int> > > ltp;
priority_queue<Point> q;
pair<double,double> solve (double o1,double p1,double q1,double o2,double p2,double q2){
    if (o1*p2-o2*p1==0||o2*p1-o1*p2==0) return make_pair(1,0);
    else return make_pair((p1*q2-p2*q1)/(o1*p2-o2*p1),(o1*q2-o2*q1)/(o2*p1-o1*p2));
}
inline void setup()
{
    ans=0;
    memset(x,0,sizeof(x));
    memset(y,0,sizeof(y));
    memset(z,0,sizeof(z));
    memset(b,0,sizeof(b));
    s.clear();
    cp.clear();
    lp.clear();
    ltp.clear();
    while (!q.empty()) q.pop();
}
int main(){
    //freopen("in.txt","r",stdin);
    freopen("angrybirds.in","r",stdin);
    freopen("angrybirds.out","w",stdout);
    scanf("%d",&t);
    while (t--){
        setup();
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
        {
            double x0,y0;
            scanf("%lf%lf",&x0,&y0);
            x[i]=x0*x0,y[i]=x0,z[i]=-y0;
        }
        for (int i=1;i<=n;i++)
            for (int j=i+1;j<=n;j++)
            {
                pair<double,double> ans=solve(x[i],y[i],z[i],x[j],y[j],z[j]);
                //printf("%lf %lf\n",ans.first,ans.second);
                if (ans.first<0) s.insert(ans),cp[ans]++,lp[ans].push_back(make_pair(i,j)),ltp[i].push_back(ans),ltp[j].push_back(ans);
            }
        //putchar('\n');
        for (set<pair<double,double> >::iterator i=s.begin();i!=s.end();i++)
        {
            //printf("%lf %lf\n",(*i).first,(*i).second);
            Point tmp;
            tmp.p=*i,tmp.cnt=cp[*i];
            q.push(tmp);
        }
        int maxv=0; pair<double,double> maxp;
        /*vector<Point>::iterator x;
        while (q.size())
        {
            int c=0;
            for (vector<Point>::iterator i=q.begin();i!=q.end();i++)
                if ((*i).cnt>maxv) x=i,maxv=(*i).cnt,maxp=(*i).p;
            for (vector<pair<int,int> >::iterator i=lp[maxp].begin();i!=lp[maxp].end();i++)
            {
                if (!b[(*i).first])
                {
                    b[(*i).first]=true,c++;
                }
                if (!b[(*i).second])
                {
                    b[(*i).second]=true,c++;
                }
            }
            if (c!=0) ans++;
            q.erase(x);
        }*/
        while (!q.empty())
        {
            Point x=q.top(); q.pop();
            int c=0;
            for (vector<pair<int,int> >::iterator i=lp[x.p].begin();i!=lp[x.p].end();i++)
            {
                if (!b[(*i).first])
                {
                    b[(*i).first]=true,c++;
                }
                if (!b[(*i).second])
                {
                    b[(*i).second]=true,c++;
                }
            }
            if (c==0) continue;
            else ans++;
        }
        for (int i=1;i<=n;i++)
            if (!b[i]) ans++;
        printf("%d\n",ans);
    }
}

2. 自己琢磨的时候

我们可以使用动态规划来完成所有情况的考虑：我们可以设状态f[x]，将x进行二进制拆分（状态压缩），其中对于任意第i位为1，则表示第i头小猪被消灭。

如何判断当前的选择能够消灭多少小猪？分析跟考场上的分析是一样的，只是最后用的是动态规划求最优解而已。

状态转移方程：

f_{i|para_j}=min\{f_i+1\}

初值：f_i=Inf

目标：f_{2^n-1}

附源代码：

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;
const int MAXN=1e5+10;
const int MAXM=7e6+10;
typedef long long ll;
ll n,m,q,u,v,t,cnt;
ll delta;
ll a[MAXN];
queue <ll> Q,q1,q2;
bool cmp(ll a,ll b)
{
    return a>b;
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
    for (int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+1+n,cmp);
    for (int i=1;i<=n;i++)
        Q.push(a[i]);
    for (int i=1;i<=m;i++)
    {
        ll t1,t2,t0,res,x1,x2;
        t0=t1=t2=res=-inf;
        if (!Q.empty()) t0=Q.front();
        if (!q1.empty()) t1=q1.front();
        if (!q2.empty()) t2=q2.front();
        res=max(t0,max(t1,t2));
        if (!Q.empty()&&res==t0) Q.pop();
        else if (!q1.empty()&&res==t1) q1.pop();
        else if (!q2.empty()&&res==t2) q2.pop();
        res=res+delta;
        x1=floor((ll)u*res/v); x2=res-floor((ll)u*res/v);
        q1.push(x1-delta-q);
        q2.push(x2-delta-q);
        delta+=q;
        if (cnt<floor(i/t)) cnt++,printf("%lld ",res);
    }
    putchar('\n');
    cnt=0;
    for (int i=1;i<=n+m;i++)
    {
        ll t1,t2,t0,res;
        t0=t1=t2=res=-inf;
        if (!Q.empty()) t0=Q.front();
        if (!q1.empty()) t1=q1.front();
        if (!q2.empty()) t2=q2.front();
        res=max(t0,max(t1,t2));
        if (!Q.empty()&&res==t0) Q.pop();
        else if (!q1.empty()&&res==t1) q1.pop();
        else if (!q2.empty()&&res==t2) q2.pop();
        res=res+delta;
        if (cnt<floor(i/t)) cnt++,printf("%lld ",res);
    }
}