题解 - Vijos

0

张厚 LV 3 @ 2009-01-13 18:50:50

系统正在处理您的请求请勿刷新此页……

您有新消息

请点击这里进入消息中心

15 / 137 (11%) 　首页站务公告　|　题库/分类/原题记录比赛团队交流讨论　|　U-Space 搜索换肤正體顯示　|　登出

公告 News >> 　　关于Vijos被黑的声明 (2008-12-8 22:16:46) 　　关于近期Vijos被挂马的说明 (2008-12-4 22:15:23) 　　CSC WorkGroup 邀请赛IV 评测完毕 (2008-11-12 23:33:35) 　　首届海峡两岸青少年程序设计大赛大陆地区邀请赛完成评测 (2008-11-9 1:01:22) 　　海峡两岸程序设计大赛将延期举行 (2008-10-25 22:56:19)

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

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

R1113058 Unaccepted 20 From 张厚－

　 P1011 FPC Vivid Puppy 2009-1-13 18:48:16

From Vivian Snow

清帝之惑之顺治清帝之惑系列各省青少年信息学奥林匹克竞赛 (Provincial OI) 竞赛原题

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 03：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

Unaccepted 有效得分：20 有效耗时：0ms

var

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

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

b:array[0..1000,0..1000]of longint;

procedure zh(i,j:longint);

begin

if (ab)and(i>1)and(j>0)and(i0)and(j>0)and(i+10)and(j>1)and(i0)and(j>0)and(it

then begin

t:=a;

x:=i;

y:=j;

end;

end;

readln;

end;

t:=0;

b[x,y]:=1;

zh(x,y);

if t>0 then write(t)

else write('1');

end.

Flag 　　 Unaccepted

题号　　P1011

类型(?) 　　动态规划

通过　　2369人

提交　　11124次

通过率　　21%

难度　　2

提交讨论题解

张厚

　Copyright Vijos 高效信息学在线评测系统 © 2005-2008. www.Vijos.cn Powered by Vivian Snow　关于　联系　帮助

　Vijos Infor ---|- Total Users : 40070 | Online Users / Processes : 29 / 257 | Proc. Time : 109 ms | Current Time : 2009-1-13 18:48:27　湘ICP备06015828号

0

330459659 LV 10 @ 2008-12-28 16:41:35

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

快排+DP 虽然慢了点但还是A了

没办法不会记忆化

0

Beta LV 6 @ 2008-12-19 20:51:02

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

妈啊 longint!!!!!!!!!!

忘了啊

大家记住

0

hpec LV 6 @ 2009-03-21 15:53:22

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索~~

开始的情况同楼下,

把integer都该成longint,AC~ 不知道为什么~~~

开始没加f:=go(i,j); 直接写x:=go(i,j); 结果34ms

改完~秒杀~~

记忆化比DP快啊。。排序貌似很浪费时间啊。。。

***|hpec killed P1011 with Awp~~

0

1gjh1 LV 8 @ 2008-12-13 21:36:10

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案错误...　├ 标准行输出 402

　├ 错误行输出 360

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

Why?

const q:array[1..4,1..2] of integer=((0,-1),(0,1),(1,0),(-1,0));

var i,j,r,c,max:integer;

a,b:array[1..500,1..500] of integer;

procedure find(m,n:integer);

var k,o,p,s:integer;

begin

s:=0;

for k:=1 to 4 do

begin

o:=m+q[k,1];p:=n+q[k,2];

if (o>=1)and(o=1)and(pa[o,p] then

begin

if b[o,p]=0 then find(o,p);

if b[o,p]>s then s:=b[o,p]

end;

end;

b[m,n]:=s+1;

end;

begin

readln(r,c);

for i:=1 to r do

for j:=1 to c do

read(a);

for i:=1 to r do

for j:=1 to c do

begin find(i,j);if b>max then max:=b;end;

writeln(max);

end.

0

xiaoX LV 10 @ 2008-12-13 18:46:14

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索…… 为什么大家都秒杀…… 我没有…… vag 6K

Flag 　　Accepted

题号　　P1011

类型(?) 　　动态规划

通过　　2323人

提交　　11000次

通过率　　21%

难度　　2

这么巧啊…… 纪念下……

0

GD-becky LV 8 @ 2008-12-02 17:42:35

happy~~一次AC~~穷举起始点+记忆化

0

rickforce LV 5 @ 2008-11-30 07:15:53

枚举每一个点然后记忆化DFS~~

不要小看记忆化DFS的效率哦~~

注意f[i][j]初始化为1就行了

0

xianweizhao LV 5 @ 2008-11-28 14:56:36

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

fan6882090 LV 7 @ 2008-11-22 20:19:20

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索,郁闷,忘加了3个'='我的AC率啊!

program p1011;

var n,m,i,j,ans:longint;

data,a:array[0..500,0..500] of longint;

function try(x,y:longint):longint;

var temp:longint;

begin

if (x=0) or (y=0) or (x>n) or (y>m)

then exit(0);

if data[x,y]0

then exit(data[x,y]);

try:=0;

if a[x-1,y]>a[x,y]

then begin

temp:=try(x-1,y);

if temp>=data[x,y]

then data[x,y]:=temp+1;

if temp+1>ans

then ans:=temp+1;

end;

if a[x+1,y]>a[x,y]

then begin

temp:=try(x+1,y);

if temp>=data[x,y]

then data[x,y]:=temp+1;

if temp+1>ans

then ans:=temp+1;

end;

if a[x,y-1]>a[x,y]

then begin

temp:=try(x,y-1);

if temp>=data[x,y]

then data[x,y]:=temp+1;

if temp+1>ans

then ans:=temp+1;

end;

if a[x,y+1]>a[x,y]

then begin

temp:=try(x,y+1);

if temp>=data[x,y]

then data[x,y]:=temp+1;

if temp+1>ans

then ans:=temp+1;

end;

try:=data[x,y];

end;

begin

readln(n,m);

for i:=1 to n do

begin

for j:=1 to m do

read(a);

readln;

end;

for i:=1 to n do

for j:=1 to m do

begin

if data=0

then data:=try(i,j);

if data>ans then ans:=data;

end;

writeln(ans+1);

end.

0

lostdeader LV 3 @ 2008-11-13 20:48:40

program fengbo;

var v,ca:array[0..501,0..501]of boolean;

　　 f,h:array[0..501,0..501]of longint;

　　 r,c,i,j,k,l,m,n,max,ans:longint;

function try(a,b:longint):boolean;

begin

try:=false;

if ca[a,b]=true then begin try:=true;exit;end;

if f[a,b+1]h[a,b] then h[a,b]:=h[a,b+1]+1;end;end;

if f[a,b-1]h[a,b] then h[a,b]:=h[a,b-1]+1;end;end;

if f[a+1,b]h[a,b] then h[a,b]:=h[a+1,b]+1;end;end;

if f[a-1,b]h[a,b] then h[a,b]:=h[a-1,b]+1;end;end;

if not try then begin ca[a,b]:=true;try:=true;h[a,b]:=1;end;

end;

begin

readln(r,c);

for i:=1 to r do

begin

　　for j:=1 to c do

　　 read(f);

　　readln;

end;

for i:=0 to c+1 do begin f[0,i]:=50000;f[r+1,i]:=50000;end;

for i:=0 to r+1 do begin f:=50000;f:=50000;end;

for i:=1 to r do

for j:=1 to c do

if v=false then

　　begin

　　 v:=true;

　　 if try(i,j) then if h>max then max:=h;

　　end;

writeln(max);

end.

0

wts LV 3 @ 2008-11-12 21:01:45

超时我认了,可为什么结果也是错的呢??哪位大牛指点一下,不胜感激啊.

program emp;

type data=record

num:integer;

x:integer;

y:integer;

end;

var i,j,n,m:longint;

a:array[0..25000] of data;

f:array[0..25000] of longint;

procedure init;

begin

assign(input,'emp.in');

reset(input);

assign(output,'emp.out');

rewrite(output);

readln(n,m);

for i:=1 to n do

begin

for j:=1 to m do

begin

read(a[(i-1)*m+j].num);

a[(i-1)*m+j].x:=i;

a[(i-1)*m+j].y:=j;

end;

readln;

end;

close(input);

end;

procedure exchange(a,b:integer);

var t:integer;

begin

t:=a;

a:=b;

b:=t;

end;

procedure sort(l,r:integer);

var

i,j,x,y,t:integer;

begin

i:=l;

j:=r;

x:=a[(l+r) div 2].num;

repeat

while a[i].numj;

if l

0

hushuihai LV 3 @ 2008-11-12 11:19:47

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

记忆化搜索

f[x,y]:=1(如果周围的点都更高）

f[x,y]:=max{f[x1,y1]+1} (周围有更低点）

0

xusc LV 7 @ 2008-11-12 08:37:41

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

....

5555

快排+动规:挂了

乱搜:ac

...?

0

329704345 LV 3 @ 2008-11-11 21:00:00

program fengbo;

var v,ca:array[0..501,0..501]of boolean;

f,h:array[0..501,0..501]of longint;

r,c,i,j,k,l,m,n,max,ans:longint;

function try(a,b:longint):boolean;

begin

try:=false;

if ca[a,b]=true then begin try:=true;exit;end;

if f[a,b+1]h[a,b] then h[a,b]:=h[a,b+1]+1;end;end;

if f[a,b-1]h[a,b] then h[a,b]:=h[a,b-1]+1;end;end;

if f[a+1,b]h[a,b] then h[a,b]:=h[a+1,b]+1;end;end;

if f[a-1,b]h[a,b] then h[a,b]:=h[a-1,b]+1;end;end;

if not try then begin ca[a,b]:=true;try:=true;h[a,b]:=1;end;

end;

begin

readln(r,c);

for i:=1 to r do

begin

for j:=1 to c do

read(f);

readln;

end;

for i:=0 to c+1 do begin f[0,i]:=50000;f[r+1,i]:=50000;end;

for i:=0 to r+1 do begin f:=50000;f:=50000;end;

for i:=1 to r do

for j:=1 to c do

if v=false then

begin

v:=true;

if try(i,j) then if h>max then max:=h;

end;

writeln(max);

end.

0

林 LV 3 @ 2008-11-11 21:32:52

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

为什么啊？？？？？？？？？？

主救我`\`\`\`\

0

陌离 LV 3 @ 2008-11-10 23:01:51

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

原来用递归的时候做好了必死的准备~~~没想到这么快！！^.^

递归版DP，本门独创！

0

六月的雨 LV 3 @ 2008-11-10 22:29:59

记得刚学DP的时候讲这个题

觉得快排预处理的方法很神奇

0

zltchenhana LV 3 @ 2008-11-10 08:15:07

本题使用记忆化搜索，即在搜索的同时设立一个

F与search(i,j)相对.search(i,j)的值一经算出，直接调用。

于是在推出递归函数时，要同时给search和F赋值以便调用；

对于任意一个点（i，j），如果人想到达的话，可以从四个方向，即其上，下，左，右

对应的坐标分为分（i-1，j），（i+1，j），（i，j-1），（i，j+1）；

因此枚举以上四点，且满足A与A[X,Y]（即以上四点）有a[x,y]>a

成立，则枚举其最大值max，max+1为本点(i,j)所求函数值，并记录即可。

最后输出所有f中最大值ans.

以下是函数部分伪代码：

search(i,j):

if F>0 then exit(f)

else 枚举四个点

if 点在界内 and 点值大于a then 记录 max

f:=max+1;

exit(f);

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

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

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

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

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

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

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

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

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

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

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

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

秒杀

0

527971925 LV 10 @ 2008-11-09 10:59:14

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案错误...　├ 标准行输出 402

　├ 错误行输出 365

├ 测试数据 10：答案错误...　├ 标准行输出 1

　├ 错误行输出 3

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

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

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

const z:array[1..4,1..2]of integer=((0,1),(0,-1),(-1,0),(1,0));

var i,j,r,c,max:longint;f,map:array[0..501,0..501]of longint;

procedure find(x,y,ans:longint);

var i:longint;

begin

if ans>f[x,y] then

begin

f[x,y]:=ans;

if ans>max then max:=ans;

for i:=1 to 4 do

if map[x+z,y+z]

题解

358 条题解

清帝之惑之顺治

信息

状态

开发

支持

题解

358 条题解

清帝之惑之顺治

信息

状态

开发

支持

还没有账户？

登录