Monthly Archives: 8 月 2012

POJ 2528（数据有误的线段树）

Posted on by

此题数据有误……

是我英文太差，还是答案出错……

Program P2528;
const
   maxn=10000;
   maxr=10000000;
var
   t,n,i,j,k:longint;
   a,b,v:array[1..maxn*2] of longint;
   h:array[1..maxr] of longint;
   col:array[1..maxn*100] of longint;
   visit:array[1..maxn*2] of boolean;


procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=v[(l+r) div 2];
   repeat
      while v[i]<m do inc(i);
      while v[j]>m do dec(j);
      if i<=j then
      begin
         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;
procedure update(l,r,sonl,sonr,root,color:longint);
var
   i,j,k,mid:longint;
begin
   mid:=(l+r) shr 1;
   if (sonl<=l) and (r<=sonr) then
   begin
      col[root]:=color;
      exit;
   end;

   if (col[root]>=0) then
   begin
      col[root*2]:=col[root];
      col[root*2+1]:=col[root];
      col[root]:=-1;
   end;
   if not((mid<sonl) or (sonr<l)) then update(l,mid,sonl,sonr,root*2,color);
   if not((r<sonl) or (sonr<mid+1)) then update(mid+1,r,sonl,sonr,root*2+1,color);



end;
function dfs(l,r,root:longint):longint;
var
   i,j,mid:longint;
begin
   mid:=(l+r) shr 1;
   if col[root]=0 then exit(0);
   if col[root]>0 then
   begin
      if not(visit[col[root]]) then
      begin
         visit[col[root]]:=true;
         exit(1);
      end
      else exit(0);
   end;

   exit(dfs(l,mid,root*2)+dfs(mid+1,r,root*2+1));

end;
begin
   read(t);
   while t>0 do
   begin
      dec(t);
      read(n);
      for i:=1 to n do
      begin
         read(a[i],b[i]);
         v[i]:=a[i];
         v[n+i]:=b[i];
      end;
      qsort(1,2*n);
      j:=1;
      for i:=2 to 2*n do
         if v[i]<>v[i-1] then
         begin
            inc(j);
            v[j]:=v[i];
         end;
      for i:=1 to j do h[v[i]]:=i;

      fillchar(col,sizeof(col),0);

      for i:=1 to n do
      begin
        update(1,j,h[a[i]],h[b[i]],1,i);
      end;
      fillchar(visit,sizeof(visit),false);
      writeln(dfs(1,j,1));

   end;
end.

POJ 2209（阅读理解）

Posted on by

这题题目看不懂……用谷歌翻译完，更看不懂……

对A此题不看Discuss的神语言流表示膜拜

Program P2209;
var
   n,p,s,ans,i:longint;
begin
   read(n,p);
   ans:=0;
   for i:=1 to n do
   begin
      read(s);
      if p=2 then s:=s*s;
      if p=3 then s:=s*s*s;
      if s>0 then inc(ans,s);
   end;
   writeln(ans);
end.

POJ 2823(双端队列）

Posted on by

这题考双端队列……好偏门的数据结构……

Program c;
const
    maxn=1000000;
type
   node=record
        num,d:longint;
        end;
   douq=record
        d:array[1..maxn] of node;
        l,r:longint;
        end;

var
   n,k,i,j:longint;
   a:array[1..maxn] of longint;
   ans1,ans2:array[1..maxn] of longint;
   minq,maxq:douq;
procedure push(var q:douq;num2,d2:longint);
begin
   with q do
   begin
      inc(r);
      d[q.r].num:=num2;
      d[q.r].d:=d2;
   end;
end;
procedure popl(var q:douq;i:longint);
begin
   with q do
   begin
      if d[l].num=i then inc(l);
   end;
end;
procedure popr(up,i:longint);
var
   j:longint;
begin
   if up=1 then
   begin
      with minq do
      begin
         while (l<r) and (d[r].d>i) do dec(r);
         if l=r then
         if d[r].d>i then dec(r);

      end;
   end
   else
   begin
      with maxq do
      begin
         while (l<r) and (d[r].d<i) do dec(r);
         if l=r then
         if d[r].d<i then dec(r);
      end;

   end;
end;
begin
   read(n,k);
   for i:=1 to n do read(a[i]);
   fillchar(minq,sizeof(minq),0);
   minq.l:=1;
   fillchar(maxq,sizeof(maxq),0);
   maxq.l:=1;
   if k=1 then
   begin
      for i:=1 to n-1 do write(a[i],' ');
      writeln(a[n]);
      for i:=1 to n-1 do write(a[i],' ');
      writeln(a[n]);
   end
   else
   begin
      for i:=1 to k do
      begin
         popr(1,a[i]);
         push(minq,i,a[i]);
         popr(0,a[i]);
         push(maxq,i,a[i]);
      end;
      ans1[1]:=minq.d[minq.l].d;
      ans2[1]:=maxq.d[maxq.l].d;
      for i:=k+1 to n do
      begin
         popl(minq,i-k);
         popl(maxq,i-k);
         popr(1,a[i]);
         push(minq,i,a[i]);
         popr(0,a[i]);
         push(maxq,i,a[i]);
         ans1[i-k+1]:=minq.d[minq.l].d;
         ans2[i-k+1]:=maxq.d[maxq.l].d;


      end;
      for i:=1 to n-k do write(ans1[i],' ');
      writeln(ans1[n-k+1]);
      for i:=1 to n-k do write(ans2[i],' ');
      writeln(ans2[n-k+1]);
   end;
end.

POJ 2195(多源多汇最小费用最大流）

Posted on by

这题 居然一次就过了^_^

Program P2195;
const
   maxn=200;
   maxm=200;
   maxh=200;
   maxd=1000;
var
   n,m,i,j,k,ut,vt:longint;
   s:string;
   form:array[1..maxn,1..maxm] of longint;
   u,v:array[1..maxh,1..2] of longint;

   map,f,cost:array[0..maxd,0..maxd] of longint;
   b:array[0..maxd] of boolean;
   q:array[1..maxd*5] of longint;
   d,pre:array[0..maxd] of longint;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
procedure spfa;
var
   i,j,h,t,now:longint;
begin
   fillchar(d,sizeof(d),127);
   fillchar(b,sizeof(b),false);
   fillchar(pre,sizeof(pre),0);
   d[0]:=0;
   b[0]:=true;
   h:=1;t:=1;
   q[1]:=0;
   while h<=t do
   begin
      now:=q[h];
      for i:=0 to 2*ut+1 do
         if (map[now,i]-f[now,i]>0) then
            if (d[now]+cost[now,i]<d[i]) then
            begin
               d[i]:=d[now]+cost[now,i];
               pre[i]:=now;
               if not(b[i]) then
               begin
                  b[i]:=true;
                  inc(t);
                  q[t]:=i;
               end;
            end;

      b[now]:=false;
      inc(h);
   end;

end;
function hllp:longint;
var
   i,j,k,flow,totalcost,nowcost:longint;
begin
   hllp:=0;
   totalcost:=0;
   while (true) do
   begin
      spfa;
      if d[ut*2+1]=2139062143 then exit(totalcost);
      flow:=maxlongint;
      i:=ut*2+1;
      repeat
         flow:=min(map[pre[i],i]-f[pre[i],i],flow);
         i:=pre[i];
      until i=0;
      i:=ut*2+1;
      nowcost:=0;
      repeat
         inc(f[pre[i],i],flow);
         f[i,pre[i]]:=-f[pre[i],i];
         inc(nowcost,cost[pre[i],i]);
         i:=pre[i];

      until i=0;
      inc(totalcost,nowcost*flow);

   end;
end;
function main:longint;
var
   i,j,k:longint;
begin
   main:=0;
   fillchar(map,sizeof(map),0);
   fillchar(f,sizeof(f),0);
   fillchar(cost,sizeof(cost),0);
   for i:=1 to ut do map[0,i]:=1;
   for i:=ut+1 to ut+vt do map[i,ut+vt+1]:=1;
   for i:=1 to ut do
      for j:=ut+1 to ut+vt do
      begin
         map[i,j]:=1;
         cost[i,j]:=abs(u[i,1]-v[j-ut,1])+abs(u[i,2]-v[j-ut,2]);
         cost[j,i]:=-cost[i,j];
      end;
   main:=hllp;
end;
begin
   while not eof do
   begin
      readln(n,m);
      if (n=0) and (m=0) then break;
      ut:=0;
      vt:=0;
      for i:=1 to n do
      begin
         readln(s);
         for j:=1 to m do
            if s[j]='m'  then
            begin
               inc(ut);
               u[ut,1]:=i;
               u[ut,2]:=j;
            end
            else if s[j]='H' then
            begin
               inc(vt);
               v[vt,1]:=i;
               v[vt,2]:=j;
            end;
      end;
      writeln(main);

   end;
end.

POJ 2516(最小费用最大流）

Posted on by

一开始居然忘添反向边……

Program P2516;
const
   maxn=100;
   maxm=100;
   maxk=100;
var
   n,m,k,i,j,l,maxflow:longint;
   need,prod:array[1..maxn,1..maxk] of longint;
   needk,prodk:array[1..maxk] of longint;
   fee:array[1..maxk,1..maxn,1..maxm] of longint;

   cost,map,f:array[0..200,0..200] of longint;

   b:array[0..200] of boolean;
   d,pre:array[0..200] of longint;
   q:array[1..500000] of longint;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure spfa;
var
   i,j,l,h,t,now:longint;
begin
   fillchar(d,sizeof(d),127);
   fillchar(b,sizeof(b),false);
   fillchar(pre,sizeof(pre),0);
   d[0]:=0;
   b[0]:=true;
   q[1]:=0;
   h:=1;t:=1;
   while h<=t do
   begin
      now:=q[h];
      for i:=0 to n+m+1 do
         if (map[now,i]-f[now,i]>0) then
            if (d[now]+cost[now,i]<d[i]) then
            begin
               d[i]:=d[now]+cost[now,i];
               pre[i]:=now;
               if not(b[i]) then
               begin
                  b[i]:=true;
                  inc(t);
                  q[t]:=i;
               end;
            end;


      b[now]:=false;
      inc(h);
   end;


end;
function hllp:longint;
var
   i,j,l,flow,totalflow,p:longint;
   totalcost,nowcost:longint;
begin
   hllp:=0;
   totalflow:=0;
   totalcost:=0;
   while (true) do
   begin
      spfa;
      if d[n+m+1]=2139062143 then exit(totalcost);
      flow:=maxlongint;
      i:=n+m+1;

      repeat
         flow:=min(flow,map[pre[i],i]-f[pre[i],i]);
         i:=pre[i];
      until i=0;

      nowcost:=0;
      i:=n+m+1;
      repeat
         inc(f[pre[i],i],flow);
         f[i,pre[i]]:=-f[pre[i],i];
         inc(nowcost,cost[pre[i],i]);
         i:=pre[i];
      until i=0;
      inc(totalcost,nowcost*flow);
   end;
end;
function main:longint;
var
   i,j,l,s,t:longint;
begin
   main:=0;
   for i:=1 to k do if prodk[i]<needk[i] then exit(-1);
   for i:=1 to k do
   begin
      fillchar(cost,sizeof(cost),0);
      fillchar(map,sizeof(map),0);
      fillchar(f,sizeof(f),0);
      s:=0;
      t:=n+m+1;
      for j:=1 to m do map[s,j]:=prod[j,i];
      for j:=1 to n do map[m+j,t]:=need[j,i];
      for j:=1 to m do
         for l:=1 to n do
         begin
            map[j,m+l]:=prod[j,i];
            cost[j,m+l]:=fee[i,l,j];
            cost[m+l,j]:=-cost[j,m+l];
         end;
      main:=main+hllp;

   end;

end;
begin
   while not seekeof do
   begin
      read(n,m,k);
      if (n=0) and (m=0) and (k=0) then break;

      fillchar(needk,sizeof(needk),0);
      fillchar(prodk,sizeof(prodk),0);

      for i:=1 to n do
         for j:=1 to k do
         begin
            read(need[i,j]);
            inc(needk[j],need[i,j]);
         end;
      for i:=1 to m do
         for j:=1 to k do
         begin
            read(prod[i,j]);
            inc(prodk[j],prod[i,j]);
         end;
      for i:=1 to k do
         for j:=1 to n do
            for l:=1 to m do
            begin
               read(fee[i,j,l]);
            end;
     writeln(main);



   end;
end.

POJ 1061(exgcd)

Posted on by

这题是exgcd……

我居然连wa了2天……

至少知道DIV函数的性质了   （-x) div t =-(x div t)    

                           (-x) div (-t) = (x div t)

发现自己数论蒟蒻……

Program p1061;
var
   x,y,n,m,l,t:int64;
   a,b,c,c2:int64;
function exgcd(a,b:int64):int64;
var
   x1,y1:longint;
begin
   if b=0 then
   begin
      x:=1;
      y:=0;
      exit(a);
   end;
   exgcd:=exgcd(b,a mod b);
   x1:=y;
   y1:=x-(a div b)*y;
   x:=x1;
   y:=y1;
end;
begin

   read(x,y,m,n,l);
   a:=n-m;
   c:=x-y;
   b:=l;
   c2:=exgcd(a,b);
   if (c mod c2<>0) then writeln('Impossible')
   else
   begin
      x:=x*(c div c2);
      y:=y*(c div c2);
      t:=b div c2;


      if t<0 then
         while (x<0) do
         begin

            x:=x-t*abs(x div t)-t;
         end;
      if t>0 then while (x<0) do x:=x+t*abs(x div t)+t;

      x:=x mod (b div c2);
      writeln(x);
   end;


end.

POJ 1018（多关键字排序还在wa…）

Posted on by

哪为朋友帮我看看多关键字排序哪儿错了……

Program P1018;
type
   product=record
           b,id:longint;
           p:longint;
           end;
var
   t,n,i,j,total,count,maxb,mintb,price:longint;
   visit:array[1..100] of longint;
   m:array[1..100] of longint;
   a:array[1..100000] of product;
   ans:double;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
function min(a,b:longint):longint;
begin
   if a>b then exit(b) else exit(a);
end;

procedure qsort(l,r:longint);
var
   i,j:longint;
   m,p:product;
begin
   i:=l;
   j:=r;
   m:=a[(l+r) div 2];
   repeat
      while a[i].b<m.b do inc(i);
 //     while (a[i].p<m.p) and (a[i].b=m.b) do inc(i);
 //     while (a[i].id<m.id) and (a[i].b=m.b) and (a[i].p=m.p) do inc(i);

      while a[j].b>m.b do dec(j);
//      while (a[j].p>m.p) and (a[j].b=m.b) do dec(j);
//      while (a[j].id>m.id) and (a[j].b=m.b) and (a[j].p=m.p) do dec(j);
      if i<=j then
      begin
         p:=a[i];
         a[i]:=a[j];
         a[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;
begin
  { assign(input,'p1018.in');
   assign(output,'p1018.out');
   reset(input);
   rewrite(output);
  }read(t);

   while t>0 do
   begin
      total:=0;
      read(n);
      mintb:=maxlongint;
      for i:=1 to n do
      begin
         read(m[i]);
         maxb:=0;
         for j:=1 to m[i] do
         begin
            inc(total);
            a[total].id:=i;
            read(a[total].b,a[total].p);
            maxb:=max(a[total].b,maxb);
         end;
         mintb:=min(maxb,mintb);
      end;
      qsort(1,total);
      ans:=0;
      for i:=1 to total-n+1 do
      begin
         if a[i].b>mintb then break;
         count:=0;
         fillchar(visit,sizeof(visit),0);
         visit[a[i].id]:=a[i].p;
         for j:=i+1 to total do
         begin
            if a[j].b<a[i].b then write('x');
            if (visit[a[j].id]=0) then
            begin
               inc(count);
               visit[a[j].id]:=a[j].p;
            end;
            visit[a[j].id]:=min(visit[a[j].id],a[j].p);
         end;
         if count<n-1 then break;
         price:=0;
         for j:=1 to n do inc(price,visit[j]);
         if ans<(a[i].b/price) then ans:=a[i].b/price;
      end;
      writeln(ans:3:3);

      dec(t);
   end;
{
   close(input);
   close(output);    }
end.

POJ 3259(负权回路）

Posted on by

注意普通路径是双向的

program P3259;
var
   f,n,m,w,i,j:longint;
   s,e,t:longint;
   map:array[1..2500,1..3] of longint;
   wmap:array[1..300,1..3] of longint;
   d:array[1..2500] of longint;
   flag:boolean;
procedure relax(u,v,w:longint);
begin
   if (d[v]>d[u]+w) then
   begin
      d[v]:=d[u]+w;
      flag:=false;
   end;
end;
procedure bellman_ford;
var
   i,j:longint;
begin
   for i:=1 to n do
   begin
      flag:=true;
      for j:=1 to m do
      begin
         relax(map[j,1],map[j,2],map[j,3]);
         relax(map[j,2],map[j,1],map[j,3]);

      end;
      for j:=1 to w do relax(wmap[j,1],wmap[j,2],-wmap[j,3]);
      if flag then break;
   end;

   if flag then writeln('NO') else writeln('YES');
end;
begin
   read(f);
   while f>0 do
   begin
      fillchar(map,sizeof(map),0);
      fillchar(wmap,sizeof(wmap),0);
      fillchar(d,sizeof(d),0);

      read(n,m,w);
      for i:=1 to m do
      begin
         read(map[i,1],map[i,2],map[i,3]);
      end;
      for i:=1 to w do read(wmap[i,1],wmap[i,2],wmap[i,3]);
      bellman_ford;
      dec(f);
   end;
end.

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.