vijos1656【宋壬初吧】

宋壬初吧关注：25贴子：419

3回复贴，共1页

vijos1656

221.194.73.*

var i,j,k,l,m,n,p,q,r,s,t,x1,x2,y1,y2:longint;
can,sel,v:array[0..8,0..8] of boolean;
short,len:array[1..7,1..7] of longint;
quene:array[1..100,1..2] of longint;
c:char;
pd:boolean;
procedure dfs(x,y,deep:longint);
var g:longint;
begin
if (x=x2)and(y=y2) then
begin
if deep=t then pd:=true;
exit;
end;
can[x,y]:=false;
if can[x-1,y] then
dfs(x-1,y,deep+1);
if pd then
begin
can[x,y]:=true;exit;
end;
if can[x+1,y] then
dfs(x+1,y,deep+1);
if pd then
begin
can[x,y]:=true;exit;
end;
if can[x,y-1] then
dfs(x,y-1,deep+1);
if pd then
begin
can[x,y]:=true;exit;
end;
if can[x,y+1] then
dfs(x,y+1,deep+1);
can[x,y]:=true;
end;
begin
while true do
begin
readln(n,m,t);
if n+m+t=0 then halt;
fillchar(can,sizeof(can),true);
for i:=1 to n do
begin
can[i,0]:=false;can[i,m+1]:=false;
end;
for i:=1 to m do
begin
can[0,i]:=false;can[n+1,i]:=false;
end;
x1:=1;y1:=1;
for i:=1 to n do
begin
for j:=1 to m do
begin
read©;
if c='D' then begin x2:=i;y2:=j;end;
if c='H' then can[i,j]:=false;
end;
readln;
end;
if abs(x1-x2+y1-y2+t) mod 2=1 then
begin
writeln('No');
continue;
end;
pd:=false;
if can[x1-1,y1] then dfs(x1-1,y1,1);
if pd then
begin
writeln('Yes');
continue;
end;
if can[x1+1,y1] then dfs(x1+1,y1,1);
if pd then
begin
writeln('Yes');
continue;
end;
if can[x1,y1-1] then dfs(x1,y1-1,1);
if pd then
begin
writeln('Yes');
continue;
end;
if can[x1,y1+1] then dfs(x1,y1+1,1);
if pd then writeln('Yes') else writeln('No');
end;
end.

1楼2009-10-04 15:56回复

221.194.73.*

var i,j,k,l,m,n,p,q,r,s,t,d:longint;
father,left,right,data,delta,mid:array[0..300000] of longint;
xd:array[0..300000,1..2] of longint;
hx:array[0..100000] of longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
function ask_max(l,r,num:longint):longint;
begin
if (l=xd[num,1])and(r=xd[num,2]) then exit(data[num]);
if r<=mid[num] then ask_max:=ask_max(l,r,left[num]) else
if l>mid[num] then ask_max:=ask_max(l,r,right[num]) else
ask_max:=max(ask_max(l,mid[num],left[num]),ask_max(mid[num]+1,r,right[num]));
inc(ask_max,delta[num]);
end;
procedure ins(l,r,num:longint);
begin
//writeln(xd[num,1],' ',xd[num,2]);
if (l=xd[num,1])and(r=xd[num,2]) then
begin
inc(delta[num],d);inc(data[num],d);exit;
end;
if delta[num]<>0 then
begin
inc(delta[left[num]],delta[num]);inc(delta[right[num]],delta[num]);
inc(data[left[num]],delta[num]);inc(data[right[num]],delta[num]);
delta[num]:=0;
end;
if r<=mid[num] then ins(l,r,left[num]) else
if l>mid[num] then ins(l,r,right[num]) else
begin
ins(l,mid[num],left[num]);
ins(mid[num]+1,r,right[num]);
end;
data[num]:=max(data[left[num]],data[right[num]]);
end;
begin
for i:=1 to 300000 do data[i]:=-2000000000;
read(n);
for i:=1 to n do read(hx[i]);
p:=0;q:=1;xd[1,1]:=1;xd[1,2]:=n;
while p<q do
begin
inc(p);
t:=(xd[p,1]+xd[p,2]) shr 1;
mid[p]:=t;
if xd[p,1]<xd[p,2] then
begin
inc(q);father[q]:=p;left[p]:=q;
xd[q,1]:=xd[p,1];xd[q,2]:=t;
inc(q);father[q]:=p;right[p]:=q;
xd[q,1]:=t+1;xd[q,2]:=xd[p,2];
end else
data[p]:=hx[xd[p,1]];
end;
for i:=q downto 2 do if data[i]>data[father[i]] then data[father[i]]:=data[i];
//for i:=1 to q do writeln(xd[i,1],' ',xd[i,2],':',data[i]);
fillchar(delta,sizeof(delta),0);
read(m);
for i:=1 to m do
begin
read(k);
if k=2 then
begin
read(l,r);
write(ask_max(l,r,1),' ');
end;
if k=1 then
begin
read(l,r,d);
ins(l,r,1);
// for j:=1 to n do write(ask_max(j,j,1),' ');writeln;
end;
end;
writeln;
end.

2楼2009-10-04 21:47