Daily Archives: 31 8 月, 2012

POJ 1868(等差数列）

Posted on by

暴力模拟无算法

Program P1868;
Var
   c:char;
   n,i,j,k:longint;
   a:array[0..10000] of longint;
function is_ant:boolean;
var
   i,j,k:longint;
begin
   for k:=1 to n shr 2 do
      for i:=1 to n-k shl 1-1 do
         if ((a[i]<a[i+k]) and (a[i+k]<a[i+2*k])) or ((a[i]>a[i+k]) and (a[i+k]>a[i+2*k])) then exit(false);




   exit(true);
end;
Begin
   while true do
   begin
      read(c);
      if c='0' then break;
      val(c,n);
      repeat
         read(c);
         if c=':' then break;
         n:=n*10+ord(c)-48;
      until false;
      for i:=1 to n do
      begin
         read(j);
         a[j]:=i;
      end;

      if is_ant then writeln('yes') else writeln('no');

      readln;

   end;
end.

POJ 1088（滑雪）

Posted on by

标准记忆化搜索 模板题

Program P1088;
var
   ans,n,m,i,j:longint;
   a,f:array[0..101,0..101] of longint;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
function dfs(x,y:longint):longint;
var
   i,j:longint;
begin
   if f[x,y]>0 then exit(f[x,y]);
   dfs:=0;
   if a[x-1,y]<a[x,y] then dfs:=max(dfs,dfs(x-1,y)+1);
   if a[x+1,y]<a[x,y] then dfs:=max(dfs,dfs(x+1,y)+1);
   if a[x,y-1]<a[x,y] then dfs:=max(dfs,dfs(x,y-1)+1);
   if a[x,y+1]<a[x,y] then dfs:=max(dfs,dfs(x,y+1)+1);
   f[x,y]:=dfs;
end;
begin
   read(n,m);
   fillchar(a,sizeof(a),127);
   for i:=1 to n do
      for j:=1 to m do
         read(a[i,j]);
   fillchar(f,sizeof(f),0);
   ans:=0;

   for i:=1 to n do
      for j:=1 to m do
      begin
         if f[i,j]=0 then ans:=max(ans,dfs(i,j));
      end;
   writeln(ans+1);
end.

POJ 1830（位运算+双向DFS）

Posted on by

此题也可用GE做，可是我不会矩阵乘法……

Program P1830;
const
   maxn=28;
   maxf=100007;
   none=-2139062144;
var
   ans,tt,n,i,j,s,t,mid:longint;
   b:array[1..29] of longint;
   h,num:array[0..maxf] of longint;

function hash(x:longint):longint;
var
   i,j:longint;
begin
   hash:=x mod maxf;
   while (num[hash]<>x) and (num[hash]<>none) do
   begin
      hash:=(hash+1) mod maxf;
   end;
   num[hash]:=x;
   exit(hash);
end;
procedure dfs(x,l:longint);
var
   i,j:longint;
begin
   if l=mid+1 then
   begin
      inc(h[hash(x)]);
      exit;
   end;
   for i:=l to mid do
      dfs(x xor b[i],i+1);
   dfs(x,mid+1);

end;
procedure find(x,l:longint);
var
   i,j:longint;
begin
   if l=n+1 then
   begin
      inc(ans,h[hash(x)]);
      exit;
   end;
   for i:=l to n do
      find(x xor b[i],i+1);
   find(x,n+1);

end;

begin
   read(tt);
   while (tt>0) do
   begin
      ans:=0;
      fillchar(b,sizeof(b),0);
      fillchar(num,sizeof(num),128);
      fillchar(h,sizeof(h),0);

      read(n);
      s:=0;
      for i:=1 to n do
      begin
         read(j);
         if j=1 then inc(s,1 shl (i-1));
      end;
      t:=0;
      for i:=1 to n do
      begin
         read(j);
         if j=1 then inc(t,1 shl (i-1));
      end;
      while (true) do
      begin
         read(i,j);
         if (i=0) and (j=0) then break;
         inc(b[i],1 shl (j-1));
      end;
      for i:=1 to n do inc(b[i],1 shl (i-1));
      mid:=n shr 1;
      dfs(s,1);
      find(t,mid+1);
      if ans=0 then writeln('Oh,it''s impossible~!!') else
      writeln(ans);
      dec(tt);
   end;
end.