关于NOI2010成长快乐的一些疑问
  • 板块学术版
  • 楼主封禁用户
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/6/6 20:14
  • 上次更新2023/11/7 01:05:16
查看原帖
关于NOI2010成长快乐的一些疑问
280636
封禁用户楼主2020/6/6 20:14

求大神解答

上个月脑子一热,想用Pascal做成长快乐(P1915)[传送门]

经过一个月的努力打拼,终于……[传送门]

第四个点尝试多次仍然只得了4分,用的是随机化贪心,代码如下???

program nemo4;
{for case 4/10}
const zero=1e-10;
      max=10000000;
type
  ty1=record
    w,x,y,p,q:extended;
  end;
  ty2=record
    t,x,y:extended;
    s:longint;
  end;
var
  v,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);
var
  i,j,tmp1:longint;
  tmp2,m:extended;
begin
  i:=l; j:=r; m:=s[(i+j) >> 1];
  repeat
    while s[i]>m do inc(i);
    while s[j]<m do dec(j);
    if i<=j then
    begin
      tmp1:=sx[i]; sx[i]:=sx[j]; sx[j]:=tmp1;
      tmp2:=s[i]; s[i]:=s[j]; s[j]:=tmp2;
      inc(i); dec(j);
    end;
  until i>j;
  if i<r then sort(i,r);
  if j>l then sort(l,j);
end;
function calc(t:longint; x,y,now:extended):extended;
var
  fx,fy,a,b,c,d,k:extended;
begin
  k:=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
  begin
    if abs(b)<zero then exit(k);
    if -c/b>-zero then k:=-c/b;
  end else
  begin
    if 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);
begin
  inc(tot_s);
  s[tot_s]:=fish[fx].w/sqr(sqr(calc(fx,x,y,now)));
  sx[tot_s]:=fx;
end;
function get_rand:longint;
var
  i,j,k:longint;
begin
  for j:=1 to tot_s do
  if (s[j]-s[j+1])/s[j]>0.031 then break;
  for k:=1 to j do
  if random(maxlongint) and 1=1 then break;
  for i:=1 to k do
  begin
    if random() < exp(-10/t) then break;
  end;
  exit(sx[i]);
end;
procedure main;
var
  now,w,turn:extended;
  now_tot,t,j,i:longint;
begin
  fillchar(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 do
  begin
    tot_s:=0;
    for i:=1 to n do
    if 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 then
  begin
    tot:=now_tot;
    all:=w;
    step:=tmp;
  end;
end;
begin
  assign(input,'nemo4.in'); reset(input);
  assign(output,'nemo4.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 do
  begin
    main;
    dec(t);
  end;
  writeln(tot);
  writeln(all-w0:0:6);
  for i:=1 to tot do
  writeln(step[i].t:0:6,' ',step[i].x:0:6,' ',step[i].y:0:6,' ',step[i].s);
  close(input); close(output);
end.

原谅我是P党 谢谢大佬

2020/6/6 20:14
加载中...