【NOI2010】 成长快乐

这里存放这道题的程序，题解在：http://blog.sina.com.cn/s/blog_86942b1401015c3u.html

case 1： 手算。

case 2：搜索

program nemo4;
{for case 2}
const zero=1e-10;max=10000000;
typety1=recordw,x,y,p,q:extended;end;ty2=recordt,x,y:extended;s:longint;end;varv,w,x,y,tot_t,all:extended;n,i,tot:longint;fish:array[0..10000] of ty1;step,tmp:array[0..10000] of ty2;get:array[0..10000] of boolean;
//==============================
procedure find(s:longint; x,y,w,now:extended);
varj:longint;a,b,c,d,fx,fy,t:extended;
beginif (s=n+1)or(now-tot_t>zero) then exit;for j:=1 to n doif not get[j] and (fish[j].w-w<-zero) thenbeginfx:=fish[j].x+fish[j].p*now;fy:=fish[j].y+fish[j].q*now;a:=sqr(v)-sqr(fish[j].p)-sqr(fish[j].q);b:=2*fish[j].p*(x-fx)+2*fish[j].q*(y-fy);c:=-sqr(x-fx)-sqr(y-fy);t:=max;if abs(a)-zero then t:=-c/b;end elsebeginif sqr(b)-4*a*c<-zero then continue;d:=(-b+sqrt(sqr(b)-4*a*c))/(2*a);if d>-zero then t:=d;d:=(-b-sqrt(sqr(b)-4*a*c))/(2*a);if (d>-zero)and(d>t) then t:=d;end;if t-max>-zero then continue;tmp[s+1].x:=fx+fish[j].p*t;tmp[s+1].y:=fy+fish[j].q*t;tmp[s+1].s:=j;tmp[s+1].t:=now+t;get[j]:=true;find(s+1,tmp[s+1].x,tmp[s+1].y,w+fish[j].w,now+t);get[j]:=false;end;if all-w<-zero thenbegintot:=s; all:=w;for j:=1 to s do step[j]:=tmp[j];end;
end;
//==============================
beginassign(input,'nemo2.in'); reset(input);assign(output,'nemo2.out'); rewrite(output);read(w,v,tot_t,x,y);read(n); tot:=0; all:=0;for i:=1 to n do read(fish[i].w,fish[i].x,fish[i].y,fish[i].p,fish[i].q);find(0,x,y,w,0);writeln(tot);writeln(all-w:0:6);for i:=1 to tot dowriteln(step[i].t:0:6,' ',step[i].x:0:6,' ',step[i].y:0:6,' ',step[i].s);close(input); close(output);
end.

case 3：模拟：

program nemo3;
{for case 3}
const zero=1e-10;max=100000000;
typety1=recordw,x,y,p,q:extended;end;ty2=recordt,x,y:extended;s:longint;end;varv,w,x,y,tot_t,a,b,c,d,now,time,all:extended;n,i,j,t,tot:longint;fish:array[0..10000] of ty1;step:array[0..10000] of ty2;dis:array[0..10000] of extended;get:array[0..10000] of boolean;
//==============================
beginassign(input,'nemo3.in'); reset(input);assign(output,'nemo3.out'); rewrite(output);read(w,v,tot_t,x,y);read(n); time:=0; tot:=0; all:=0;for i:=1 to n do read(fish[i].w,fish[i].x,fish[i].y,fish[i].p,fish[i].q);for i:=1 to n dobeginfor j:=1 to n do dis[j]:=max;for j:=1 to n doif not get[j] and (fish[j].w-w<-zero) thenbegina:=sqr(v)-sqr(fish[j].p)-sqr(fish[j].q);b:=2*fish[j].p*(x-fish[j].x)+2*fish[j].q*(y-fish[j].y);c:=-sqr(x-fish[j].x)-sqr(y-fish[j].y);if abs(a)-zero then dis[j]:=d;d:=(-b-sqrt(sqr(b)-4*a*c))/(2*a);if d>-zero then dis[j]:=d;end;end;now:=max; t:=0;for j:=1 to n doif not get[j] and (fish[j].w-w<-zero) and (now-dis[j]>zero) thenbegint:=j;now:=dis[j];end;if t=0 then break;time:=time+now;if time-tot_t>zero then break;get[t]:=true;inc(tot);step[tot].x:=fish[t].x+fish[t].p*now;step[tot].y:=fish[t].y+fish[t].q*now;step[tot].s:=t;step[tot].t:=time;x:=step[tot].x; y:=step[tot].y;w:=w+fish[t].w;all:=all+fish[t].w;for j:=1 to n doif not get[j] thenbeginfish[j].x:=fish[j].x+fish[j].p*now;fish[j].y:=fish[j].y+fish[j].q*now;end;end;writeln(tot);writeln(all:0:6);for i:=1 to tot dowriteln(step[i].t:0:6,' ',step[i].x:0:6,' ',step[i].y:0:6,' ',step[i].s);close(input); close(output);
end.

case 4 and 10：随机化贪心

program nemo5;
{for case 4/10}
const zero=1e-10;max=10000000;
typety1=recordw,x,y,p,q:extended;end;ty2=recordt,x,y:extended;s:longint;end;
varv,w0,x0,y0,tot_t,all,x,y:extended;n,tot,i,tot_s,t:longint;fish:array[0..10000] of ty1;step,tmp:array[0..10000] of ty2;get:array[0..10000] of boolean;sx:array[0..10000] of longint;s:array[0..10000] of extended;
//==============================
procedure sort(l,r:longint);
vari,j,tmp1:longint;tmp2,m:extended;
begini:=l; j:=r; m:=s[(i+j) >> 1];repeatwhile s[i]>m do inc(i);while s[j]j;if il then sort(l,j);
end;
//==============================
function calc(t:longint; x,y,now:extended):extended;
varfx,fy,a,b,c,d,k:extended;
begink:=max;fx:=fish[t].x+now*fish[t].p;fy:=fish[t].y+now*fish[t].q;a:=sqr(v)-sqr(fish[t].p)-sqr(fish[t].q);b:=2*fish[t].p*(x-fx)+2*fish[t].q*(y-fy);c:=-sqr(x-fx)-sqr(y-fy);if abs(a)-zero then k:=-c/b;end elsebeginif sqr(b)-4*a*c<-zero then exit(k);d:=(-b+sqrt(sqr(b)-4*a*c))/(2*a);if d>-zero then k:=d;d:=(-b-sqrt(sqr(b)-4*a*c))/(2*a);if (d>-zero)and(d>k) then k:=d;end;exit(k);
end;
//==============================
procedure insert(fx:longint; now:extended);
begininc(tot_s);s[tot_s]:=fish[fx].w/sqr(sqr(calc(fx,x,y,now)));sx[tot_s]:=fx;
end;
//==============================
function get_rand:longint;
vari,j,k:longint;
beginfor j:=1 to tot_s doif (s[j]-s[j+1])/s[j]>0.031 then break;for k:=1 to j doif random(maxlongint) and 1=1 then break;for i:=1 to k dobeginif random() < exp(-10/t) then break;end;exit(sx[i]);
end;
//==============================
procedure main;
varnow,w,turn:extended;now_tot,t,j,i:longint;
beginfillchar(get,sizeof(get),0);fillchar(tmp,sizeof(tmp),0);now:=0; now_tot:=0; x:=x0; y:=y0; w:=w0;for j:=1 to n dobegintot_s:=0;for i:=1 to n doif not get[i] and(fish[i].w-w<-zero) then insert(i,now);sort(1,tot_s);if tot_s<1 then break;t:=get_rand;turn:=calc(t,x,y,now);if turn>max-1000 then continue;now:=now+turn;if now-tot_t>zero then break;get[t]:=true;inc(now_tot);tmp[now_tot].x:=fish[t].x+fish[t].p*now;tmp[now_tot].y:=fish[t].y+fish[t].q*now;tmp[now_tot].s:=t;tmp[now_tot].t:=now;x:=tmp[now_tot].x; y:=tmp[now_tot].y;w:=w+fish[t].w;end;if w>all thenbegintot:=now_tot;all:=w;step:=tmp;end;
end;
//==============================
beginassign(input,'nemo10.out'); reset(input);readln(tot); readln(all);for i:=1 to tot doread(step[i].t,step[i].x,step[i].y,step[i].s);close(input);assign(input,'nemo10.in'); reset(input);assign(output,'nemo10.out'); rewrite(output);randomize;read(w0,v,tot_t,x0,y0);read(n); all:=all+w0;for i:=1 to n do read(fish[i].w,fish[i].x,fish[i].y,fish[i].p,fish[i].q);t:=20;while t>0 dobeginmain;dec(t);end;writeln(tot);writeln(all-w0:0:6);for i:=1 to tot dowriteln(step[i].t:0:6,' ',step[i].x:0:6,' ',step[i].y:0:6,' ',step[i].s);close(input); close(output);
end.

case 5/6：接元宝

program nemo6;
{for case 5/6}
const zero=1e-10;
typety1=recordw,x,y,p,q:extended;end;ty2=recordt,x,y:extended;s:longint;end;
varv,w0,x0,y0,tot_t,all,best:extended;n,tot,i,j,t:longint;fish:array[0..10000] of ty1;step:array[0..10000] of ty2;f,fall:array[0..10000] of extended;sa,g:array[0..10000] of longint;
//====================
procedure sort(l,r:longint);
vari,j,tmp1:longint;tmp2,m:extended;
begini:=l; j:=r; m:=fall[(i+j) >> 1];repeatwhile fall[i]m do dec(j);if i<=j thenbegintmp2:=fall[i]; fall[i]:=fall[j]; fall[j]:=tmp2;tmp1:=sa[i]; sa[i]:=sa[j]; sa[j]:=tmp1;inc(i); dec(j);end;until i>j;if il then sort(l,j);
end;
//====================
function check(l,r:longint):boolean;
beginif abs(fish[sa[l]].x-fish[sa[r]].x)/v+fall[l]-fall[r]>zero then exit(false);exit(true);
end;
//====================
procedure huisu(x:longint);
beginif g[x]>0 then huisu(g[x]);inc(tot);all:=all+fish[sa[x]].w;step[tot].s:=sa[x];step[tot].x:=fish[sa[x]].x;step[tot].t:=fall[x];
end;
//====================
beginassign(input,'nemo6.in'); reset(input);assign(output,'nemo6.out'); rewrite(output);randomize;read(w0,v,tot_t,x0,y0);read(n); all:=0;for i:=1 to n dobeginread(fish[i].w,fish[i].x,fish[i].y,fish[i].p,fish[i].q);fall[i]:=abs(fish[i].y-y0)/abs(fish[i].q);sa[i]:=i;end;sort(1,n);for i:=1 to n do f[i]:=-100000000;f[0]:=0;for i:=1 to n dobeginfor j:=0 to i-1 doif check(j,i) and (f[i]

program nemo2;
{for case7/8}
uses math;
typety=recordt,x,y:extended;s:int64;end;varn,tx,tot,p,q,maxq,ans,wi:int64;i,j:longint;w,v,t,x0,y0,time:extended;fash,id:array[0..2000,0..2000] of int64;step:array[0..2000] of ty;f,g:array[0..2000,0..2000] of int64;
//===============================
procedure huisu(x,y:int64);
beginif x>1 then huisu(x-1,g[x,y]);inc(tot);//writeln(x,' ',y);time:=time+sqrt(sqr(x-y0)+sqr(y-x0))/v;step[tot].t:=time;step[tot].x:=y; step[tot].y:=x;x0:=y; y0:=x;step[tot].s:=id[x,y];
end;
//===============================
beginassign(input,'nemo7.in'); reset(input);assign(output,'nemo7.out'); rewrite(output);read(w,v,t,x0,y0);read(n);fillchar(fash,sizeof(fash),$fe);for i:=1 to n dobeginread(wi);read(p,q); fash[q,p]:=wi;id[q,p]:=i;if maxqf[i-1,j-1] thenbeginf[i,j]:=f[i-1,j+1]+fash[i,j];g[i,j]:=j+1;end elsebeginf[i,j]:=f[i-1,j-1]+fash[i,j];g[i,j]:=j-1;end;for i:=0 to 2000 doif ans

program nemo;
{for case 9}
const max=10000000;zero=1e-6;
typety1=recordw,x,y,p,q:extended;end;ty2=recordt,x,y:extended;s:longint;end;
varw,x,y,v,tot_t,now_t,ans,d:extended;n,i,j,t,tot:longint;f:array[0..10000] of ty1;get:array[0..10000] of boolean;step:array[0..10000] of ty2;
//============================
function dis(i:longint; x,y:extended):extended;
beginexit(sqrt(sqr(x-f[i].x)+sqr(y-f[i].y)));
end;
//============================
beginassign(input,'nemo9.in'); reset(input);assign(output,'nemo9.out'); rewrite(output);read(w,v,tot_t,x,y);read(n); ans:=0; tot:=0; now_t:=0;fillchar(get,sizeof(get),false);for i:=1 to n do read(f[i].w,f[i].x,f[i].y,f[i].p,f[i].q);for i:=1 to n dobegind:=max; t:=0;for j:=1 to n doif not get[j] and (f[j].w-w<-zero) and (dis(j,x,y)zero then break;get[t]:=true;w:=w+f[t].w;ans:=ans+f[t].w;inc(tot);step[tot].t:=now_t;step[tot].s:=t;step[tot].x:=f[t].x;step[tot].y:=f[t].y;x:=f[t].x; y:=f[t].y;end;writeln(tot);writeln(ans:0:6);for i:=1 to tot dowriteln(step[i].t:0:6,' ',step[i].x:0:6,' ',step[i].y:0:6,' ',step[i].s);close(input); close(output);
end.

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