分享三道题目的代码+JavaScript Syntax Highlight测试

    寒假时没事写了这几个代码,算是我几个月后重操键盘了。这是几道经典题目,可能有人需要,再加上昨天搞JavaScript改过去改过来把PJBlog改得面目全非终于实现了代码高亮忍不住想Show一下,于是把这些代码(连同题目)发了上来。

标准的网络流题目代码

Problem : goods
货物运输

问题描述
    你第一天接手一个大型商业公司就发生了一件倒霉的事情:公司不小心发送了一批次品。很不幸,你发现这件事的时候,这些次品已经进入了送货网。这个送货网很大,而且关系复杂。你知道这批次品要发给哪个零售商,但是要把这批次品送到他手中有许多种途径。送货网由一些仓库和运输卡车组成,每辆卡车都在各自固定的两个仓库之间单向运输货物。在追查这些次品的时候,有必要保证它不被送到零售商手里,所以必须使某些运输卡车停止运输,但是停止每辆卡车都会有一定的经济损失。你的任务是,在保证次品无法送到零售商的前提下,制定出停止卡车运输的方案,使损失最小。

输入格式
    第一行:两个用空格分开的整数N(0<=N<=200)和M(2<=M<=200)。N为运输卡车的数目,M为仓库的数目。1号仓库是公司发货的出口,仓库M属于零售商。
    第二行到第N+1行:每行有三个整数,Si、Ei和Ci。Si和Ei(1<=Si,Ei<=M)分别表示这辆卡车的出发仓库和目的仓库,Ci(0<=Ci<=10,000,000)是让这辆卡车停止运输的损失。

输出格式
    输出一个整数,即最小的损失数。

样例输入
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

样例输出
50

样例说明
         40
      1——>2
      |      /|
      |     / |
    20|    /  |30
      |  20   |
      |  /    |
      | /     |
      /_     V
      4<——3
          10

    如图,停止1->4、2->4、3->4三条卡车运输线路可以阻止货物从仓库1运输到仓库4,代价为20+20+10=50。

数据规模
    对于50%的数据,N,M<=25
    对于100%的数据,N,M<=200

program goods;

const
   MaxN=200;
   MaxM=200;
   Infinite=Maxlongint;

type
   rec=record
         node,father:integer;
         minf:longint;
       end;

var
   f,c:array[1..MaxN,1..MaxN]of longint;
   queue:array[1..MaxN]of rec;
   hash:array[1..MaxN]of boolean;
   n,m,closed,open:integer;

procedure readp;
var
   i,x,y:integer;
   t:longint;
begin
   readln(m,n);
   for i:=1 to m do
   begin
      readln(x,y,t);
      c[x,y]:=c[x,y]+t;
   end;
end;

function FindPath:boolean;

   procedure Init;
   begin
      fillchar(hash,sizeof(hash),0);
      fillchar(queue,sizeof(queue),0);
      closed:=0;
      open:=1;
      queue[1].node:=1;
      queue[1].father:=0;
      queue[1].minf:=Infinite;
      hash[1]:=true;
   end;

   function min(a,b:longint):longint;
   begin
      if a<b then min:=a
      else min:=b;
   end;

var
   i,NodeNow:integer;
begin
   Init;
   repeat
      inc(closed);
      NodeNow:=queue[closed].node;
      for i:=1 to n do if not hash[i] then
         if (f[NodeNow,i]<c[NodeNow,i]) then
         begin
            inc(open);
            queue[open].node:=i;
            queue[open].father:=closed;
            queue[open].minf:=min(queue[closed].minf,c[NodeNow,i]-f[NodeNow,i]);
            hash[i]:=true;
            if i=n then exit(true);
         end;
   until closed>=open;
   exit(false);
end;

procedure AddPath;
var
   i,j:integer;
   delta:longint;
begin
   delta:=queue[open].minf;
   i:=open;
   repeat
      j:=queue[i].father;
      inc(f[queue[j].node,queue[i].node],delta);
      dec(f[queue[i].node,queue[j].node],delta);
      i:=j;
   until i=0;
end;

procedure writep;
var
   i:integer;
   ans:longint=0;
begin
   for i:=1 to n do
      ans:=ans+f[1,i];
   writeln(ans);
end;

{====main====}
begin
   assign(input,'goods.in');
   reset(input);
   readp;
   close(input);

   while FindPath do AddPath;

   assign(output,'goods.out');
   rewrite(output);
   writep;
   close(output);
end.

统计逆序对 Treap版

Problem : inverse
逆序对

问题描述
    在一个排列中,前面出现的某个数比它后面的某个数大,即当Ai>Aj且i<j时,则我们称Ai和Aj为一个逆序对。给出一个1到N的排列,编程求出逆序对的个数。

输入格式
    第一行输入一个正整数N;
    第二行有N个用空格隔开的正整数,这是一个1到N的排列。

输出格式
    输出输入数据中逆序对的个数。

样例输入
4
3 1 4 2

样例输出
3

样例说明
    在输入数据中,(3,1)、(3,2)和(4,2)是仅有的三个逆序对。

数据规模
    对于30%的数据,N<=1000;
    对于100%的数据,N<=100 000。
program inverse;

const
   MaxH=Maxlongint;
  
type
   p=^rec;
   rec=record
          v,s,h:longint;
          left,right:p;
       end;

var
   header:p=nil;
   ans:int64=0;

procedure CalcuS(var w:p);
begin
   w^.s:=1;
   if w^.right<>nil then inc(w^.s,w^.right^.s);
   if w^.left<>nil then inc(w^.s,w^.left^.s);
end;

function RotateLeft(w:p):p;
var
   tmp:p;
begin
   tmp:=w^.left;
   w^.left:=tmp^.right;
   tmp^.right:=w;
   exit(tmp);
end;

function RotateRight(w:p):p;
var
   tmp:p;
begin
   tmp:=w^.right;
   w^.right:=tmp^.left;
   tmp^.left:=w;
   exit(tmp);
end;

function Insert(a:longint;w:p):p;
begin
  if w=nil then
  begin
     new(w);
     w^.v:=a;
     w^.h:=random(MaxH);
     w^.s:=1;
     w^.left:=nil;
     w^.right:=nil;
  end

  else if a<w^.v then
  begin
     ans:=ans+1;
     if w^.right<>nil then ans:=ans+w^.right^.s;
     w^.left:=Insert(a,w^.left);
     if w^.left^.h<w^.h then
     begin
        w:=RotateLeft(w);
        CalcuS(w^.right);
     end else
        CalcuS(w^.left);
  end

  else if a>w^.v then
  begin
     w^.right:=Insert(a,w^.right);
     if w^.right^.h<w^.h then
     begin
        w:=RotateRight(w);
        CalcuS(w^.left);
     end else
        CalcuS(w^.right);
  end;

  exit(w);
end;

{====main====}
var
   n,i,t:longint;
begin
   randseed:=2910238;
  
   assign(input,'inverse.in');
   reset(input);
   readln(n);
   for i:=1 to n do
   begin
      read(t);
      header:=Insert(t,header);
   end;
   close(input);

   assign(output,'inverse.out');
   rewrite(output);
   writeln(ans);
   close(output);
end.

USACO经典题目:矩形颜色(离散化+扫描)

Problem : rect
矩形颜色

问题描述
  N个不同颜色的不透明长方形(1<=N<=1000)被放置在一张宽为A长为B的白纸上。这些长方形被放置时,保证了它们的边与白纸的边缘平行。所有的长方形都放置在白纸内,所以我们会看到不同形状的各种颜色。坐标系统的原点(0,0)设在这张白纸的左下角,而坐标轴则平行于边缘。

输入数据
    每行输入的是放置长方形的方法。第一行输入的是那个放在最底下的长方形(即白纸)。
    第一行:A、B和N,由空格分开(1<=A,B<=10,000)
    第二到N+1行:每行为五个整数llx,lly,urx,ury,color。这是一个长方形的左下角坐标,右上角坐标和颜色。颜色1和底部白纸的颜色相同。

输出数据
    输出文件应该包含一个所有能被看到的颜色连同该颜色的总面积的清单(即使颜色的区域不是连续的),按color的增序顺序。
    不要打印出最后不能看到的颜色。

样例输入
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

样例输出
1 91
2 84
3 187
4 38

数据规模
    对于50%的数据,A,B<=300,N<=60;
    对于100%的数据,A,B<=10000,N<=1000。

program rect;

const
   MaxN=1000;       { Rect number in the Worst Case }
   MaxCol=1000;     { Color number in the Worst Case }
   Infinity=Maxint; { Set to be Heap[0] }

type
   RecSeg=record
            y,x1,x2,order:integer;
          end;
var
   xar,heap:array[0..MaxN*2+2]of integer; { Array of All X-Value and Heap, respectively }
   color:array[1..MaxN+1]of integer;      { Index of Color corresponding to order}
   ans:array[1..MaxCol]of longint;        { Answers to be print }
   seg:array[0..MaxN*2+2]of RecSeg;       { Horizontal Segments }
   hash:array[1..MaxN*2+2]of boolean;     { Determine if a Segment has been scanned }
   n,HeapSize:integer;

procedure SwapInt(var a,b:integer);
var
   tmp:integer;
begin
   tmp:=a;
   a:=b;
   b:=tmp;
end;

procedure SwapRec(var a,b:RecSeg);
var
   tmp:RecSeg;
begin
   tmp:=a;
   a:=b;
   b:=tmp;
end;

procedure DataInsert(start,x1,y1,x2,y2,col,order:integer);
var
   tmp:RecSeg;
begin
   xar[start]:=x1;
   xar[start+1]:=x2;
   color[start div 2+1]:=col;

   tmp.order:=order;
   tmp.y:=y1;
   tmp.x1:=x1;
   tmp.x2:=x2;
   seg[start]:=tmp;

   tmp.y:=y2;
   seg[start+1]:=tmp;
end;

procedure Readp;
var
   a,b,x1,x2,y1,y2,col,i:integer;
begin
   readln(a,b,n);
   n:=n+1;
   DataInsert(1,0,0,a,b,1,1);
   for i:=2 to n do
   begin
      readln(x1,y1,x2,y2,col);
      DataInsert(2*i-1,x1,y1,x2,y2,col,i);
   end;
end;

procedure SortXar;
var
   i,j:integer;
begin
   for i:=1 to 2*n do
   for j:=1 to 2*n-1 do
      if xar[j]>xar[j+1] then SwapInt(xar[j],xar[j+1]);
end;

procedure SortSeg;
var
   i,j:integer;
begin
   for i:=1 to 2*n do
   for j:=1 to 2*n-1 do
      if seg[j].y>seg[j+1].y then SwapRec(seg[j],seg[j+1]);
end;

procedure HeapInsert(x:integer);
var
   w:integer;
begin
   inc(HeapSize);
   w:=HeapSize;
   while Heap[w shr 1]<x do
   begin
      Heap[w]:=Heap[w shr 1];
      w:=w shr 1;
   end;
   Heap[w]:=x;
end;

procedure HeapDelete;
var
&n
bsp;  x:integer;
   w:integer=1;
begin
   x:=Heap[HeapSize];
   dec(HeapSize);
   while w shl 1<=HeapSize do
   begin
      w:=w shl 1;
      if (w<>HeapSize) and (Heap[w+1]>Heap[w]) then inc(w);
      if Heap[w]>x then Heap[w shr 1]:=Heap[w]
      else begin
         w:=w shr 1;
         break;
      end;
   end;
   Heap[w]:=x;
end;

procedure Scan(x1,x2:integer);
var
   i:integer;
   j:integer=0;
begin
   for i:=1 to 2*n do if (seg[i].x1<=x1) and (seg[i].x2>=x2) then
   begin
      inc(ans[Color[Heap[1]]],(x2-x1)*(seg[i].y-seg[j].y));
      hash[seg[i].order]:=not hash[seg[i].order];
      if hash[seg[i].order] then HeapInsert(seg[i].order)
         else while (HeapSize>0) and not hash[Heap[1]] do HeapDelete;
      j:=i;
   end;
end;

procedure Solve;
var
   i:integer;
begin
   for i:=1 to 2*n-1 do if xar[i]<xar[i+1] then
   begin
      fillchar(Heap,Sizeof(Heap),0);
      fillchar(hash,Sizeof(hash),0);
      HeapSize:=0;
      Heap[0]:=Infinity;
      Scan(xar[i],xar[i+1]);
   end;
end;

procedure Writep;
var
   i:integer;
begin
   for i:=1 to MaxCol do
      if ans[i]>0 then writeln(i,' ',ans[i]);
end;

{====main====}
begin
   assign(input,'rect.in');
   reset(input);
   assign(output,'rect.out');
   rewrite(output);

   Readp;
   SortXar;
   SortSeg;
   Solve;
   Writep;

   close(input);
   close(output);
end.

    这几天大家发现我改PJBlog改错了什么东西导致Bug的话麻烦帮忙报告一下。事实上很有可能有人发现有Bug但是不能报告,因为我很有可能把验证码系统也搞坏了。
    如果这几天大家没有发现问题的话,我把这几天我的PJBlog个性修改方法和心得写出来分享一下(越来越喜欢搞Web Design了)。

做人要厚道
转贴请注明出处
(这篇日志没什么技术含量,感觉写上这两句很别扭)

什么是离散化?

    如果说今年这时候OIBH问得最多的问题是二分图,那么去年这时候问得最多的算是离散化了。对于“什么是离散化”,搜索帖子你会发现有各种说法,比如“排序后处理”、“对坐标的近似处理”等等。哪个是对的呢?哪个都对。关键在于,这需要一些例子和不少的讲解才能完全解释清楚。
    离散化是程序设计中一个非常常用的技巧,它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。下面我将用三个例子说明,如何运用离散化改进一个低效的,甚至根本不可能实现的算法。

    《算法艺术与信息学竞赛》中的计算几何部分,黄亮举了一个经典的例子,我认为很适合用来介绍离散化思想。这个问题是UVA10173(http://acm.uva.es/p/v101/10173.html),题目意思很简单,给定平面上n个点的坐标,求能够覆盖所有这些点的最小矩形面积。这个问题难就难在,这个矩形可以倾斜放置(边不必平行于坐标轴)。
      
    这里的倾斜放置很不好处理,因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α,那么答案就很简单了:矩形面积最小时四条边一定都挨着某个点。也就是说,四条边的斜率已经都知道了的话,只需要让这些边从外面不断逼近这个点集直到碰到了某个点。你不必知道这个具体应该怎么实现,只需要理解这可以通过某种方法计算出来,毕竟我们的重点在下面的过程。
    我们的算法很显然了:枚举矩形的倾角,对于每一个倾角,我们都能计算出最小的矩形面积,最后取一个最小值。
    这个算法是否是正确的呢?我们不能说它是否正确,因为它根本不可能实现。矩形的倾角是一个实数,它有无数种可能,你永远不可能枚举每一种情况。我们说,矩形的倾角是一个“连续的”变量,它是我们无法枚举这个倾角的根本原因。我们需要一种方法,把这个“连续的”变量变成一个一个的值,变成一个“离散的”变量。这个过程也就是所谓的离散化。
    我们可以证明,最小面积的矩形不但要求四条边上都有一个点,而且还要求至少一条边上有两个或两个以上的点。试想,如果每条边上都只有一个点,则我们总可以把这个矩形旋转一点使得这个矩形变“松”,从而有余地得到更小的矩形。于是我们发现,矩形的某条边的斜率必然与某两点的连线相同。如果我们计算出了所有过两点的直线的倾角,那么α的取值只有可能是这些倾角或它减去90度后的角(直线按“”方向倾斜时)这么C(n,2)种。我们说,这个“倾角”已经被我们 “离散化”了。虽然这个算法仍然有优化的余地,但此时我们已经达到了本文开头所说的目的。

    对于某些坐标虽然已经是整数(已经是离散的了)但范围极大的问题,我们也可以用离散化的思想缩小这个规模。最近搞模拟赛Vijos似乎火了一把,我就拿两道Vijos的题开刀。
    VOJ1056(http://www.vijos.cn/Problem_Show.asp?id=1056) 永远是离散化的经典问题。大意是给定平面上的n个矩形(坐标为整数,矩形与矩形之间可能有重叠的部分),求其覆盖的总面积。平常的想法就是开一个与二维坐标规模相当的二维Boolean数组模拟矩形的“覆盖”(把矩形所在的位置填上True)。可惜这个想法在这里有些问题,因为这个题目中坐标范围相当大(坐标范围为-10^8到10^8之间的整数)。但我们发现,矩形的数量n<=100远远小于坐标范围。每个矩形会在横纵坐标上各“使用”两个值, 100个矩形的坐标也不过用了-10^8到10^8之间的200个值。也就是说,实际有用的值其实只有这么几个。这些值将作为新的坐标值重新划分整个平面,省去中间的若干坐标值没有影响。我们可以将坐标范围“离散化”到1到200之间的数,于是一个200*200的二维数组就足够了。实现方法正如本文开头所说的“排序后处理”。对横坐标(或纵坐标)进行一次排序并映射为1到2n的整数,同时记录新坐标的每两个相邻坐标之间在离散化前实际的距离是多少。这道题同样有优化的余地。
    最后简单讲一下计算几何以外的一个运用实例(实质仍然是坐标的离散)。才考的VOJ1238(http://www.vijos.cn/Problem_Show.asp?id=1238)中,标程开了一个与时间范围一样大的数组来储存时间段的位置。这种方法在空间上来看十分危险。一旦时间取值范围再大一点,盲目的空间开销将导致Memory Limit Exceeded。我们完全可以采用离散化避免这种情况。我们对所有给出的时间坐标进行一次排序,然后同样用时间段的开始点和结束点来计算每个时刻的游戏数,只是一次性加的经验值数将乘以排序后这两个相邻时间点的实际差。这样,一个1..n的数组就足够了。

    离散化的应用相当广泛,以后你会看到还有很多其它的用途。

2007.04.05补充:
VOJ1056那个例子看来还是有人不明白。
我发一张示意图,注意左边的10*7的数组是如何等价地转化为右边两个4*4的数组的

Matrix67原创
转载请注明出处