【NOIP2016】【CJOJ2257】2257 愤怒的小鸟

题目

Description

https://www.luogu.org/problem/show?pid=2831

Kiana最近沉迷于一款神奇的游戏无法自拔。

简单来说,这款游戏是在一个平面上进行的。

有一架弹弓位于(0,0)处,每次Kiana可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如y = ax^2 + bx的曲线,其中a, b是Kiana指定的参数,且必须满足a<0。

当小鸟落回地面(即x轴)时,它就会瞬间消失。

在游戏的某个关卡里,平面的第一象限中有n只绿色的小猪,其中第i只小猪所在的坐标为(xi,yi)。

如果某只小鸟的飞行轨迹经过了(xi,yi),那么第i只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;

如果一只小鸟的飞行轨迹没有经过(xi,yi),那么这只小鸟飞行的全过程就不会对第i只小猪产生任何影响。

例如,若两只小猪分别位于(1, 3 )和(3, 3 )

Kiana可以选择发射一只飞行轨迹为y=-x^2+ 4x的小鸟,这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对Kiana来说都很难,所以Kiana还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有T个关卡,现在Kiana想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

Input

输入格式:

第一行包含一个正整数T,表示游戏的关卡总数。

下面依次输入这T个关卡的信息。每个关卡第一行包含两个非负整数n,m,分别表示该关卡中的小猪数量和Kiana输入的神秘指令类型。接下来的n行中,第i行包含两个正实数(xi,yi),表示第i只小猪坐标为(xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果m=0,表示Kiana输入了一个没有任何作用的指令。

如果m=1,则这个关卡将会满足:至多用只小鸟即可消灭所有小猪。

如果m=2,则这个关卡将会满足:一定存在一种最优解,其中有一只小鸟消灭了至少只小猪。

保证1<=n<=18,0<=m<=2,0< xi,yi<10,输入中的实数均保留到小数点后两位。

上文中,符号和分别表示对c向上取整和向下取整

Output

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数,表示相应的关卡中,消灭所有小猪最少需要的小鸟数量。

题解

题目没有贴全,样例也没有打了(到Luogu上去看)

这道题目。。。。怎么说。。。。其实有点水。

作为Tg的D2T3确实偏简单了一些(T2有毒)







我的思路比较暴力:每次强行枚举任意两只猪,算出其抛物线(判断是否合法),计算出最多能够消灭几只猪(使用状压存状态)。最后再添加一个单独消灭某只猪的DFS。强暴DFS计算。



至于优化,我加了一个记忆化搜索和对ans的剪枝。

这题的思路十分暴力,我在CJOJ上很快就AC了



【NOIP2016】【CJOJ2257】2257 愤怒的小鸟





不知道再别的OJ上是不是AC的(没有试,很可能被卡精度)

希望诸位dalao帮我测一测

如果Wa了,也请各位dalao帮我查一下错误,谢谢了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX=25;
double A,B;
int ans;
int n,m,T;
int f[MAX][(1<<20)];//记忆化
inline void solve(int i,int j);//求解抛物线
struct Pig
{
double x,y;
}P[MAX];
bool operator <(Pig a,Pig b)
{
if(a.x!=b.x)
return a.x<b.x;
else
return a.y<b.y;
}
inline void DFS(int x,int t,int b)//还有x只猪没被消灭,t用来存储消灭情况
{
if(x<=1)//只有一直猪也只接判断
{
ans=min(ans,b+x);//b用来储存鸟的数量
return;
}
if(b>=ans-1)return;
if(f[x][t]!=0)
{
if(b>=f[x][t])return;
else
f[x][t]=b;
}
else
f[x][t]=b;
for(int i=1;i<=n;++i)
{
int tt=t,kk=0;
if((1<<(i-1))&t)//这只猪已经死了
continue;
for(int j=i+1;j<=n;++j)
{
if((1<<(j-1))&t)//这只猪也死了
continue;
tt= t|(1<<(i-1));
tt=tt|(1<<(j-1));
kk=2;
solve(i,j);//求解这两只猪所在的抛物线
if(A>=-0.001||B<=0.001)continue;//不合题意的抛物线
for(int k=1;k<=n;++k)//检查是否有猪在这条抛物线上
{
if(!(tt&(1<<(k-1))))//猪没有死才检查
{
double yy=P[k].x*(A*P[k].x+B);
if(fabs(yy-P[k].y)<=0.0001)//如果能够打死(卡下精度)
{
kk+=1;
tt=tt|(1<<(k-1));
}
// if(yy<=0)//这只鸟已经没了
// break;
}
}
DFS(x-kk,tt,b+1);
}
DFS(x-1,t|(1<<(i-1)),b+1);//单独弄死
} }
int main()
{
cin>>T;
while(T--)
{
memset(f,0,sizeof(f));
cin>>n>>m;
if(m==0)ans=n;
if(m==1)ans=n/3+1;
if(m==2)ans=1+(n-n/3);
for(int i=1;i<=n;++i)
cin>>P[i].x>>P[i].y;
DFS(n,0,0);
cout<<ans<<endl;
}
}
inline void solve(int i,int j)
{
double a1=P[i].x*P[i].x;
double a2=P[j].x*P[j].x;
double b1=P[i].x;
double b2=P[j].x;
double c1=P[i].y;
double c2=P[j].y;
double tt=a1/a2;
a2=a1;b2*=tt;c2*=tt;//把a的系数化成一样的
if(fabs(b2-b1)<=0.001)//不能够除以0
{
B=-1000;
A=+1000;
return;
}
B=(c2-c1)/(b2-b1);//加减消元求B
if(fabs(a1)<=0.001)//不能够除以0
{
B=-1000;
A=+1000;
return;
}
A=(c1-B*b1)/a1;//代入消元求A
}
上一篇:iOS 使用宏定义函数和代码块


下一篇:冒烟测试与BVT测试