今天我正式开始按照我的目录写我的OI心得了。我要把我所有学到的OI知识传给以后千千万万的OIer。以前写过的一些东西不重复写了，但我最后将会重新整理，使之成为一个完整的教程。
    按照我的目录，讲任何东西之前我都会先介绍时间复杂度的相关知识，以后动不动就会扯到这个东西。这个已经写过了，你可以在这里看到那篇又臭又长的文章。在讲排序算法的过程中，我们将始终围绕时间复杂度的内容进行说明。
    我把这篇文章称之为“从零开始学算法”，因为排序算法是最基础的算法，介绍算法时从各种排序算法入手是最好不过的了。

    给出n个数，怎样将它们从小到大排序？下面一口气讲三种常用的算法，它们是最简单的、最显然的、最容易想到的。选择排序(Selection Sort)是说，每次从数列中找出一个最小的数放到最前面来，再从剩下的n-1个数中选择一个最小的，不断做下去。插入排序(Insertion Sort)是，每次从数列中取一个还没有取出过的数，并按照大小关系插入到已经取出的数中使得已经取出的数仍然有序。冒泡排序(Bubble Sort)分为若干趟进行，每一趟排序从前往后比较每两个相邻的元素的大小（因此一趟排序要比较n-1对位置相邻的数）并在每次发现前面的那个数比紧接它后的数大时交换位置；进行足够多趟直到某一趟跑完后发现这一趟没有进行任何交换操作（最坏情况下要跑n-1趟，这种情况在最小的数位于给定数列的最后面时发生）。事实上，在第一趟冒泡结束后，最后面那个数肯定是最大的了，于是第二次只需要对前面n-1个数排序，这又将把这n-1个数中最小的数放到整个数列的倒数第二个位置。这样下去，冒泡排序第i趟结束后后面i个数都已经到位了，第i+1趟实际上只考虑前n-i个数（需要的比较次数比前面所说的n-1要小）。这相当于用数学归纳法证明了冒泡排序的正确性：实质与选择排序相同。上面的三个算法描述可能有点模糊了，没明白的话网上找资料，代码和动画演示遍地都是。

    这三种算法非常容易理解，因为我们生活当中经常在用。比如，班上的MM搞选美活动，有人叫我给所有MM排个名。我们通常会用选择排序，即先找出自己认为最漂亮的，然后找第二漂亮的，然后找第三漂亮的，不断找剩下的人中最满意的。打扑克牌时我们希望抓完牌后手上的牌是有序的，三个8挨在一起，后面紧接着两个9。这时，我们会使用插入排序，每次拿到一张牌后把它插入到手上的牌中适当的位置。什么时候我们会用冒泡排序呢？比如，体育课上从矮到高排队时，站队完毕后总会有人出来，比较挨着的两个人的身高，指挥到：你们俩调换一下，你们俩换一下。
    这是很有启发性的。这告诉我们，什么时候用什么排序最好。当人们渴望先知道排在前面的是谁时，我们用选择排序；当我们不断拿到新的数并想保持已有的数始终有序时，我们用插入排序；当给出的数列已经比较有序，只需要小幅度的调整一下时，我们用冒泡排序。

    我们来算一下最坏情况下三种算法各需要多少次比较和赋值操作。
    选择排序在第i次选择时赋值和比较都需要n-i次（在n-i+1个数中选一个出来作为当前最小值，其余n-i个数与当前最小值比较并不断更新当前最小值），然后需要一次赋值操作。总共需要n(n-1)/2次比较与n(n-1)/2+n次赋值。
    插入排序在第i次寻找插入位置时需要最多i-1次比较（从后往前找到第一个比待插入的数小的数，最坏情况发生在这个数是所有已经取出的数中最小的一个的时候），在已有数列中给新的数腾出位置需要i-1次赋值操作来实现，还需要两次赋值借助临时变量把新取出的数搬进搬出。也就是说，最坏情况下比较需要n(n-1)/2次，赋值需要n(n-1)/2+2n次。我这么写有点误导人，大家不要以为程序的实现用了两个数组哦，其实一个数组就够了，看看上面的演示就知道了。我只说算法，一般不写如何实现。学算法的都是强人，知道算法了都能写出一个漂亮的代码来。
    冒泡排序第i趟排序需要比较n-i次，n-1趟排序总共n(n-1)/2次。给出的序列逆序排列是最坏的情况，这时每一次比较都要进行交换操作。一次交换操作需要3次赋值实现，因此冒泡排序最坏情况下需要赋值3n(n-1)/2次。
    按照渐进复杂度理论，忽略所有的常数，三种排序的最坏情况下复杂度都是一样的：O(n^2)。但实际应用中三种排序的效率并不相同。实践证明（政治考试时每道大题都要用这四个字），插入排序是最快的（虽然最坏情况下与选择排序相当甚至更糟），因为每一次插入时寻找插入的位置多数情况只需要与已有数的一部分进行比较（你可能知道这还能二分）。你或许会说冒泡排序也可以在半路上完成，还没有跑到第n-1趟就已经有序。但冒泡排序的交换操作更费时，而插入排序中找到了插入的位置后移动操作只需要用赋值就能完成（你可能知道这还能用move）。本文后面将介绍的一种算法就利用插入排序的这些优势。

    我们证明了，三种排序方法在最坏情况下时间复杂度都是O(n^2)。但大家想过吗，这只是最坏情况下的。在很多时候，复杂度没有这么大，因为插入和冒泡在数列已经比较有序的情况下需要的操作远远低于n^2次（最好情况下甚至是线性的）。抛开选择排序不说（因为它的复杂度是“死”的，对于选择排序没有什么“好”的情况），我们下面探讨插入排序和冒泡排序在特定数据和平均情况下的复杂度。
    你会发现，如果把插入排序中的移动赋值操作看作是把当前取出的元素与前面取出的且比它大的数逐一交换，那插入排序和冒泡排序对数据的变动其实都是相邻元素的交换操作。下面我们说明，若只能对数列中相邻的数进行交换操作，如何计算使得n个数变得有序最少需要的交换次数。
    我们定义逆序对的概念。假设我们要把数列从小到大排序，一个逆序对是指的在原数列中，左边的某个数比右边的大。也就是说，如果找到了某个i和j使得i<j且Ai>Aj，我们就说我们找到了一个逆序对。比如说，数列3,1,4,2中有三个逆序对，而一个已经有序的数列逆序对个数为0。我们发现，交换两个相邻的数最多消除一个逆序对，且冒泡排序（或插入排序）中的一次交换恰好能消除一个逆序对。那么显然，原数列中有多少个逆序对冒泡排序（或插入排序）就需要多少次交换操作，这个操作次数不可能再少。
    若给出的n个数中有m个逆序对，插入排序的时间复杂度可以说是O(m+n)的，而冒泡排序不能这么说，因为冒泡排序有很多“无用”的比较（比较后没有交换），这些无用的比较超过了O(m+n)个。从这个意义上说，插入排序仍然更为优秀，因为冒泡排序的复杂度要受到它跑的趟数的制约。一个典型的例子是这样的数列：8, 2, 3, 4, 5, 6, 7, 1。在这样的输入数据下插入排序的优势非常明显，冒泡排序只能哭着喊上天不公。
    然而，我们并不想计算排序算法对于某个特定数据的效率。我们真正关心的是，对于所有可能出现的数据，算法的平均复杂度是多少。不用激动了，平均复杂度并不会低于平方。下面证明，两种算法的平均复杂度仍然是O(n^2)的。
    我们仅仅证明算法需要的交换次数平均为O(n^2)就足够了。前面已经说过，它们需要的交换次数与逆序对的个数相同。我们将证明，n个数的数列中逆序对个数平均O(n^2)个。
    计算的方法是十分巧妙的。如果把给出的数列反过来（从后往前倒过来写），你会发现原来的逆序对现在变成顺序的了，而原来所有的非逆序对现在都成逆序了。正反两个数列的逆序对个数加起来正好就是数列所有数对的个数，它等于n(n-1)/2。于是，平均每个数列有n(n-1)/4个逆序对。忽略常数，逆序对平均个数O(n^2)。
    上面的讨论启示我们，要想搞出一个复杂度低于平方级别的排序算法，我们需要想办法能把离得老远的两个数进行操作。

    人们想啊想啊想啊，怎么都想不出怎样才能搞出复杂度低于平方的算法。后来，英雄出现了，Donald Shell发明了一种新的算法，我们将证明它的复杂度最坏情况下也没有O(n^2) （似乎有人不喜欢研究正确性和复杂度的证明，我会用实例告诉大家，这些证明是非常有意思的）。他把这种算法叫做Shell增量排序算法（大家常说的希尔排序）。
    Shell排序算法依赖一种称之为“排序增量”的数列，不同的增量将导致不同的效率。假如我们对20个数进行排序，使用的增量为1,3,7。那么，我们首先对这20个数进行“7-排序”(7-sortedness)。所谓7-排序，就是按照位置除以7的余数分组进行排序。具体地说，我们将把在1、8、15三个位置上的数进行排序，将第2、9、16个数进行排序，依此类推。这样，对于任意一个数字k，单看A(k), A(k+7), A(k+14), ...这些数是有序的。7-排序后，我们接着又进行一趟3-排序（别忘了我们使用的排序增量为1,3,7）。最后进行1-排序（即普通的排序）后整个Shell算法完成。看看我们的例子：

  3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2  <-- 原数列
  3 3 2 0 5 1 5 7 4 4 0 6 1 6 8 7 9 9 8 2  <-- 7-排序后
  0 0 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9  <-- 3-排序后
  0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9  <-- 1-排序后（完成）

    在每一趟、每一组的排序中我们总是使用插入排序。仔细观察上面的例子你会发现是什么导致了Shell排序的高效。对，每一趟排序将使得数列部分有序，从而使得以后的插入排序很快找到插入位置。我们下面将紧紧围绕这一点来证明Shell排序算法的时间复杂度上界。
    只要排序增量的第一个数是1，Shell排序算法就是正确的。但是不同的增量将导致不同的时间复杂度。我们上面例子中的增量(1, 3, 7, 15, 31, ..., 2^k-1)是使用最广泛的增量序列之一，可以证明使用这个增量的时间复杂度为O(n√n)。这个证明很简单，大家可以参看一些其它的资料，我们今天不证明它。今天我们证明，使用增量1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2^p*3^q，时间复杂度为O(n*(log n)^2)。
    很显然，任何一个大于1的正整数都可以表示为2x+3y，其中x和y是非负整数。于是，如果一个数列已经是2-排序的且是3-排序的，那么对于此时数列中的每一个数A(i)，它的左边比它大的只有可能是A(i-1)。A2绝对不可能比A12大，因为10可以表示为两个2和两个3的和，则A2<A4<A6<A9<A12。那么，在这个增量中的1-排序时每个数找插入位置只需要比较一次。一共有n个数，所以1-排序是O(n)的。事实上，这个增量中的2-排序也是O(n)，因为在2-排序之前，这个数列已经是4-排序且6-排序过的，只看数列的奇数项或者偶数项（即单看每一组）的话就又成了刚才的样子。这个增量序列巧妙就巧妙在，如果我们要进行h-排序，那么它一定是2h-排序过且3h-排序过，于是处理每个数A(i)的插入时就只需要和A(i-h)进行比较。这个结论对于最开始几次（h值较大时）的h-排序同样成立，当2h、3h大于n时，按照定义，我们也可以认为数列是2h-排序和3h-排序的，这并不影响上述结论的正确性（你也可以认为h太大以致于排序时每一组里的数字不超过3个，属于常数级）。现在，这个增量中的每一趟排序都是O(n)的，我们只需要数一下一共跑了多少趟。也就是说，我们现在只需要知道小于n的数中有多少个数具有2^p*3^q的形式。要想2^p*3^q不超过n，p的取值最多O(log n)个，q的取值最多也是O(log n)个，两两组合的话共有O(logn*logn)种情况。于是，这样的增量排序需要跑O((log n)^2)趟，每一趟的复杂度O(n)，总的复杂度为O(n*(log n)^2)。早就说过了，证明时间复杂度其实很有意思。
    我们自然会想，有没有能使复杂度降到O(nlogn)甚至更低的增量序列。很遗憾，现在没有任何迹象表明存在O(nlogn)的增量排序。但事实上，很多时候Shell排序的实际效率超过了O(nlogn)的排序算法。

    后面我们将介绍三种O(nlogn)的排序算法和三种线性时间的排序算法。最后我们将以外部排序和排序网络结束这一章节。

    很多人问到我关于转贴的问题。我欢迎除商业目的外任何形式的转贴（论坛、Blog、Wiki、个人网站、PodCast，甚至做成ppt、pdf），但一定要注明出处，最好保留原始链接。我的网站需要点反向链接才能在网络中生存下去，大家也都可以关注并且推广这个Blog。我一直支持cc版权协议，因此发现了文章中的问题或者想要补充什么东西尽管提出来，好让更多的人学习到好东西。我昨天看Blog上原来写的一些东西，居然连着发现了几个错误式子和错别字，好奇大家居然没有提出来。发现了问题真的要告诉我，即使格式有点问题也要说一下，决不能让它那么错着。另外有什么建议或想法也请说一下，我希望听到不同的声音不同的见解，好让我决定这类文章以后的发展方向。

Matrix67原创
转贴请注明出处

    我的FireFox一直不能显示Google Analytics的Flash，网上也没有搜索到相关的内容。今天发誓要把这个问题解决了，初步断定是某个插件的问题。我开始把插件一个一个的关闭，后来发现是MediaWrap的问题。把MediaWrap选项中的“ShockwaveFlash格式”前面的勾去掉就可以了。当然，你也可以在需要用Google Analytics时单击状态栏上的图标暂时关闭它。
    希望与我有同样困扰的同志能看到这篇日志。

    今天下午一起床，我就带好我的iPod和PowerShot S60去看传说中的钉子户去了。激动得忘了石小路道路仍然堵塞，上了公车就后悔走石桥铺这条路了（不过我也找不到去杨家坪的其它路）。到了杨家坪下车后，往商业中心走几步你就能看到传说中的神迹了。

    和大多数人想象的不同，神迹所在的位置是非常热闹的城市繁华地带，这里车来车往，高楼耸立：

    杨家坪轻轨车站是最好的观察点。轻轨车站高于地面，这个扶梯通向车站外的天桥：

    车站外天桥上观望神迹的人群。

    我所在的地方，人们正在激烈地讨论。可以看到，从天桥上看去神迹没有那么壮观。要想在更高的地方观望，必须买张票上车站。

    轻轨车站门口。

    轻轨车站内的样子。

    豁出去了，买了车票到了更高的地方。

    到了上面后，神迹一下子就壮观了。舍不得花钱买车票的人得不到这么好的观望点。不知道会不会因为这样轻轨生意变得特别好。

    换一个角度。

    来一个广角的。

    车来了，我要上去了。今天就这样结束了我的膜拜之旅。

Matrix67原创
转贴请注明出处

Update: 现在已经不用PJBlog了，文章中的很多链接已经失效。需要什么帮助请直接联系我。

  
1. 去掉UBB斜体标签

    经常在Blog发布代码的同志会发现斜体标签[i]很恶心，一旦你代码里的某个数组遇上了循环变量，原本整齐的代码就会歪掉一大半。考虑到反正平时不太需要斜体，估计一定有人会像我一样想去掉这个UBB标签。
    去掉它要改两个地方。在common\ubbcode.asp中去掉下面这两行
re.Pattern="\[i\]([^\r]*?)\[\/i\]"
strContent=re.Replace(strContent,"<i>$1</i>")
    还有一个地方要修改，就是common\function.asp中的自动闭合UBB那一段。你需要去掉function closeUBB(strContent)函数中arrTags数组里的"i"。也就是说，找到
arrTags=array("code","quote","list","color","align","font","size","b","i","u","html")
    并替换成
arrTags=array("code","quote","list","color","align","font","size","b","u","html")
    如果不做这一个操作的话，你会发现有多余的[/i]出现。


2. Blog顶部调用Twitter最近三条信息

    最近Twitter确实是火了一把，估计有人需要下面这段代码。为了加快Blog载入速度（Twitter慢死了），我将把JavaScript放在footer中调用。
    添加一个模块并且设为内容栏置顶，代码如下（红色部分需要自己修改）：
<div style="PADDING-RIGHT: 4px; PADDING-LEFT: 4px; PADDING-BOTTOM: 4px; PADDING-TOP: 4px; TEXT-ALIGN: left; OVERFLOW:hidden; WHITE-SPACE:nowrap;" >
WHAT AM I DOING NOW by <a href="http://twitter.com/matrix67" target="_blank">twitter.com</a><br/>
<span id="stat0"></span>, <span id="stat0_time"></span> |
<span id="stat1"></span>, <span id="stat1_time"></span> |
<span id="stat2"></span>, <span id="stat2_time"></span>
</div>
    然后在footer.asp中添加如下代码：
<script type="text/javascript" src="http://www.twitter.com/t/status/user_timeline/1758881?count=3&named_obj"></script>
<script type="text/javascript"><!--
document.getElementById('stat0').innerHTML = Twitter.posts[0].text;
document.getElementById('stat0_time').innerHTML = Twitter.posts[0].relative_created_at;
document.getElementById('stat1').innerHTML = Twitter.posts[1].text;
document.getElementById('stat1_time').innerHTML = Twitter.posts[1].relative_created_at;
document.getElementById('stat2').innerHTML = Twitter.posts[2].text;
document.getElementById('stat2_time').innerHTML = Twitter.posts[2].relative_created_at;
--></script>
    这样的效果是两行文字，第二行不换行，让它超出边界不管（我觉得这样好看些）。Twitter太慢了，我玩了一天就不玩了，因此不给demo了，这里只贴个效果图：

3. PJBlog自带的一种悬停提示框特效

    header中有一段被注释掉了的js文件引用。把header.asp中的
<!--<script type="text/javascript" src="common/nicetitle.js"></script>-->
    改成
<script type="text/javascript" src="common/nicetitle.js"></script>
    然后你就能看到效果了。控制提示框样式的css在皮肤文件的typography.css中的div.nicetitle一段，你可以参考我所修改的样式（改为灰色背景）。
/*提示框CSS*/
   div.nicetitle {
    position: absolute;
    padding: 4px !important;
    padding: 6px 4px 4px 4px;
    top: 0;
    left: 0;
    font-family:Tahoma, Verdana;
    font-size: 12px;
    width: 15em;
    background: #CCCCCC;
    color: #222222;
    border: 1px solid #888888;
    text-align: left;
}


4. 把PJBlog的验证码改为算式验证码（两位加法）

    我研究这个研究了半天，把GetCode.asp改过去改过来调了半天终于搞出来了，效果见我的登陆界面matrix67.com/blog/login.asp。在分析BMP文件格式时头疼死了，后来才知道每一行输出像素必须是4的倍数（即使图象宽度不是4的倍数，不足的话要用0填空补足）。
    下载下面这个rar文件，解压缩后替换common\GetCode.asp文件。
点击下载此文件
    这样改后，图片宽度增加了，很多地方无法对齐，于是在common\function.asp中需要把
Function getcode()
    getcode= "<img src=""common/getcode.asp"" alt="""" style=""margin-right:40px;""/>"        
End Function
    改为
Function getcode()
    getcode= "<img src=""common/getcode.asp"" alt="""" style=""margin-right:8px;""/>"    
End Function
    这样才能和用户名、密码的输入框对齐。

    你可能还需要在文件内容中搜索所有出现过的“验证码：”并改为“算一算：”。
    昨天发现改了验证码后居然还有垃圾留言，没想通是为什么。



5. 让你的PJBlog支持语法高亮

    不同于网上流行的那个JS，我使用的是这个JS，它要简单一些（只有一个JS文件），而且使用也非常简单（自动查找HTML的<code>标签）。它仅仅是对语法进行高亮，并没有显示行号和折叠等功能。但同时它只对代码颜色进行修改，更加整洁，兼容PJBlog本身的代码显示效果。这里是我的一个效果演示（Pascal代码高亮）。
    你可以在这里下载这个JS脚本的最新版本。这个文件里还带有一份该脚本详细的使用说明。它可以支持的语言我列在了下面，脚本文件总共37KB，因此你可能需要从中删除一些语言支持。至于怎么删除部分语言，你看了那个JS源码后就知道了。

• Python
  
• Ruby
  
• Perl
  
• PHP
  
• HTML
  
• CSS
  
• Javascript
  
• VBScript
  
• Delphi
  
• Java
  
• C++

    这个JS存在一个问题，它的某个定义与PJBlog重复了，前者的comment类是指的注释，而后者的comment是指的评论。你需要把JS文件中所有的'comment'替换为'comments'避免冲突（替换操作时要包括引号，因为我们只替换各个字符串定义）。
    我另外写了一个Pascal的关键字列表，比Delphi的关键字多一些，更适合Pascal语言。你可以把它加在JS文件里，需要的同学可以参考一下（顺便展示JS代码的高亮效果）：
var PASCAL_KEYWORDS = {'abs': 1,'addr': 1,'and': 1,'ansichar': 1,'ansistring': 1,'array': 1,'as': 1,'asm': 1,'begin': 1,'boolean': 1,'byte': 1,'cardinal': 1,'case': 1,'char': 1,'class': 1,'comp': 1,'const': 1,'constructor': 1,'currency': 1,'destructor': 1,'div': 1,'do': 1,'double': 1,'downto': 1,'else': 1,'end': 1,'except': 1,'exports': 1,'extended': 1,'false': 1,'file': 1,'finalization': 1,'finally': 1,'for': 1,'function': 1,'goto': 1,'if': 1,'implementation': 1,'in': 1,'inherited': 1,'int64': 1,'initialization': 1,'integer': 1,'interface': 1,'is': 1,'label': 1,'library': 1,'longint': 1,'longword': 1,'mod': 1,'nil': 1,'not': 1,'object': 1,'of': 1,'on': 1,'or': 1,'packed': 1,'pansichar': 1,'pansistring': 1,'pchar': 1,'pcurrency': 1,'pdatetime': 1,'pextended': 1,'pint64': 1,'pointer': 1,'private': 1,'procedure': 1,'program': 1,'property': 1,'pshortstring': 1,'pstring': 1,'pvariant': 1,'pwidechar': 1,'pwidestring': 1,'protected': 1,'public': 1,'published': 1,'raise': 1,'real': 1,'real48': 1,'record': 1,'repeat': 1,'set': 1,'shl': 1,'shortint': 1,'shortstring': 1,'shr': 1,'single': 1,'smallint': 1,'string': 1,'then': 1,'threadvar': 1,'to': 1,'true': 1,'type': 1,'unit': 1,'until': 1,'uses': 1,'val': 1,'var': 1,'varirnt': 1,'while': 1,'widechar': 1,'widestring': 1,'with': 1,'word': 1,'write': 1,'writeln': 1,'xor': 1,'assign': 1,'reset': 1,'rewrite': 1,'exit': 1,'halt': 1,'break': 1,'read': 1,'readln': 1,'new': 1,'length': 1,'append': 1,'close': 1};

LANGUAGES.pascal = {
  defaultMode: {
    lexems: [IDENT_RE],
    illegal: '("|\\$[G-Zg-z]|\\/\\*|</)',
    contains: ['comments', 'string', 'number', 'function', 'class'],
    keywords: PASCAL_KEYWORDS
  },
  case_insensitive: true,
  modes: [
    {
      className: 'comments',
      begin: '{', end: '}'
    },
    {
      className: 'comments',
      begin: '\\(\\*', end: '\\*\\)',
      relevance: 10
    },
    C_LINE_COMMENT_MODE,
    {
      className: 'number',
      begin: NUMBER_RE, end: '^',
      relevance: 0
    },
    {
      className: 'string',
      begin: '\'', end: '\'',
      contains: ['quote'],
      relevance: 0
    },
    {
      className: 'quote',
      begin: '\'\'', end: '^'
    },
    {
      className: 'function',
      begin: 'function', end: '[:;]',
      lexems: [IDENT_RE],
      keywords: {'function': 1},
      contains: ['title', 'params', 'comments'],
      relevance: 0
    },
    {
      className: 'function',
      begin: '(procedure|constructor|destructor)', end: ';',
      lexems: [IDENT_RE],
      keywords: {'constructor': 1, 'destructor': 1, 'procedure': 1},
      contains: ['title', 'params', 'comments'],
      relevance: 10
    },
    {
      className: 'title',
      begin: IDENT_RE, end: '^'
    },
    {
      className: 'params',
      begin: '\\(', end: '\\)',
      lexems: [IDENT_RE],
      keywords: PASCAL_KEYWORDS,
      contains: ['string']
    }
  ]
};//pascal, written by matrix67.com

    下面这个压缩包里的css文件定义了各种类型的高亮颜色。各种颜色具体的值是我自己定的，你不喜欢可以修改一下以符合你的界面风格。
点击下载此文件

    现在你需要把这个highlight.css文件连同前面的highlight.js文件保存在common目录下。然后在common\ubbcode.asp中找到
re.Pattern="\[quote\](.*?)\[\/quote\]"
    在它上面加入以下代码：
re.Pattern="\[code=(.[^\]]*)\](.*?)\[\/code\]"
strContent= re.Replace(strContent,"<div class=""UBBPanel""><div class=""UBBTitle""><img src=""images/quote.gif"" style=""margin:0px 2px -3px 0px"" alt=""程序代码""/> 程序代码</div><div class=""UBBContent""><pre><code class=""$1"">$2</code></pre></div></div>")
    然后在header.asp中找到
<link rel="stylesheet" rev="stylesheet" href="skins/<%=Skins%>/UBB/editor.css" type="text/css" media="all" /><!--UBB编辑器代码-->
    在其下面加入这一行代码：
<link rel="stylesheet" rev="stylesheet" href="common/highlight.css" type="text/css" media="all" />
    最后在footer.asp中加入以下代码：
<script type="text/javascript" src="common/highlight.js"></script>
<script type="text/javascript">
   initHighlightingOnLoad();
</script>

    以后你就可以通过使用形如[ code=delphi] TheOneILove:=SexyMM [ /code]的UBB标签来高亮各种语言的代码。
    目前已知的问题：由于这个脚本需要用<pre>，而用了<pre>后将导致无法换行，因此你可能会想为这个UBB框单独设一个css强制换行。我最讨厌换行的问题了，IE和FireFox总是不能兼顾，后来干脆把overflow设成hidden，两边看上去都顺眼，超了右边界的就让它去吧。


6. 让你的TagsCloud看起来更明显，更大

    看看我的标签云，你会发现虽然每个标签的文章也不多，但大小同样很明显。更改tag.asp可以让你的Tags在日志数不多的情况下大小对比同样强烈。
    在tag.asp中找到
<%
  function getTagSize(c)
   dim i
   for i=1 to 10
    if int(c)<i*2.5 then
        getTagSize=12+i
        exit function
    end if
   next
   getTagSize=22
  end function
%>
    改成
<%
  function getTagSize(c)
   dim i
   for i=1 to 20
    if int(c)<i*1.5 then
        getTagSize=12+i
        exit function
    end if
   next
   getTagSize=34
  end function
%>
    说明一下，改了之后的意思为，标签大小共有20个等级，从12px起，每多1.5篇文章字体就大一号，有1.5 x 20=30篇文章时字号达到12+20=32，如果文章数超过30了标签字体大小都是34px。你可以自己改这几个数字直到满意位置。
    字体变大后会引起一个问题：标签过于挤了一些，行与行之间的空隙窄得难以忍受。你可能会想为标签云单独设一个css。还是tag.asp文件，你需要把
<div class="Content-body">
    改成
<div class="Content-tagscloud">
    并把你的皮肤文件夹内layout.css文件中对Content-body的定义复制一份，修改line-height属性并重命名为Content-tagscloud。参考我的改法（不同的皮肤具体的内容不同）。

    我所用的皮肤中相关的定义如下：
  /*---日志内容框--*/
  .Content-body{margin:8px 2px 2px 8px;overflow:hidden;text-align:left;width:98%;line-height: 160%;background-image: url();background-repeat: repeat-y;background-position: right;color: #292929;}
    在它下面添加一段代码，整个内容变成这样：
  /*---日志内容框--*/
  .Content-body{margin:8px 2px 2px 8px;overflow:hidden;text-align:left;width:98%;line-height: 160%; background-image: url();background-repeat: repeat-y;background-position: right;color: #292929;}
  .Content-tagscloud{margin:8px 2px 2px 8px;overflow:hidden; text-align:left;width:98%; line-height: 35px;background-image: url();background-repeat: repeat-y; background-position: right;color: #292929;}
    这样，标签云的行距就拉开了。


发现Bug或者有任何问题请在下面报告一下。

Matrix67原创
转贴请注明出处。

下列20个单选题，每题5分，满分100分。
题目纯属无聊，仅供娱乐；请不要过于认真，不知道答案也别来问我。
Matrix67.com原创，转贴请注明出处。

1. 与32、95、XP属于同一类事物的是：
   A. 61             B. SEX
   C. 我             D. Love is Everything

2. 如果48=0，那么84等于什么？
   A. :)             B. T
   C. 000            D. 12:56

3. 下面这些选项中哪一项是一种计算机高级语言？
   A.                B.
   C.                D.

4. 下面这些算式中哪一个算出来很可能是负数？
   A. 1111+1111      B. 2222+2222
   C. 11111+11111    D. 22222+22222

5. (10000000000)2
   A. (1024)1        B. (1024)10
   C. (1024)100      D. (1024)1000

6. 请选择下列描述中错误的一项：
   A. 270400是一个完全平方数
   B. 500500是一个三角形数
   C. 33550336是一个完全数
   D. 以上三项全错

7. 这道题的题目是什么？
   A. 关于递归运算的题目
   B. 关于线性规划的题目
   C. 关于汇编语言的题目
   D. 关于周莉莉的一切

8. 1099511627776B
   A. tumor          B. tuberculosis
   C. aeroacrophobia D. pneumonoultramicroscopicsilicovolcanoconiosis

9. 下面四个选项中有几个是错误的？
   A. 1个            B. 2个
   C. 3个            D. 4个

10. 以下哪个命令可以列出当前目录下的文件？
   A. 楼主           B. 楼上
   C. 火星           D. 沙发

11. 请选出下面四个选项中与众不同的一项：
   A. 1              B. 2　　　　　　　
   C. 3              D. 4              

12. 你认为OIer最喜欢下列哪个选项？
   A. C              B. C
   C. C              D. C

13. 恐怖份子与战斗机
   A. √             B. ×
   C. ∴             D. ∵

14. 27乘以6.5等于多少？
   A. 92.755         B. 175.6
   C. 23.1516        D. -7632.33

15.

16. We use Θ if O( f(n) )=__( f(n) )
   A. 劳力士         B. 欧米茄
   C. 天梭           D. 斯沃琪

17. 以下哪个选项在英文中出现频率最高？
   A. 麦当劳         B. 氧
   C. 2.718          D. 函数

18. 打网游为什么经常死机？
   A. 经常出现各种人物
   B. 经常出现各种宠物
   C. 经常出现各种怪物
   D. 经常出现各种NPC

19.
   A. 123456         B. 234567
   C. 345678         D. 456789

20 以下哪个选项正是本题所缺少的？
   A. ,              B. .
   C. ?              D. !

    寒假时没事写了这几个代码，算是我几个月后重操键盘了。这是几道经典题目，可能有人需要，再加上昨天搞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
   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的这个帖子里找到了这个好东西，它可以帮助OIer将大规模的图论题数据转化为图便于观察。今天我又用到了几次，突然想到把它介绍在我的Blog上。
    graphviz的主页设在http://www.graphviz.org，你可以在这里下载到最新的Windows版本，目前最新版本的安装程序为graphviz-2.12.exe。安装后你可以在dos下（任何目录中）调用它的命令行模式。
    这里，我们使用dot语言。官方网站上有关于dot语言的详细的用户手册，这里我只把常用的一些功能做一下演示。你可以在这篇日志的三个截图中掌握足够的知识来应用graphviz。
    先说明一下最顶上的Hello World程序。dot是程序名，参数-Tgif表示以gif格式输出，参数-O表示输出文件的方式设为默认（在当前目录下输出名为noname的文件，其后缀名与参数-T???所设定的类型相同）。下面一行输入的是graphviz所用的dot语言，digraph G表示有向图，花括号里描述图的内容。这样就生成了一个最简单的图。

    下面一个例子说明了如何输出一个边上有权值的无向图。这是OIer经常要用的东西。size=4,4指定了图的大小，单位为英寸。如果没有这一句的话，默认的图要大得多。你可以另外写一个程序把你的数据按图中的格式转化为dot代码。虽然graphviz可以从外部文件中读入这段代码，但我觉得粘贴进dos窗口更方便一些。

        

    下面这个例子包含更多的参数，展示了graphviz更多的功能。输出为ps文件更好看一些，因为输出ps文件可以反锯齿（应该是矢量的）。

    和Xbox上的Geometry Wars几乎一样，是一个类似于Crimson Land的Survival类射击游戏。难以想象仅仅是一些简单的线条和几何形状可以搞出这么绚丽震撼的游戏画面。
    文件大小2.6M，下载地址：http://gridwars.marune.de