大家AK杯 灰天飞雁NOIP模拟赛题解/数据/标程

数据

http://files.cnblogs.com/htfy/data.zip

简要题解

桌球碰撞

纯模拟，注意一开始就在袋口和v=0的情况。v和坐标可以是小数。为保险起见最好用extended/double类型。

program prob1;

var
 ans:array[0..6,0..600] of longint;
 n,i,j:longint;
 a0,r0,px,py,vx,vy,left,t,newp:extended;
 flag:boolean;

function dist(x1,y1,x2,y2:extended):extended;inline;begin exit( sqrt(sqr(x1-x2)+sqr(y1-y2))); end;
function store(num:longint;x,y:extended):boolean;inline;
  begin
  //writeln('x=',x,' y=',y);
  //readln;
  if x=0 then
    if (y>=0) and (y<=r0) then
      begin
      inc(ans[1,0]);
      ans[1,ans[1,0]]:=num;
      exit(true);
    end else
    if (y>=5-r0) and (y<=5) then
      begin
      inc(ans[4,0]);
      ans[4,ans[4,0]]:=num;
      exit(true);
    end;

  if x=10 then
    if (y>=0) and (y<=r0) then
      begin
      inc(ans[3,0]);
      ans[3,ans[3,0]]:=num;
      exit(true);
    end else
    if (y>=5-r0) and (y<=5) then
      begin
      inc(ans[6,0]);
      ans[6,ans[6,0]]:=num;
      exit(true);
    end;

  if y=0 then
    if (x>=0) and (x<=r0) then
      begin
      inc(ans[1,0]);
      ans[1,ans[1,0]]:=num;
      exit(true);
    end else
    if (x>=5-r0) and (x<=5+r0) then
      begin
      inc(ans[2,0]);
      ans[2,ans[2,0]]:=num;
      exit(true);
    end else
    if (x>=10-r0) and (x<=10) then
      begin
      inc(ans[3,0]);
      ans[3,ans[3,0]]:=num;
      exit(true);
    end;

  if y=5 then
    if (x>=0) and (x<=r0) then
      begin
      inc(ans[4,0]);
      ans[4,ans[4,0]]:=num;
      exit(true);
    end else
    if (x>=5-r0) and (x<=5+r0) then
      begin
      inc(ans[5,0]);
      ans[5,ans[5,0]]:=num;
      exit(true);
    end else
    if (x>=10-r0) and (x<=10) then
      begin
      inc(ans[6,0]);
      ans[6,ans[6,0]]:=num;
      exit(true);
    end;
  exit(false);
end;

  begin

  readln(n,r0,a0);
  fillchar(ans,sizeof(ans),0);
  for i:=1 to n do
    begin
    //writeln('i=',i, ' ');
    readln(px,py,vx,vy);

    left:=(vx*vx+vy*vy)/(2*a0);
    if (vx=vy) and (vx=0) then begin {writeln('inti');}store(i,px,py); continue; end;
    //process
    while left>=0 do
      begin
      if store(i,px,py) then break;
      flag:=false;

      if vx<0 then
        begin
        t:=px/(-vx);
        newp:=t*vy+py;
        if (newp>=0) and (newp<=5) then
          begin
          flag:=true;
          left:=left-dist(px,py,0,newp);
          px:=0;
          py:=newp;
          vx:=-vx;
        end;
      end else
      if vx>0 then
        begin
        t:=(10-px)/(vx);
        newp:=t*vy+py;
        if (newp>=0) and (newp<=5) then
          begin
          flag:=true;
          left:=left-dist(px,py,10,newp);
          px:=10;
          py:=newp;
          vx:=-vx;
        end;
      end;

      if (vy>0) and not flag then
        begin
        t:=(5-py)/vy;
        newp:=t*vx+px;
        if (newp>=0) and (newp<=10) then
          begin
          flag:=true;
          left:=left-dist(px,py,newp,5);
          px:=newp;
          py:=5;
          vy:=-vy;
        end;
      end else
      if vy<0 then
        begin
        t:=py/(-vy);
        newp:=t*vx+px;
        if (newp>=0) and (newp<=10) then
          begin
          flag:=true;
          left:=left-dist(px,py,newp,0);
          px:=newp;
          py:=0;
          vy:=-vy;
        end;
      end;

    end;
  end;
  for i:=1 to 6 do
    begin
    write(ans[i,0]);
    if ans[i,0]<>0 then write(' ');
    for j:=1 to ans[i,0] do
      if j<ans[i,0] then write(ans[i,j],' ') else write(ans[i,j]);
    writeln;
  end;

end.

旋转圆盘

DP，设F[t,i,j]为第t时刻到达第i层第j块的最大得分和。

则F[t,i,j]=w[i,j]+Max{

F[t-1,i,j]//不动

,F[t-1,i,prev(j)]//从前面走过来

,F[t-1,i,next(j)]//从后面走过来

,F[t-1,i-1,j]//从上面跳下来

,F[t-2,i-1,k]+w[i-1,k] (k<>j) //从上面转后跳下来

}

注意到最后一种情况若朴素查找Max{f[t-2,i-1,k] k<>j}则会使转移代价成为O(m)，从而整个程序的复杂度会达到O(tn m^2)从而TLE

我们可以记录每一个t,i下F[t,i,k]的最大值、最大值时的maxk 和 除最大值以外的F[t,i,k]_max(k<>maxk)

这样我们就可以在O(1)时间内得到Max{f[t-2,i-1,k] k<>j}了

注意到W较大，用int64存储

用滚动数组压缩空间，滚动数组mod 3较慢，不如直接mod 4=and 3快

program prob2;

var
 t0,n,m,i,j,t:longint;
 ans:int64;
 a:array[0..300,0..300] of int64;
 f:array[-2..3,-2..300,-2..300] of int64;
 max1,max2,pos1,pos2:array[-2..3,-2..300] of int64;

function prev(P:int64):int64;inline; begin if p=m then exit(1) else exit(p+1); end;
function next(P:int64):int64;inline; begin if p=1 then exit(m) else exit(p-1); end;
function max(a,b:int64):int64;inline; begin if a>b then exit(a);exit(b); end;

  begin

  readln(n,m,t0);
  for i:=1 to n do
    begin
    for j:=1 to m do
      read(a[i,j]);
    readln;
  end;

  fillchar(f,sizeof(f),$81);
  //max1[t0,i] max2 pos1 pos2
  fillchar(max1,sizeof(max1),$81);
  fillchar(max2,sizeof(max2),$81);

  f[0,1,1]:=0;
  for t:=1 to t0 do
    for i:=1 to n do
      begin
      max1[t and 3,i]:=-maxlongint;max2[t and 3,i]:=-maxlongint;
      for j:=1 to m do
        begin
        f[t and 3,i,j]:=f[(t-1) and 3,i,j];
        f[t and 3,i,j]:=max(f[(t-1) and 3,i,j],f[(t-1) and 3,i,prev(j)]);
        f[t and 3,i,j]:=max(f[t and 3,i,j],f[(t-1) and 3,i,next(j)]);
        f[t and 3,i,j]:=max(f[t and 3,i,j],f[(t-1) and 3,i-1,j]);
        if j<>pos1[(t-2) and 3,i-1] then f[t and 3,i,j]:=max(f[t and 3,i,j],max1[(t-2) and 3,i-1]+a[i-1,pos1[(t-2) and 3,i-1]]) else
          f[t and 3,i,j]:=max(f[t and 3,i,j],max2[(t-2) and 3,i-1]+a[i-1,pos2[(t-2) and 3,i-1]]);

        f[t and 3,i,j]:=f[t and 3,i,j]+a[i,j];

        if f[t and 3,i,j]>max1[t and 3,i] then begin max1[t and 3,i]:=f[t and 3,i,j];pos1[t and 3,i]:=j; end
        else
        if f[t and 3,i,j]>max2[t and 3,i] then begin max2[t and 3,i]:=f[t and 3,i,j];pos2[t and 3,i]:=j; end;

      end;
  end;

  ans:=-maxlongint;
  for i:=1 to n do
    for j:=1 to m do
      ans:=max(ans,f[t0 and 3,i,j]);
  writeln(ans);

end.

弹幕游戏

直接输出0或1什么的都有30分入账（HT：所以说这是水题模拟赛）

正解是对抗搜索。甲是Max游戏者 乙是Min游戏者

alpha-beta减枝考虑到这是noip模拟赛就没加（其实是因为出不出来卡朴素的数据）（跑了一个上午的对拍器没找到合理的数据）

细节很多，自己看代码吧

program prob3;

Const
  TLEFT=1;
  TRIGHT=2;
  TUP=3;
  TDOWN=4;
  PLAYERA=false;
  PLAYERB=true;
  dx:array[1..5] of longint=(-1,1,0,0,0);
  dy:array[1..5] of longint=(0,0,1,-1,0);
  illegal=$1235;//不合法状态，用一个够大的数标记

Type

 TBullet=record//子弹定义
   x,y,dir:integer;//x y 子弹坐标 dir运动方向,详见前
   ava:boolean;//是否要继续处理子弹的运动,如果已经跑到外面了就赋ava=false
 end;
 TSelfState=record
   top,sx,sy,ax,ay,bx,by:longint;//一个游戏者的状态 包含了小怪的位置和自机位置和子弹栈
   bullet:array[0..55] of TBullet;
 end;
 TState=record
   pa,pb:TSelfState;//状态 包含了甲乙游戏者的两个网格
   score,t:integer;
 end;

Var
 now:TState;
 t0:longint;
 q:array[0..20,false..true] of longint;

Function max(a,b:longint):longint;inline;begin if a>b then exit(a);exit(b); end;
Function min(a,b:longint):longint;inline;begin if a<b then exit(a);exit(b); end;

Function missed(var ss:TselfState):boolean;inline;//判断一个网格内是否已经中弹
var
 i:longint;
  begin
  with ss do
    begin
    if (sx=ax) and (sy=ay) then exit(true);//撞到小怪了
    if (sx=bx) and (sy=by) then exit(true);
    for i:=1 to top do
      if bullet[i].ava and (sx=bullet[i].x) and (sy=bullet[i].y) then exit(true);//撞到子弹了
    exit(false);
  end;
end;

procedure createbullet(var ss:TselfState;px,py,pdir:longint);inline;//在一个游戏者的网格中创建子弹
  begin
  if not((px>=1) and (px<=5) and (py>=1) and (py<=6)) then exit;//子弹在外面不用创建了
  inc(ss.top);
  with ss.bullet[ss.top] do
    begin
    dir:=pdir;
    x:=px;
    y:=py;
    ava:=true;
  end;
end;

procedure movebullet(var ss:TselfState);inline;//子弹的移动
var
 i:longint;
  begin
  for i:=1 to ss.top do
    with ss.bullet[i] do
      if ava then
        begin
        x:=x+dx[dir];
        y:=y+dy[dir];
        if not((x>=1) and (x<=5) and (y>=1) and (y<=6)) then ava:=false;//子弹到外面就不用处理了
      end;
end;

procedure createmoz(var ss:TselfState;pt:longint);inline;//创建小怪的子弹
  begin
  if odd(pt) then //奇数秒 a小怪产生子弹
    begin
    createbullet(ss,ss.ax+1,ss.ay,TRIGHT);
    createbullet(ss,ss.ax-1,ss.ay,TLEFT);
    createbullet(ss,ss.ax,ss.ay-1,TDOWN);
  end else
    begin //偶数秒 b小怪产生子弹
    createbullet(ss,ss.bx+1,ss.by,TRIGHT);
    createbullet(ss,ss.bx-1,ss.by,TLEFT);
    createbullet(ss,ss.bx,ss.by-1,TDOWN);
  end;

end;

function expand(player:boolean;apro:longint):boolean;inline;//apro 操作方式 1左 2右 3上 4下 5ATK 返回表示该操作是否合法 若合法即改写状态
  begin

  if player=PLAYERA then
  with now.pa do
    begin
    if (sx=5) and (apro=2) then exit(false);
    if (sx=1) and (apro=1) then exit(false);
    if (sy=1) and (apro=4) then exit(false);
    if (sy=6) and (apro=3) then exit(false); //在边界还需要向外移动肯定不合法
    if missed(now.pa) then dec(now.score); //中弹判定
    if apro<5 then begin sx:=sx+dx[apro];sy:=sy+dy[apro]; end else//需要移动的情况
      begin //产生子弹的情况
      createbullet(now.pb,sx-1,sy+2,TDOWN);
      createbullet(now.pb,sx,sy+2,TDOWN);
      createbullet(now.pb,sx+1,sy+2,TDOWN);
    end;
    movebullet(now.pa);//子弹移动
    createmoz(now.pa,now.t); //产生小怪子弹
    //inc(now.t);  a游戏者操作后回合数不会+1~
    exit(true);
  end;

  if player=PLAYERB then
  with now.pb do
    begin
    if (sx=5) and (apro=2) then exit(false);
    if (sx=1) and (apro=1) then exit(false);
    if (sy=1) and (apro=4) then exit(false);
    if (sy=6) and (apro=3) then exit(false);
    if missed(now.pb) then inc(now.score);
    if apro<5 then begin sx:=sx+dx[apro];sy:=sy+dy[apro]; end else
      begin
      createbullet(now.pa,sx-1,sy+2,TDOWN);
      createbullet(now.pa,sx,sy+2,TDOWN);
      createbullet(now.pa,sx+1,sy+2,TDOWN);
    end;
    movebullet(now.pb);
    createmoz(now.pb,now.t);
    inc(now.t); //b操作完后回合数+1
    exit(true);
  end;

end;

function search(dpt:longint;player:boolean):longint;
var
 i,o:longint;
 oldnow:Tstate;
  begin
  q[dpt,player]:=illegal;
  search:=illegal;
  if dpt=t0+1 then
    exit(now.score);
  oldnow:=now;
  for i:=1 to 5 do
    begin
    now:=oldnow;
    if not expand(player,i) then continue;
    if player=playera then o:=search(dpt,not player) else o:=search(dpt+1,not player);
    if o<>illegal then
      if search=illegal then
        search:=o
      else
      if player=playera then //轮到a行动,他会找分差最大的方案
        search:=max(search,o)
      else
        search:=min(search,o);//b行动,分差最小的方案
    q[dpt,player]:=search;

    if player=playera then //alpha-beta剪枝
      begin
      if (search>q[dpt-1,not player]) and (q[dpt-1,not player]<>illegal) then exit;
    end else
      if (search<q[dpt,not player]) and (q[dpt,not player]<>illegal) then exit;
  end;
end;

  begin
  readln(t0);
  filldword(q,sizeof(q) div 4,illegal);
  with now.pa do
    begin
    top:=0;
    readln(sx,sy,ax,ay,bx,by);
  end;
  with now.pb do
    begin
    top:=0;
    readln(sx,sy,ax,ay,bx,by);
  end;
  now.score:=0;
  now.t:=1;
  writeln(search(1,playera));

end.