最近发生的有争议的事情太多了，几乎每一天网友们都在争论什么天大的事情。抛开其它的话题不说，电脑里能多一种字体并不是坏事。今天终于找到了传说中的静蕾字体，贴几张图供大家参考。

中文效果：

英文和数字效果：

符号效果：

    个人认为，这个虽然奇丑无比（我写的字肯定漂亮得多），但是一些别的字库里找不到的手写体特性是可以接受的（比如“是”字）。人家静蕾又没惹到你，没事骂人家干什么？网上没事找事跟着起哄唯恐天下不乱的人真多，还是我们以学术研究为主的OIer最朴实，最善良。

    Drive的命运很惨，先是被拆成了两季，然后又被砍。我所追的唯一一部春季新剧就这样结束了。整个剧集只播放了四集（准确地说是三集）就被撤下来了，官方宣布第一季最后两集可能在今年夏季播出，第二季播出基本上是不可能了。撤下来的周一8点档将由House的重播来填补。

    前几天我随便发了一篇关于Drive的日志，当时预言Drive随时会被砍。只是我没想到事情会发生得这么快。
    今天起来看到官方论坛上全是Drive Fans的抱怨说Drive被取消了。算下来，从首播到被砍总共不到10天。FOX的剪刀手果然名不虚传，Nathan Fillion的经典Firefly就曾经死在FOX下，这次仍然是他主演的Drive再一次遭到不测。就我个人来看，这部剧还是有希望成为经典的，收视率低的原因很可能仅仅是受到枪杀事件的影响。这样一部剧集需要剧情的发展，FOX应该再给它一点时间。
    还有，我曾经在想，为什么不交换一下星期一24和Drive的位置，把24的时间调整到前面来做Drive的lead-in？

    本来以为今天周末了又会来很多人在这里留言，结果……混得忘了日期了，居然都快五一了。

What is it?
    最近大家喜欢在留言板发一些与本站无关的话题并互相引用回复，这说明一个论坛模块是有必要的，于是想到了开发讨论区模块。
    这个单版面讨论区用于访问本站的网友进行讨论和聊天。它和留言板的功能有很大的区别。比如，下面8条消息中，前4条应该发到留言板，后4条应该发到讨论区。
    1. 这个Blog太他妈的牛了
    2. 为什么我要用代理才能上你的网？
    3. 建议把验证码换成3位乘法并加入平方和阶乘运算
    4. 申请友链www.8rong8chi.com，logo可以在www.3gedaibiao.com里找到
    5. 问一下Matrix67的情书那道题
    6. 记者MM的PP到手，请登陆www.colorwolf.com查看。
    7. 跪求Sky Angel Vol.39 - Vol.41和Tokyo Hot n0204
    8. matrix哥哥你好，我是一个可爱的初三MM，我好想跟你聊天啊，+我QQ:xxxxxxxx

    另外，针对某篇日志的留言直接在日志下面写评论就可以了。

History:
    23号的日志里我曾经说过我要写一个PJBlog的单版面论坛模块。实际的工作是从昨天开始的。
    昨天一起床我就开始研究PJBlog的数据库和函数，经过两天两夜的奋战终于写出了一个大致成形的程序。目前这个模块属于VERY Beta版，只用了两个asp文件，里面有很多问题。数据库结构的合理性有待观察，因此数据有可能会重建从而导致数据丢失。目前论坛界面非常简陋，你进去看了别被吓到就是了。任何一个牛人也有菜的时候，如果以后我开发了什么大型web 2.0，我不会忘记今天我写的这个终极菜鸟程序。

Features:
    这个单版面论坛的程序特点就是没有任何特点，除了发帖回贴外这个论坛程序目前不支持任何其它的操作（如头像、签名、高亮、置顶、PM、积分、附件、交易等），并且以后也不打算支持。毕竟这是一个个人Blog的模块而已。
    这个单版面论坛的管理方式就是不进行任何管理。不删除任何帖子，不分版限制话题，用户无需注册即可发言。仅仅是一个大家随意交流的地方。各位在其它论坛发的水贴老被删的话可以到这里来（想不通OIBH为什么不开水区）。请大家自觉远离色情，远离政治。

TODO List:
    加入分页功能
    加入管理员的管理功能
    加入自动清除陈贴的功能
    将浏览方式改为纯Ajax
    一些简单的界面美化
    修复大家提出的Bug
    可能加入其它一些大家提出的有创意的构想

有Bug请报告一下。

注：这篇日志是4月份写的，“下个月”指的07年5月

    下个月的16号就是本菜鸟的生日了，为了庆祝一下自己19岁生日，我计划在5月12日（星期六）晚举办一次生日邀请赛，请各位OIer赏脸。题目差不多想好了，先在这里发布一下消息。4道题3个半小时，到时候题目就在这里发布（OIBH上也会发布一份），仍然采用电子邮件提交，邮箱还是那两个：gs.matrix67@gmail.com，和matrix67@tom.com。
    本次邀请赛的难度比NOIp高一些，对于今年要参加NOIp的同学们来说是一次提高自己的机会；对于即将奔赴福州的各位巨牛来说……就当一次积人品增信心的弱智模拟赛吧。

    我们之前所有的排序算法都是给定了数据再进行排序，排序的效率很大程度上取决于数据的好坏。我们今天所介绍的是一个完全不同的排序方法，它可以在“暗箱”里对数据进行排序（即你不必知道实际数据是什么），换句话说这种排序方法不依赖于数据(Data-Independent)，所有比较操作都与数据无关。你甚至可以立即忘掉前面的比较结果，因为对于所有可能的数据这类排序算法都能得到正确答案并且排序步骤完全相同。本文结束后再回过头来看这段话你将有更深的认识。
  
    我们设置一个暗箱，暗箱左边有n个输入口，暗箱右边有n个输出口。我们需要设计一个暗箱使得，任意n个数从左边输进去，右边出来的都是有序的。图1显示了有4个输入的暗箱。
  
    暗箱里唯一允许的元件叫做“比较器”(Comparator)，每个比较器连接两个元素，当上面那个比下面那个大时它将交换两个元素的位置。也就是说，每经过一个比较器后，它的两端中较小的一个总是从上面出来，较大的总是到了下面。图2显示了一种包含4个比较器的暗箱系统。当输入数据3,1,4,2通过这个系统时，输出为1,3,2,4，如图3所示。这种暗箱结构叫做比较网络(Comparator Network)。如果对于任意一个输入数据，比较网络的输出都是有序的，那么这个比较网络就叫做排序网络(Sorting Network)。显然，我们例子中的比较网络不是一个排序网络，因为它不能通过3,1,4,2的检验。

    现在，我们的第一个问题是，是否存在比较网络。就是说，有没有可能使得任意数据通过同一组比较器都能输出有序的结果。我们最初的想法当然是，把我们已知的什么排序算法改成这种形式。把原来那十种排序又翻出来看一遍，找一找哪些排序的比较操作是无条件的。运气不错，我们所学的第一个算法——冒泡排序，它的比较就是无条件的，不管数据怎样冒泡排序都是不断比较相邻元素并把较小的放到前面。冒泡排序是一个彻头彻尾的排序网络模型，我们可以立即画出冒泡排序所对应的排序网络（图4）。这是我们得到的第一个排序网络。我们通常不认为插入排序是排序网络，因为插入排序的比较次数取决于数据的有序程度。
  
    传统的计算机一次只能处理一个比较。排序网络真正的研究价值在于，假如有机器可以同时处理多个比较器，排序的速度将大幅度提高。我们把比较器的位置稍微移动一下，把那些互不冲突（处理的元素不同）的比较器压缩到一层(Stage)（图5），这样整个排序过程压缩为了2n-3层。实现排序网络的机器可以在单位时间里并行处理同一层中所有的比较。此时，比较次数的多少对排序效率不起决定作用了，即使比较次数多一些但是排序网络的层次更少，效率也会更高一些。我们自然又想，排序网络需要的层数能否少于2n-3。我们想到，图5的左下角和右下角似乎有些空，我们期望能在这些位置加一些比较从而减少层数。图6给出了一个只有n层的排序网络，这叫做奇偶移项排序(Odd-even Transposition Sort)。我们下文将证明它确实是一个排序网络。这次的图很多，排版也很困难，累死我了。我把下面的图7也放到这里来了，不然到处都是图很难看。
  

    给出一个比较网络，怎样判断它是不是一个排序网络？很遗憾，现在还没有找到一种好的算法。事实上，这个问题是一个NPC问题。注：这种说法是不准确的，因为目前还没有迹象表明这个问题是NP问题。准确的说法应该是，“判断某比较网络为排序网络”是Co-NP Complete，而“判断某比较网络不是排序网络”（即找到一个反例）才是NP Complete。
    传统的做法是枚举所有n的排列来验证，一共要考虑n!种情况。下面我们介绍排序网络理论里最重要的结论：0-1原理(0-1 Principle)。使用这个原理来验证排序网络只需要考虑2^n种情况。0-1原理告诉我们，如果所有的01序列能够通过比较网络排出顺序，那么这足以说明该网络为排序网络。证明过程很简单。为了证明这个结论，我们证明它的逆否命题（逆否命题与原命题同真假）：如果一个比较网络不是排序网络，那么至少存在一个01序列不能被排序。我们给出一种算法，这个算法可以把任何一个不能被排序的输入数据转化为一个不能被排序的01序列。
    在最初的例子（图3）中，输入数据3,1,4,2的输出为1,3,2,4，没有成功地排出顺序，从而判断出该网络不是排序网络。这说明，输出结果中存在逆序对（左边某个数大于右边的某个数）。我们从输出结果中找出一个逆序对来。例子中，(3,2)就是我们要找的数。现在，我们把输入中所有小于数字3（左边那个数）的数都变成0，把所有大于等于3的数都变成1。这样，3,1,4,2就变成了1,0,1,0。显然，把得到的这个01序列输入进去，原来曾经发生过交换的地方现在仍然会交换，原来不曾交换的地方现在也同样不会发生交换（当两个0或两个1进行比较时，我们既可以认为它们不交换，也可以看成它们要互相交换，反正都一样）。最后，该01序列输出的结果中，本来3的位置现在还是1，原来2的位置现在仍然是0，逆序对仍然存在。因此，只要一个比较网络不是排序网络，那么总可以找到一个01序列不能被排序。等价地，如果所有的01序列都能被排序了，这个比较网络也就是排序网络了。

    我们用0-1原理来证明奇偶移项排序的正确性。我们对n进行数学归纳证明。n=2时（一个“工”字）显然是排序网络。
    图中是n=8的情况。我们假设对于所有n<=7，奇偶移项排序网络都是正确的。我们同时假定所有输入数字非0即1，下面我们说明n=8时所有的01序列都能被正确排序。
    假设最后一个数是1（图7，在前面的），那么这个1将始终排在最后不参与任何交换操作，对前面7个数没有任何影响。除去无用的灰色部分，剩下的就是n=7这一规模较小的子排序网络，由归纳假设则n=8也是排序网络；
  
    假设最后一个数是0（图8），那么在每一次比较中这个0都会被提到前面去（前面说过，两个0之间交不交换是一回事）。蓝色的箭头表示每个数跑到了什么位置。你会发现除最后一个数以外前7个数之间的比较器又构成了n=7的情况。

    接下来，我们提出一些比较器个数为O(n*logn*logn)的排序网络。其中一种就是之前提到过的2^p*3^q增量Shell排序。这种增量排序的特点是每一趟排序中的每个数只与前面的数比较一次，因此它可以非常方便地转化为排序网络。图9就是一个n=8的Shell排序网络。Bitonic排序也可以做到O(n*logn*logn)的比较器个数，今天不介绍它。下面详细介绍奇偶归并排序网络。
  
    奇偶归并排序网络也是一种比较器个数为O(n*logn*logn)的排序网络。它和归并排序几乎相同，不同的只是合并的过程。普通归并排序的O(n)合并过程显然是依赖于数据的，奇偶归并排序可以把这个合并过程改成非数据依赖型，但复杂度将变高。这个合并过程本身也是递归的。我们假设n是2的幂（不是的话可以在前面添0补足，这对复杂度的计算没有影响），算法首先把n个数中所有的奇数项和偶数项分别递归地合并，然后在排序后的第i个偶数项和第i+1个奇数项之间设立比较器。
    假如1,4,6,8和2,3,7,9是两段已经有序的子序列，合并过程首先递归地合并1,6,2,7和4,8,3,9，这样原数列就变成了1,3,2,4,6,8,7,9。然后分别把(3,2),(4,6),(8,7)三对相邻元素中各自较小的那个交换到前面，完成合并操作。使用0-1原理证明这个结论出乎意料的简单：图10显示了n=16的情况，白色的方格代表一个0，灰色方格代表1。奇偶项分别排序后，偶数项1的个数最多比奇数项多出2个，我们设立的比较器可以考虑到所有的情况，不管什么情况都能让它最终变得有序。
  
    由前面说过的结论，合并过程总共需要比较O(nlogn)次。归并排序递归一共有O(logn)层，每一层总的比较器个数不超过O(nlogn)，因此总共O(n*logn*logn)。一个n=8的完整的奇偶归并排序网络如图11所示。

    菜鸟献丑，漏洞百出。如果我有什么错误，各位大牛请指正。
    Matrix67原创，转载请注明出处。

  外部排序(External Sort)已经在这里提到过，不再说了。
  所有排序的知识到这里说完了，下次再发布的就是数论相关内容了。数论部分将从进位制开始谈起。
  我会一直写下去，本人活到什么时候写到什么时候写完为止。不过，这几天缓一下，我计划做一个PJBlog的单版面论坛模块。

I Can Count to at Least Two.
http://www.youdontknowjack.com/node/63

Madam, I'm Adam.
http://www.youdontknowjack.com/node/93

That's So, Like, Last Chinese New Year.
http://www.youdontknowjack.com/node/114  (Have you ever seen "LOST"?)

Am I the Only One at Work Today?
http://www.youdontknowjack.com/node/115

I'm Not Dead Yet! Oh, Yep, I Am.
http://www.youdontknowjack.com/node/123

做人要厚道
……………………

很早就跟别人说我想搞Ajax，今天终于修成正果，实现了首页asp程序Ajax化。Ajax太他妈的牛了。
目前在我这里运行良好，有Bug的话报告一下。
目前已知问题：不支持Opera。目前还不知道是为什么，期待哪位高人给本菜鸟指点一下。现在Opera也可以了，原因出在cache上。

    常去mimima(已封，因此该asp程序不支持), 2kdown, pidown等种子host网站的同志都知道，这类站点有一个非常麻烦的地方就是不支持FireFox，点击Download后不能下载，而是出现一整页的乱码。上这种站点又怕有毒，开IE Tab开得胆战心惊的。今天搞烦了，决定把这个问题解决了。初步认为，错误原因应该是那边的php返回的Content-Type不对。然后，网上搜索半天解决方案都没有，于是想到自己写一个GreaseMonkey脚本，后来写来写去发现怎么也不行，又想搞FireFox扩展。最后突然想到办法，为什么不用asp把那边的数据用XMLhttp偷过来并转化成正确的Content-Type？于是，我的又一个asp小程序诞生了。
    这是一个测试版，可能有很多Bug，大家可以帮忙报告一下。这个asp程序在我这里还没出问题，至少上面提到的两个网站是完全可以的，我今天已经用了好几次了。注意，有一些其它的BT种子上传站点，虽然界面非常相似，但代码不一样（比如onlyff.com），它们是支持FireFox的，同时因为Post方式不一样，该asp程序不支持。

点击这里进入

需要测试一下么？你可以把下面的地址复制到输入框里然后点击Download。
http://www.pidown.com/link.php?ref=M70vw7SS8o
严重NSFW，别因为好奇真下了点开来看。我？我是满了18岁的了，下个月就19了。

    回过来想一下，JavaScript也可以XMLhttp，但是我不知道怎样用JS生成一个二进制文件。我想至少出于安全方面的考虑，这是不大可能的。

2007.04.22  pidown和2kdown也被封了，本asp程序彻底作废，关了。