数据
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.