Daily Archives: 17 8 月, 2012

POJ 2506(放方块）

Posted on by

高精Dp

Program P2506;
type
   arr=record
       a:array[1..10000] of longint;
       len:longint;
       end;
const
   base=1000;
var
   i,j,n:longint;
   f:array[0..250] of arr;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
Procedure add(a,b:arr;var c:arr);
var
   i,j,len:longint;
begin
   fillchar(c,sizeof(c),0);
   for i:=1 to max(a.len,b.len) do
   begin
      inc(c.a[i],a.a[i]+2*b.a[i]);
      inc(c.a[i+1],c.a[i] div base);
      c.a[i]:=c.a[i] mod base;
   end;
   i:=max(a.len,b.len);
   while (c.a[i+1]>0) do
   begin
      inc(i);
      inc(c.a[i+1],c.a[i] div base);
      c.a[i]:=c.a[i] mod base;
   end;
   while (i>1) and (c.a[i]=0) do dec(i);
   c.len:=i;

end;
begin
   fillchar(f,sizeof(f),0);
   for i:=0 to 250 do f[i].len:=1;
   f[1].a[1]:=1;
   f[0].a[1]:=1;
   for i:=2 to 250 do add(f[i-1],f[i-2],f[i]);
   while not eof do
   begin
      readln(n);
      write(f[n].a[f[n].len]);
      for i:=f[n].len-1 downto 1 do
      begin
         if f[n].a[i]<100 then write('0');
         if f[n].a[i]<10 then write('0');
         write(f[n].a[i]);
      end;
      writeln;
   end;

end.

POJ 1832(9连环）

Posted on by

格雷码做

0要特判

答案 就是读入的两个数充格雷码转为2进制的差的绝对值的十进制

Program P1832;
Type
   arr=record
       a:array[1..500] of longint;
       len:longint;
       end;
var
   n,m,i:longint;
   a,b,c,d:arr;
   node2:array[1..1000] of arr;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
function compare:boolean;
var
   i,j:longint;
begin
   while (a.len>1) and (a.a[a.len]=0) do dec(a.len);
   while (b.len>1) and (b.a[b.len]=0) do dec(b.len);
   if a.len<b.len then exit(true)
   else if a.len>b.len then exit(false);

   i:=a.len;
   while (i>1) and (a.a[i]=b.a[i]) do
   begin
      dec(i);
   end;
   if (a.a[i]<=b.a[i]) then exit(true) else exit(false);
end;
Procedure Subtract(a,b:arr;var c:arr);
var
   i,j:longint;
   pa:arr;
begin
   if (compare) then
   begin
      pa:=a;
      a:=b;
      b:=pa;
   end;
   fillchar(c,sizeof(c),0);
   for i:=1 to a.len do
   begin
      inc(c.a[i],a.a[i]-b.a[i]);
      if c.a[i]<0 then
      begin
         inc(c.a[i],2);
         dec(c.a[i+1]);
      end;
   end;
   c.len:=a.len;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);
end;
procedure add(a,b:arr;var c:arr);
var
   i,j:longint;
begin
   fillchar(c,sizeof(c),0);
   for i:=1 to max(a.len,b.len) do
   begin
      inc(c.a[i],a.a[i]+b.a[i]);
      inc(c.a[i+1],c.a[i] div 10);
      c.a[i]:=c.a[i] mod 10;
   end;
   c.len:=max(a.len,b.len)+1;
   while (c.len>1) and (c.a[c.len]=0) do dec(c.len);
end;
begin
   fillchar(node2,sizeof(node2),0);
   node2[1].len:=1;
   node2[1].a[1]:=1;

   for i:=2 to 500 do
   begin
      add(node2[i-1],node2[i-1],node2[i]);
   end;

 {  assign(input,'P1832.in');
   assign(output,'P1832.out');
   reset(input);
   rewrite(output);
  }
   read(m);
   while m>0 do
   begin
      fillchar(a,sizeof(a),0);
      fillchar(b,sizeof(b),0);
      read(n);

      if n=0 then
      begin
         writeln('0');
         dec(m);
         continue;
      end;
      for i:=n downto 1 do read(a.a[i]);
      for i:=n downto 1 do read(b.a[i]);
      for i:=n-1 downto 1 do
      begin
         a.a[i]:=(a.a[i] xor a.a[i+1]);
      end;

      for i:=n-1 downto 1 do
         b.a[i]:=b.a[i] xor b.a[i+1];
      a.len:=n;
      b.len:=n;

      subtract(a,b,c);
//      for i:=n downto 1 do write(c.a[i]);
//      writeln;
      fillchar(d,sizeof(d),0);
      d.len:=1;
      for i:=n downto 1 do
         if c.a[i]>0 then add(node2[i],d,d);

      for i:=d.len downto 1 do write(d.a[i]);


      writeln;
      dec(m);
   end;
{   close(input);
   close(output);
}
end.

POJ 1860（判定正圈）

Posted on by

Bellman_ford

Program P1860;
var
   n,m,i,j,s:longint;
   v:double;
   flag:boolean;
   d:array[1..100] of double;
   x,y:array[1..100] of longint;
   map:array[1..100,1..4] of double;
procedure relax(i:longint);
begin
   if (d[y[i]]<(d[x[i]]-map[i,2])*map[i,1]) then
   begin
      d[y[i]]:=(d[x[i]]-map[i,2])*map[i,1];
      flag:=false;
   end;
   if (d[x[i]]<(d[y[i]]-map[i,4])*map[i,3]) then
   begin
      d[x[i]]:=(d[y[i]]-map[i,4])*map[i,3];
      flag:=false;
   end;

end;
procedure bell_ford;
var
   i,j:longint;
begin
   for i:=1 to n do
   begin
      flag:=true;
      for j:=1 to m do relax(j);
      if flag then break;
   end;
   if flag then writeln('NO')
   else writeln('YES');
end;
begin
   while not seekeof do
   begin
      readln(n,m,s,v);
      fillchar(d,sizeof(d),0);
      d[s]:=v;
      for i:=1 to m do
      begin
         readln(x[i],y[i],map[i,1],map[i,2],map[i,3],map[i,4]);
      end;
      bell_ford;
   end;
end.

POJ 1207(3N+1)

Posted on by

3n+1问题 果断暴力

Program P1207;
var
   i,j,k,n,m,ans:longint;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
procedure swap(var a,b:longint);
var
   p:longint;
begin
   p:=a;
   a:=b;
   b:=p;
end;
begin
   while not eof do
   begin
      readln(n,m);
      write(n,' ',m,' ');
      if n>m then swap(n,m);
      ans:=0;
      for i:=n to m do
      begin
         j:=1;
         k:=i;
         while (k<>1) do
         begin
            if (k mod 2=0) then k:=k div 2
            else k:=k*3+1;
            inc(j);
         end;

         ans:=max(ans,j);
      end;
      writeln(ans);
   end;
end.