记录号 Flag 得分 记录信息 环境 评测机 程序提交时间

R1565183 Accepted 100 From |－

　 P1121 FPC Vivid Puppy 2009-9-28 12:52:52

From zhouyc

马拦过河卒 全国青少年信息学奥林匹克分区联赛 (NOIp) 竞赛原题

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 588ms

├ 测试数据 10：答案正确... 775ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1363ms

呃呃。puppy就是好啊。

编译通过...

├ 测试数据 01：答案正确... 181ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：181ms

郁闷

water

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var

n,m,i,j,x,y:longint;

a:array[-1..15,-1..15]of longint;

begin

readln(n,m,x,y);

for i:=0 to n do

for j:=0 to m do

if ((i=x)and(j=y))or((i=x-1)and(j=y-2))or((i=x-2)and(j=y-1))or((i=x-1)and(j=y+2))

or((i=x-2)and(j=y+1))or((i=x+1)and(j=y-2))or((i=x+2)and(j=y-1))or((i=x+1)and(j=y+2))

or((i=x+2)and(j=y+1))then a:=0

else if (i=0) and(j=0)then a[0,0]:=1

else

a:=a+a;

writeln(a[n,m]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 212ms

├ 测试数据 10：答案正确... 306ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：518ms

郁闷。。遇上两次Sunny，一次70，一次90

DP

Var a,f:array[-1..10000,-1..10000] of LONGINT;

n,m,i,j,x,y:LONGINT;

begin

readln(n,m,x,y);

for i:=0 to n do

for j:=0 to m do

a:=1;

for i:=0 to n do

f:=1;

for j:=0 to m do

f[0,j]:=1;

a[x,y]:=0;

a[x+1,y+2]:=0;

a[x+2,y+1]:=0;

a[x-1,y-2]:=0;

a[x-2,y-1]:=0;

a[x-1,y+2]:=0;

a[x-2,y+1]:=0;

a[x+1,y-2]:=0;

a[x+2,y-1]:=0;

for i:=1 to n do

for j:=1 to m do if a0 then f:=f+f;

if (n=1) and (m=1) then f[n,m]:=1;

writeln(f[n,m]);

end.

第三个点过不去 帮下忙

递推解决。。。。

f[i][j] = f[j] + f[i][j-1];

f[0][j] and f[i][0] 要单独考虑。

当0列或0行有一个被马占了，后面的 f[0][j] = 0;f[i][0]也一样。。。。。

{给新手看的(因为我也是新手)}

用的回溯的方法 最后一组要用990ms的时间

不过这个题是一道很好的深搜或回溯的例题

有兴趣可以来看看解题报告和回溯程序

http://wwzhwdwd.blog.163.com/blog/static/12815145020098185342616

#include

int ok[16][16];

int n,m;

long sum;

void search(int x,int y)

{

if(x==n&&y==m)sum++;

if(x>n||y>m)return;

if(ok[x][y]==1)return;

search(x+1,y);

search(x,y+1);

}

main()

{

int x,y;

int i,j;

scanf("%d%d%d%d",&n,&m,&x,&y);

if(x-2>=0){

if(y+1=0)ok[x-2][y-1]=1;

}

if(x+2=0){

if(y+2=0)ok[x-1][y-2]=1;

}

if(x+1

program dsa;

var a,b,b1,b2,i,j:longint;

f:array[-100..100,-100..100] of int64;

begin

readln(b1,b2,a,b);

for i:=0 to 15 do f:=1;

for i:=0 to 15 do f[0,i]:=1;

f[a+1,b+2]:=0;

f[a+1,b-2]:=0;

f[a-1,b+2]:=0;

f[a-1,b-2]:=0;

f[a+2,b+1]:=0;

f[a+2,b-1]:=0;

f[a-2,b-1]:=0;

f[a-2,b+1]:=0;

f[a,b]:=0;

for i:=1 to b1 do

for j:=1 to b2 do

begin

f:=f+f;

f[a+1,b+2]:=0;

f[a+1,b-2]:=0;

f[a-1,b+2]:=0;

f[a-1,b-2]:=0;

f[a+2,b+1]:=0;

f[a+2,b-1]:=0;

f[a-2,b-1]:=0;

f[a-2,b+1]:=0;

f[a,b]:=0;

end;

writeln(f[b1,b2]);

end.

为什么第3个点没过- - 大牛帮帮忙

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

动态转移方程:f:=f+f;

var a,b,m,n,i,j:longint;

p:array[-1..20,-1..20]of longint;

function place(x,y:longint):boolean;

begin

if ((x=a-2)and(y=b-1))or((x=a-2)and(y=b+1))or

((x=a-1)and(y=b-2))or((x=a-1)and(y=b+2))or

((x=a+2)and(y=b-1))or((x=a+2)and(y=b+1))or

((x=a+1)and(y=b-2))or((x=a+1)and(y=b+2))or

((x=0)and(y=0))or((x=a)and(y=b))

then place:=false

else place:=true;

end;

begin

readln(m,n,a,b);

for i:=-1 to m do

for j:=-1 to n do

p:=0;

p[0,0]:=1;

for i:=0 to m do

for j:=0 to n do

if place(j,i) then p:=p+p;

writeln(p[m,n]);

end.

非常正宗的搜索.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

大家别想太多，红书上的算法很好

其实这个题目有点错误。会下象棋的都知道，兵如果直接走是可以把马给吃掉的。但是题目的测试数据都是要把马的初始点理解为马的控制范围……（注意！）因为这个我第一次给挂了。汗 - -|| 而且我不能理解的是，为什么只能往下和右走啊？？其实是可以往左的，可能是因为题目需要吧。

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|-

program p1121;

var a:array[-5..20,-5..20]of int64;

i,j,n,m,fx,fy,x,y:integer;

begin

readln(fx,fy,x,y);

fillchar(a,sizeof(a),0);

a[x+1,y+2]:=-1;

a[x+2,y+1]:=-1;

a[x+2,y-1]:=-1;

a[x+1,y-2]:=-1;

a[x-1,y-2]:=-1;

a[x-2,y-1]:=-1;

a[x-2,y+1]:=-1;

a[x-1,y+2]:=-1;

a[x,y]:=-1;

for i:=0 to fx+1 do

if a-1 then a:=1 else break;

for i:=0 to fy+1 do

if a[0,i]-1 then a[0,i]:=1 else break;

for i:=1 to fx+1 do

for j:=1 to fy+1 do

if a-1 then

begin

if (a=-1) and (a=-1) then a:=0 else

if a=-1 then a:=a else

if a=-1 then a:=a else

a:=a+a;

end;

writeln(a[fx,fy]);

end.

const

u:array[1..8]of integer=(-2,-1,1,2,2,1,-1,-2);

v:array[1..8]of integer=(1,2,2,1,-1,-2,-2,-1);

var

a:array[0..15,0..15]of longint;

m,n,x,y,i,j:longint;

begin

readln(m,n,x,y);

fillchar(a,sizeof(a),0);

a[x,y]:=-1;

for i:=1 to 8 do

a[x+u[i],y+v[i]]:=-1;

a[0,0]:=1;

for i:=0 to m do

for j:=0 to n do

if (a-1)

then begin

if (i>0)and(a-1)

then a:=a+a;

if (j>0)and(a-1)

then a:=a+a;

end;

writeln(a[m,n]);

end.

一次过。好High!!!!!

动归王道啊

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 509ms

├ 测试数据 10：答案正确... 650ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1159ms

program ex;

const

dx:array[1..2]of longint=(1,0);

dy:array[1..2]of longint=(0,1);

ddx:array[1..8]of longint=(-1,-2,-1,-2, 1, 2,1,2);

ddy:array[1..8]of longint=(-2,-1, 2, 1,-2,-1,2,1);

var

i,j,xb,yb,xm,ym,count:longint;

bo:array[0..21,0..21]of boolean;

procedure dfs(x,y:longint);

var i,j:longint;

begin

if (x=xb)and(y=yb) then

begin

inc(count);

exit;

end;

for i:=1 to 2 do

begin

if bo[x+dx[i],y+dy[i]] then

dfs(x+dx[i],y+dy[i]);

end;

end;

begin

read(xb,yb,xm,ym);

fillchar(bo,sizeof(bo),true);

for i:=0 to xb+1 do bo:=false;

for i:=0 to yb+1 do bo[xb+1,i]:=false;

bo[xm,ym]:=false;

for i:=1 to 8 do

bo[xm+ddx[i],ym+ddy[i]]:=false;

dfs(0,0);

writeln(count);

end.

DFS=AC....

但是其实可以递推的。。。 算了 不写了。。。

DP

f=f+f

注意马能拦的地方

好冂，挂表挂错，组合数学。

var

f:array[-2..20,-2..20] of longint;

tf:array[-5..20,-5..20] of integer;

a1,a2,a3,x1,x2,y1,y2,n,m:longint;

begin

readln(n,m,x2,y2);

fillchar(f,sizeof(f),0);

fillchar(tf,sizeof(tf),0);

tf[x2,y2]:=1; tf[x2-2,y2-1]:=1; tf[x2-2,y2+1]:=1;

tf[x2-1,y2-2]:=1; tf[x2-1,y2+2]:=1; tf[x2+1,y2-2]:=1;

tf[x2+1,y2+2]:=1; tf[x2+2,y2-1]:=1; tf[x2+2,y2+1]:=1;

f[0,0]:=1;

for a1:=0 to n do

for a2:=0 to m do

if (tf[a1,a2]=0)and((a20)or(a10)) then

f[a1,a2]:=f[a1-1,a2]+f[a1,a2-1];

writeln(f[n,m]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 399ms

├ 测试数据 10：答案正确... 508ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：907ms