Monthly Archives: 9 月 2012

POJ 2110(最小生成树）

Posted on by

这题的思路就是找一个范围，看看这个范围是否可行

主流是二分Ans，我是先把点排序，求最小生成树检查首位的

Program P2110;
type
   ed=record
      u,v,w:longint;
      end;
var
   a:array[1..120,1..120] of longint;
   edge:array[0..30000] of ed;
   n,i,j,size,ans:longint;
   now:longint;
   father:array[0..10001] of longint;
   b:array[0..121,0..121] of boolean;
procedure add(u,v,w:longint);
begin
   inc(size);
   edge[size].u:=u;
   edge[size].v:=v;
   edge[size].w:=w;

end;
procedure qsort(l,r:longint);
var
   i,j,m:longint;
   p:ed;
begin
   i:=l;
   j:=r;
   m:=edge[(l+r) shr 1].w;
   repeat
      while edge[i].w<m do inc(i);
      while edge[j].w>m do dec(j);
      if i<=j then
      begin
         p:=edge[i];
         edge[i]:=edge[j];
         edge[j]:=p;
         inc(i);
         dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);



end;
function getfather(x:longint):longint;
begin
   if x=father[x] then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
function hash(x,y:longint):longint;
begin
  exit((x-1)*n+y);
end;
begin
   size:=0;
   read(n);
   for i:=1 to n do
      for j:=1 to n do
      begin
         read(a[i,j]);
         add(i,j,a[i,j]);
      end;

  // (0,n*n)
   qsort(1,size);


   edge[0].w:=edge[1].w-1;
   ans:=110;
   //                 writeln;
   for i:=1 to size do
   begin

      if edge[i].w=edge[i-1].w then continue;
      for j:=0 to n*n do father[j]:=j;
      fillchar(b,sizeof(b),false);
      for j:=i to size do
      begin
         b[edge[j].u,edge[j].v]:=true;
         now:=hash(edge[j].u,edge[j].v);

         if b[edge[j].u-1,edge[j].v] then
            if getfather(now)<>getfather(now-n) then
            begin
               father[father[now]]:=father[father[now-n]];
               if getfather(0)=getfather(n*n) then break;
            end;

         if b[edge[j].u+1,edge[j].v] then
            if getfather(now)<>getfather(now+n) then
            begin
               father[father[now]]:=father[father[now+n]];
               if getfather(0)=getfather(n*n) then break;
            end;

         if b[edge[j].u,edge[j].v+1] then
            if getfather(now)<>getfather(now+1) then
            begin
               father[father[now]]:=father[father[now+1]];
               if getfather(0)=getfather(n*n) then break;
            end;

         if b[edge[j].u,edge[j].v-1] then
            if getfather(now)<>getfather(now-1) then
            begin
               father[father[now]]:=father[father[now-1]];
               if getfather(0)=getfather(n*n) then break;
            end;



         if getfather(1)=getfather(n*n) then break;

      end;



      if getfather(1)<>getfather(n*n) then break;
      if ans>edge[j].w-edge[i].w then ans:=edge[j].w-edge[i].w;


   end;
   writeln(ans);



end.

POJ 1952（最长不下降子序列的个数）

Posted on by

求一个序列的最长不下降子序列的长度，与个数（相同数列算1个）

关键是如何判重。

显然如果之前有一个尾数相同且长度相同的序列，哪么后一个包含前一个所有可能的序列相同的序列，故将前一个序列删除（重复)

Program P1952;
var
   n,i,j,ans:longint;
   a,len,f,path:array[1..5000] of longint;
begin
   read(n);
   for i:=1 to n do read(a[i]);
   for i:=1 to n do
   begin
      len[i]:=1;
      f[i]:=1;
      path[i]:=i;
      for j:=i-1 downto 1 do
         if (a[j]>a[i]) and (len[j]+1>len[i]) then
         begin
            len[i]:=len[j]+1;
            f[i]:=f[j];
         end
         else if (a[j]>a[i]) and (len[j]+1=len[i]) then inc(f[i],f[j]);


      for j:=1 to i-1 do
         if (a[i]=a[j]) and (len[i]=len[j]) then f[j]:=0;



   end;
   j:=0;
   for i:=1 to n do if len[i]>j then j:=len[i];
   ans:=0;
   for i:=1 to n do if len[i]=j then inc(ans,f[i]);

   writeln(j,' ',ans);


end.

POJ 1951（空串特判）

Posted on by

这题的教训是 要特判空串 

Program P1951;
var
   s:string;
   len,i,j:longint;
   b:array[0..10000] of boolean;
function isdight(x:longint):boolean;
begin
   if (x>=65) and (x<=90) then exit(false);
   if (x>=97) and (x<=122) then exit(false);
   exit(true);

end;
begin
   readln(s);
   fillchar(b,sizeof(b),false);
   b[ord('a')]:=true;
   b[ord('e')]:=true;
   b[ord('i')]:=true;
   b[ord('o')]:=true;
   b[ord('u')]:=true;
   b[ord('A')]:=true;
   b[ord('E')]:=true;
   b[ord('I')]:=true;
   b[ord('O')]:=true;
   b[ord('U')]:=true;

   i:=1;
   while i<=length(s) do
   begin
      if b[ord(s[i])] and not(isdight(ord(s[i]))) then delete(s,i,1)
      else
      begin
         b[ord(s[i])]:=true;
         inc(i);

      end;
   end;


   while (s[1]=' ') and (length(s)>=1) do delete(s,1,1);
   while (s[length(s)]=' ') and (length(s)>=1) do delete(s,length(s),1);
   i:=pos('  ',s);
   while i<>0 do
   begin
      delete(s,i,1);
      i:=pos('  ',s);
   end;
   i:=pos(' .',s);
   while i<>0 do
   begin
      delete(s,i,1);
      i:=pos(' .',s);
   end;
   i:=pos(' ,',s);
   while i<>0 do
   begin
      delete(s,i,1);
      i:=pos(' ,',s);
   end;
   i:=pos(' ?',s);
   while i<>0 do
   begin
      delete(s,i,1);
      i:=pos(' ?',s);
   end;



   writeln(s);

end.

POJ 1950(不打表做法）

Posted on by

这题就是搜……

注意设定maxn 要不然肯定爆 maxn=1*10^最大位数/2 1234..89-11121314这样的

Program aa;
const
   maxn=1000000000000000;
var
   n,t:longint;
   a:array[1..15] of char;
procedure dfs(l,sum,res,bl:int64);
var
   i,j:longint;
begin
   if l=n then
   begin
      res:=res+bl*sum;
      if res=0 then
      begin
         inc(t);
         if t<=20 then
         begin
            for i:=1 to n-1 do write(i,' ',a[i],' ');
            writeln(n);


         end;
      end;


      exit;
   end;

   a[l]:='+';
   dfs(l+1,l+1,res+bl*sum,1);
   a[l]:='-';
   dfs(l+1,l+1,res+bl*sum,-1);
   a[l]:='.';
   if sum<=maxn then
   if l+1<=9 then
      dfs(l+1,sum*10+(l+1),res,bl)
   else
      dfs(l+1,sum*100+(l+1),res,bl);


end;
begin
 {  assign(output,'a.pas');
   rewrite(output);
  }
   read(n);
   t:=0;
   dfs(1,1,0,1);
   writeln(t);

 //  close(output);
end.

POJ 3278(BFS-搜索范围）

Posted on by

这题是BFS水的

主要是范围

0<=n,k<=100000  但是有可能搜到200000……

半天功夫才A.

program P3278;
const
   maxn=200000;
var
   n,k,i,j:longint;
   q,deep:array[1..maxn] of longint;
   b:array[0..maxn] of boolean;
procedure add(x:longint);
begin
   if not(b[x]) then
   begin
      b[x]:=true;
      inc(j);
      q[j]:=x;
      deep[j]:=deep[i]+1;
   end;
end;
begin
   read(n,k);
   i:=1;
   j:=1;
   fillchar(b,sizeof(b),false);
   b[n]:=true;
   q[1]:=n;deep[1]:=0;
   if n=k then
   begin
      writeln('0');
      halt;
   end;


   while i<=j do
   begin
      if (q[i]>0) then add(q[i]-1);
      if b[k] then break;
      if (q[i]<maxn) then add(q[i]+1);
      if b[k] then break;
      if (q[i]*2<maxn) then add(q[i]*2);
      if b[k] then break;
      inc(i);
   end;
   writeln(deep[j]);

end.

POJ 3256(SPFA）

Posted on by

这题只能对每一个点查一遍……

有向图的话能用floyd，可是迫于时限用了SPFA。

Program aa;
const
   maxk=10000;
   maxn=10000;
   maxm=10000;
var
   k,n,m,i,j,l:longint;
   a:array[1..maxk] of longint;
   q:array[1..maxn] of longint;
   edge,next,head:array[1..maxm] of longint;
   size:longint;
   res,num,b:array[1..maxn] of boolean;

procedure add(u,v:longint);
begin
   inc(size);
   edge[size]:=v;
   next[size]:=head[u];
   head[u]:=size;
end;


procedure spfa;
var
   i,j,p,now,v:longint;
begin
   i:=1;j:=1;
   while (i<=j) do
   begin
      now:=q[i];
      p:=head[now];
      while p<>0 do
      begin
         v:=edge[p];
         if not(b[v]) then
         begin
            b[v]:=true;
            inc(j);
            q[j]:=v;
         end;



         p:=next[p];
      end;
      inc(i);
   end;
   for i:=1 to n do
      res[i]:=res[i] and b[i];

end;

begin
   size:=0;
   fillchar(head,sizeof(head),0);
   fillchar(edge,sizeof(edge),0);
   fillchar(next,sizeof(next),0);
   fillchar(b,sizeof(b),false);
   fillchar(res,sizeof(res),true);
   fillchar(num,sizeof(num),false);
   read(k,n,m);
   for i:=1 to k do read(a[i]);
   for i:=1 to m do
   begin
      read(j,l);
      add(j,l);
   end;

   for i:=1 to k do
      if not(num[a[i]]) then
      begin
         num[a[i]]:=true;
         q[1]:=a[i];
         fillchar(b,sizeof(b),false);
         b[q[1]]:=true;
         spfa;
      end;
   l:=0;
   for i:=1 to n do if res[i] then inc(l);
   writeln(l);



end.

POJ 3692（匈牙利算法）

Posted on by

匈牙利算法：

b[]保存当前找交错路P的各点是否已被连通，a[]表示某点之前的点

本题的2分图是取最大团（各点互相连通），利用2分图性质，可看成补图的最大独立集（各点互不连通）……

Program P3692;
const
   maxn=200;

var
   n,m,l,i,j,k,ans,x,y:longint;
   b:array[1..400] of boolean;
   map:array[1..400,1..400] of boolean;
   a:array[1..400] of longint;
function find(x:longint):boolean;
var
   i,j:longint;
begin
   for i:=1 to m do
      if not(b[i]) and (map[x,i]) then
      begin
         b[i]:=true;
         if a[i]=0 then begin a[i]:=x; exit(true); end;
         if find(a[i]) then begin a[i]:=x; exit(true); end;
      end;

   exit(false);
end;
begin
   i:=1;
   read(n,m,l);
   while (n+m+l>0) do
   begin
      ans:=0;
      fillchar(a,sizeof(a),0);
      fillchar(map,sizeof(map),true);
      for k:=1 to l do
      begin
         read(x,y);
         map[x,y]:=false;
      end;
      for k:=1 to n do
      begin
         fillchar(b,sizeof(b),false);
         if find(k) then inc(ans);
      end;
      writeln('Case ',i,': ',n+m-ans);
      inc(i);
      read(n,m,l);
   end;
end.

HYSBZ 1050(队列-大小边比值最大的路径）

Posted on by

已知边，判断2点连通性

要用并查集……千万别搜啊~

Program ee;
var
   edge:array[1..10000,1..3] of longint;
   s,t,n,m,i,j,pmax,pmin:longint;
   father:array[1..1000] of longint;

procedure swap(var a,b:longint);
var
   p:longint;
begin
   p:=a;
   a:=b;
   b:=p;
end;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=edge[(l+r) shr 1,3];
   repeat
      while edge[i,3]<m do inc(i);
      while edge[j,3]>m do dec(j);
      if i<=j then
      begin
         swap(edge[i,1],edge[j,1]);
         swap(edge[i,2],edge[j,2]);
         swap(edge[i,3],edge[j,3]);
         inc(i);dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);

end;
function gcd(a,b:longint):longint;
begin
   if b=0 then exit(a) else exit(gcd(b,a mod b));
end;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x) else father[x]:=getfather(father[x]);
   exit(father[x]);
end;
begin
   pmax:=50000000;pmin:=1;
   read(n,m);
   for i:=1 to m do read(edge[i,1],edge[i,2],edge[i,3]);
   read(s,t);
   qsort(1,m);
   i:=1;

   for i:=1 to m do
   begin
      for j:=1 to n do father[j]:=j;
      j:=i;
      while (getfather(s)<>getfather(t)) and (j<=m) do
      begin
         if getfather(edge[j,2])<>getfather(edge[j,1]) then father[father[edge[j,2]]]:=father[father[edge[j,1]]];
         inc(j);
      end;
      if getfather(s)=getfather(t) then
      begin
         dec(j);
         if (pmax/pmin>edge[j,3]/edge[i,3]) then
         begin
            pmax:=edge[j,3];
            pmin:=edge[i,3];
         end;
      end;

   end;



   if pmax=50000000 then writeln('IMPOSSIBLE')
   else if (pmax mod pmin=0) then writeln(pmax div pmin)
   else
   begin
      i:=gcd(pmax,pmin);
      pmax:=pmax div i;pmin:=pmin div i;
      writeln(pmax,'/',pmin);
   end;

end.

HYSBZ 1616（纯深搜）

Posted on by

题目大意：一张图G，有一些障碍物，求路径长度一定（可环）时的路径总数

果断广搜

Program ttd;
var
   n,m,t,i,j,k,x1,x2,y1,y2:longint;
   s:string;
   b:array[0..101,0..101] of boolean;

   f:array[0..15,0..101,0..101] of longint;
begin
   readln(n,m,t);
   fillchar(b,sizeof(b),true);
   for i:=1 to n do
   begin
      readln(s);
      for j:=1 to m do if s[j]='*' then b[i,j]:=false;
   end;
   readln(x1,y1,x2,y2);
   fillchar(f,sizeof(f),0);
   f[0,x1,y1]:=1;

   for k:=1 to t do
   begin
      for i:=1 to n do
         for j:=1 to m do
            if f[k-1,i,j]>0 then
            begin
               if b[i+1,j] then inc(f[k,i+1,j],f[k-1,i,j]);
               if b[i-1,j] then inc(f[k,i-1,j],f[k-1,i,j]);
               if b[i,j+1] then inc(f[k,i,j+1],f[k-1,i,j]);
               if b[i,j-1] then inc(f[k,i,j-1],f[k-1,i,j]);



            end;


   end;
             {
   for k:=0 to t do
   begin
   for i:=1 to n do
   begin
      for j:=1 to m do
      begin
         write(f[k,i,j],' ');
      end;
      writeln;
      end;
      writeln;
   end;
            }
   writeln(f[t,x2,y2]);


end.

HYSBZ 1601(单点带值的最小生成树）

Posted on by

题目大意：最小生成树

建源点0与各点连线的权为建水库的大小。

Program aa;
var
   n,i,j,p:longint;
   u,v,w:array[0..100000] of longint;
   size,cost:longint;
   father:array[0..300] of longint;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;j:=r;m:=w[(l+r) shr 1];
   repeat
      while w[i]<m do inc(i);
      while w[j]>m do dec(j);
      if i<=j then
      begin
         p:=w[i];w[i]:=w[j];w[j]:=p;
         p:=u[i];u[i]:=u[j];u[j]:=p;
         p:=v[i];v[i]:=v[j];v[j]:=p;
         inc(i);dec(j);
      end;
   until i>j;
   if l<j then qsort(l,j);
   if i<r then qsort(i,r);
end;
function getfather(x:longint):longint;
begin
   if father[x]=x then exit(x);
   father[x]:=getfather(father[x]);
   exit(father[x]);
end;
begin
   read(n);
   for i:=1 to n do
   begin
      read(w[i]);
      u[i]:=0;v[i]:=i;
   end;
   size:=n;
   for i:=1 to n do
      for j:=1 to n do
      begin
        read(p);
        if i=j then continue;
        inc(size);
        u[size]:=i;v[size]:=j;w[size]:=p;
      end;


   qsort(1,size);

   cost:=0;
   for i:=0 to n do father[i]:=i;
   for i:=1 to size do
   begin
      if (getfather(u[i])<>getfather(v[i])) then
      begin
         inc(cost,w[i]);
         father[getfather(u[i])]:=father[getfather(v[i])];
      end;
   end;


   writeln(cost);


end.