[NOI2010]：成长快乐

传送门
目前30 at 12.14
话说洛谷此题样例错了，而且第二个点是第十个点。。。
首先第一个点可以手算，10分
第二个点爆搜：

#include
#include
#include
#include
#include
#define ll long long
#define min(a,b) a
#define max(a,b) a>b?a:b
using namespace std;
const int N=1e5+5;
const double eps=1e-12;
struct Point{double x,y;Point(){}Point(double _x,double _y):x(_x),y(_y){}inline Point operator + (const Point& b) const {return Point(x+b.x,y+b.y);}inline Point operator - (const Point& b) const {return Point(x-b.x,y-b.y);}inline Point operator * (double b) const {return Point(x*b,y*b);}
}nemo,P[N],v[N];
inline int dcmp(double x){if(fabs(x)return 0;return x>eps?1:-1;
}
inline double dis(const Point& a,const Point& b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double dis2(const Point& a,const Point& b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
inline double Dot(const Point& a,const Point& b){return a.x*b.x+a.y*b.y;}
inline double Mod(const Point& a){return sqrt(Dot(a,a));}
inline double Mod2(const Point& a){return Dot(a,a);}
int n,s[N],use[N];
double w0,V,T,w[N];
double maxw;
int ans[N],anscnt;
double tm[N],anstm[N];
Point pos[N],anspos[N];
inline double solve(double a,double b,double c){double d=b*b-4.0*a*c;if(dcmp(d)<0)return -1;d+=eps;d=sqrt(d);double x1=(-b+d)/(2.0*a),x2=(-b-d)/(2.0*a);double x=max(x1,x2);if(x<0)return -1;if(x1<0)x1=1e9;if(x2<0)x2=1e9;x=min(x1,x2);return x;
}
inline void dfs(int cnt,double noww,double nowt,Point now){if(nowt>T)return;if(noww>maxw){for(int i=1;ifor(int i=1;ifor(int i=1;iif(cnt>n)return;for(int i=1;i<=n;i++){if(use[i])continue;if(w[i]>=noww+eps)continue;Point B=P[i]+v[i]*nowt,A=now;double a=Mod2(v[i])-V*V;double b=-2.0*Dot(v[i],A-B);double c=dis2(A,B);double tmp=solve(a,b,c);if(tmp==-1)continue;use[i]=1;s[cnt]=i;tm[cnt]=tmp+nowt;pos[cnt]=B+v[i]*tmp;dfs(cnt+1,noww+w[i],nowt+tmp,pos[cnt]);use[i]=0;}
}
int main(){freopen("nemo2.in","r",stdin);freopen("nemo2.out","w",stdout);scanf("%lf %lf %lf %lf %lf",&w0,&V,&T,&nemo.x,&nemo.y);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf %lf %lf %lf %lf",&w[i],&P[i].x,&P[i].y,&v[i].x,&v[i].y);dfs(1,w0,0,nemo);printf("%d\n",anscnt-1);printf("%.6lf\n",maxw-w0);for(int i=1;iprintf("%.6lf %.6lf %.6lf %d\n",anstm[i],anspos[i].x,anspos[i].y,ans[i]);return 0;
}

第三个点因为每次只能吃一个，所以排序然后模拟即可：

#include
#include
#include
#include
#include
#define ll long long
#define min(a,b) a
#define max(a,b) a>b?a:b
using namespace std;
const int N=1e5+5;
const double eps=1e-12;
struct Point{double x,y;Point(){}Point(double _x,double _y):x(_x),y(_y){}inline Point operator + (const Point& b) const {return Point(x+b.x,y+b.y);}inline Point operator - (const Point& b) const {return Point(x-b.x,y-b.y);}inline Point operator * (double b) const {return Point(x*b,y*b);}
}nemo,P[N],v[N];
struct fish{Point pos,v;double w;int id;
}F[N];
inline bool cmp(const fish& a,const fish& b){return a.winline int dcmp(double x){if(fabs(x)return 0;return x>eps?1:-1;
}
inline double dis(const Point& a,const Point& b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double dis2(const Point& a,const Point& b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
inline double Dot(const Point& a,const Point& b){return a.x*b.x+a.y*b.y;}
inline double Mod(const Point& a){return sqrt(Dot(a,a));}
inline double Mod2(const Point& a){return Dot(a,a);}
int n,s[N],use[N];
double w0,V,T,w[N];
double tm[N];
Point pos[N];
inline double solve(double a,double b,double c){double d=b*b-4.0*a*c;if(dcmp(d)<0)return -1;d+=eps;d=sqrt(d);double x1=(-b+d)/(2.0*a),x2=(-b-d)/(2.0*a);double x=max(x1,x2);if(x<0)return -1;if(x1<0)x1=1e9;if(x2<0)x2=1e9;x=min(x1,x2);return x;
}
int main(){freopen("nemo4.in","r",stdin);freopen("nemo4.out","w",stdout);scanf("%lf %lf %lf %lf %lf",&w0,&V,&T,&nemo.x,&nemo.y);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lf %lf %lf %lf %lf",&F[i].w,&P[i].x,&P[i].y,&v[i].x,&v[i].y),F[i].pos=P[i],F[i].v=v[i],F[i].id=i;sort(F+1,F+n+1,cmp);int cnt=1;double noww=w0,nowt=0;Point now=nemo;for(int i=1;i<=n;i++){Point B=F[i].pos+F[i].v*nowt,A=now;double a=Mod2(F[i].v)-V*V;double b=-2.0*Dot(F[i].v,A-B);double c=dis2(A,B);double tmp=solve(a,b,c);s[cnt]=F[i].id;tm[cnt]=tmp+nowt;pos[cnt]=B+F[i].v*tmp;noww+=F[i].w;nowt+=tmp;now=pos[cnt];cnt++;}printf("%d\n",cnt-1);printf("%.6lf\n",noww-w0);for(int i=1;iprintf("%.6lf %.6lf %.6lf %d %.6lf\n",tm[i],pos[i].x,pos[i].y,s[i],F[i].w);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！