不知大家有过硬盘坏道没，反正有一次我是遇上了，珍贵的collection顷刻间化为乌有。信息时代，每个人都面临着一个新的问题：如何储存你的重要文件最为安全？大多数人会选择多弄它几个备份，虽然这种办法的效率和“性价比”都不高。有没有什么高效而又节省空间的办法来保证数据安全呢？最近，ttsiod写了一篇关于Linux小软件Rsbep的文章，里面提到的算法可以保证大段数据丢失以后仍然能复原原来的数据。算法基于一种叫做Reed-Solomon的编码方式。

    Reed-Solomon编码的核心思想非常有趣：任意k个点都惟一地确定了一个最高次数为k-1次的多项式，如果我们把要传送的信息用一个多项式函数上的点来表示，那么我们可以用更多的点来描述这一信息，这样即使某些点的位置在传输过程中发生了错误，接收者也能根据其它的点来复原全部信息。考虑一个大小为n的有限域（由于一个字节有2^8=256种可能的值，n通常取256），其元素分别为x_0, x_1, x_2, ..., x_n；而我们要传输的数据长度为k。首先我们把这k个字节的数据当作有限域的前k个非0元素所对应的函数值，确定出它们所对应的k-1次多项式函数f；然后计算出n-1个非0元素的函数值f(x_1), f(x_2), ..., f(x_n)，作为最终的编码发送出去。注意我们的元素是一个有限域，因此多项式的值仍然在这个域里面（范围仍然是0到255）。在实际应用中，我们通常取k=223，这样的话223个字节的数据将加强为一段255字节长的数据，其中有32个字节是附加的信息。这种编码的纠错能力很强，即使有16个字节在传输中发生错误，我们也能通过剩余的信息复原出原始数据。

查看更多 »

    我在学校时，时不时会有人闯进宿舍，给宿舍里的每个人发一张调查表邀请大家填写。如果我不是很忙的话，通常还是很乐意填写的。不过，有时我很悲哀的发现，很多调查表的设计都很缺乏科学性。设计一张合理的调查表并不是一件容易的事情，你需要综合考虑各方面的因素。例如，假如你需要在调查表中问一个极度隐私的问题，尽管你在调查表上再三强调你们的保密措施，但你真的指望所有人都能够如实地回答吗？你真的指望会有人在“我不是处男/处女”或“我有同性恋倾向”前面打一个勾然后把表递到问卷回收人的手中吗？
    让我们考虑这样一个问题：你希望在调查表上问一个隐私问题。为了方便起见，假设这个问题只有“是”和“否”两个选项。有什么方案能够绝对地保证个人隐私完全不可能被泄露，让每个人都能够放心地填写，并且问卷回收之后能够得到一个准确的统计结果？
查看更多 »

    下面给出一种算法，该算法只需要使用加法运算和比较运算就可以求出n个数的最小公倍数：每一次操作都把当前最小的那个数加上它的初始值，直到所有数都相等为止。下面这个列表显示了用这个算法寻找30, 12, 18三个数的最小公倍数的全过程。初始时12是三个数中的最小数，于是该数加上12；接下来18成了最小的数，于是该数加上18变成了36；此时第二个数24又变成了最小数，于是再加上其对应的初始值12；以此类推直到三个数都变成相同的数180为止，这个180就是30, 12, 18的最小公倍数。

30 12 18
30 24 18
30 24 36
30 36 36
60 36 36
60 48 36
60 48 54
60 60 54
60 60 72
90 60 72
90 72 72
90 84 72
90 84 90
90 96 90
120 96 90
120 96 108
120 108 108
120 120 108
120 120 126
150 120 126
150 132 126
150 132 144
150 144 144
150 156 144
150 156 162
180 156 162
180 168 162
180 168 180
180 180 180

    这个算法为什么是正确的呢？它有什么实际用途呢？

查看更多 »

    曾经看到过自动扫雷软件，当时我就在想，扫雷游戏是否有什么牛B的多项式算法。最近才看到，扫雷问题居然是一个NP完全问题，并且这个定理有一个简单、直观而又神奇的证明。在这里和大家分享一下整个证明过程。
    首先，扫雷一定是NP问题，它显然可以在多项式的时间里验证一个解。接下来，我们需要把一个已知的NP完全问题归约到扫雷问题上去。我们将给出一种把逻辑电路问题归约到扫雷问题的方法，这样的话我们就可以利用扫雷问题解决逻辑电路问题，从而说明逻辑电路问题不比扫雷难。我们将把逻辑电路问题转换成一种对应的扫雷布局，就像画画一样把逻辑电路画在扫雷的棋盘上。如果你还不知道什么叫NP完全问题，什么叫逻辑电路问题，你可以看一看我的这篇文章。

   
    上图就是一条带有Boolean值的线路。注意到x和x'中有且仅有一个有雷。如果（沿线路方向）前一个格子有雷，我们就说这条线路状态为True；反之如果后一个格子有雷，那么这条线路所传递的Boolean值就是False。每条线路的起始端都如下图左所示，其中符号*表示该格里必然有雷，x和x'中同样是有且仅有一个有雷，但到底是哪一个里面有雷谁也说不清楚。线路是可以拐弯的，如下图右所示，这可以保证转角后Boolean值相同。
   

查看更多 »

昨天的，一题滑动窗口，二题O(n^3)的DP。三题是二维线段树？ 大家说得对，三题用线段树套平衡树显然更简单、更科学。
四题显然应该是先二分k，关键是怎么检验？我的做法是枚举交点Pi，枚举圆Cj（Pi不在Cj上），然后找出Cj上的所有交点所能产生的弦的中点与Pi的连线的中点，对它们进行检验。如果是三个圆交成一个空心的“瘪三角形”区域的话，画画草图就能明白我这样做的理由，关键是圆多了的话不知有反例没。结果最后没调出来，搞了半天就把一二两题做了。后来一想也就算了，反正第四题这么做也没啥根据，估计是错的。

今天下午的，一题垃圾题，二题纯计算几何，三题二分加网络流？
四题是个科学题目，O(根号n)的算法：先预处理数组f[d][r][s]，表示后一半有d位数，模k余r，数字都在给定集合内，数字和为s的情况有多少种。然后枚举前面一半，直接查表累加就可以了。代码不是一般难写，要处理很多特殊情况。我已经N久没写过这么麻烦的代码了。最后还是写垃圾了，效率居然比暴力还慢，不知道是不是哪儿写错了。谢wywcgs提醒，算法错了。即使只处理一半的长度，k仍然巨大无比。 刚才在路上突然想到了（其实最初我也是这样想的，后来做着做着就忘了这个细节）：正如网友Zero所说，这道题目可以分情况套用两种不同的算法。k较小时用上面的算法没错，当k的长度超过y的一半时可以直接暴力枚举k的倍数，复杂度仍为O(根号n)。

几乎都是科学题目。算法大概都知道，就是写代码的能力太差太差了啊。

我把题目搞丢了，麻烦哪位给一个比赛题目的链接，谢了。
Update: 感谢网友dahe_1984提供两次比赛题目的链接：
http://hi.baidu.com/one%5Fperson/blog/item/ef8d0d4ce0d952fcd62afc35.html
http://hi.baidu.com/one%5Fperson/blog/item/4d211e23db8ddd4b93580737.html

    在这篇文章里，我们从信息论的角度证明了，基于比较的排序算法需要的比较次数（在最坏情况下）至少为log2(n!)，而log(n!)=Θ(nlogn)，这给出了比较排序的一个下界。但那里我们讨论的只是最理想的情况。一个事件本身所含的信息量是有大小之分的。看到这篇文章之后，我的思路突然开阔了不少：信息论是非常强大的，它并不只是一个用来分析理论最优决策的工具。从信息论的角度来分析算法效率是一件很有趣的事，它给我们分析排序算法带来了一种新的思路。

    假如你手里有一枚硬币。你希望通过抛掷硬币的方法来决定今天晚上干什么，正面上网反面看电影。投掷硬币所产生的结果将给你带来一些“信息”，这些信息的多少就叫做“信息量”。如果这个硬币是“公正”的，正面和反面出现的概率一样，那么投掷硬币后不管结果咋样，你都获得了1 bit的信息量。如果你事先就已经知道这个硬币并不是均匀的，比如出现正面的概率本来就要大得多，这时我们就说事件结果的不确定性比刚才更小。如果投掷出来你发现硬币果然是正面朝上，这时你得到的信息量就相对更小（小于1 bit）；反之如果投掷出来居然反面朝上了，那你就得到了一个相对较大的信息量（大于1 bit）。但平均下来，我们得到的信息量是小于1 bit的，因为前者发生的可能性毕竟要大一些。最极端的情况就是，这是一枚被捣了鬼的魔术硬币，你怎么投都是正面。此时，你投了硬币等于没投，反正结果都是正面朝上，你得到的信息量永远为0。
    这个理论是很符合生活实际的。昨天晚上我出去吃饭时，坐在我后面的那个人是男的还是女的？这种问题就比较有价值，因为大家都猜不到答案究竟是什么；但要问我昨天跟谁一起出去上自习去了，问题的答案所含的信息量就变小了，因为大家都知道如果我破天荒地跑去自习了的话多半是有MM陪着一起去的。如果有网友问我是男的还是女的，那就更不可思议了，因为我不但多次在这个Blog里提到我一直想找一个合适的MM，还在AboutMe里面发了我的照片。如果某人刚操完一个MM，突然扭过头去问“对了，你是男的还是女的呀”，那这个人绝对是一个不折不扣的大傻B，因为这个问题所能带来的信息量几乎为0。
    总之，当每种结果出现的概率都相等，事件的不确定性达到最大，其结果最难预测时，事件的发生将会给我们带来最大的信息量。我们把一个事件的不确定程度叫做“熵”，熵越大表明这个事件的结果越难以预测，同时事件的发生将给我们带来越多的信息。如果在排序算法里每次比较的熵都是最大的，理论上来说这种（基于比较的）排序算法就应当是最优的。但我们一会儿将看到，我们已知的排序算法总是不完美的，每种算法都会或多或少地存在一些价值明显不大的比较。

查看更多 »

1. 给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
2. 给你n个数，其中有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。

1. 从头到尾异或一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑到异或运算满足交换律，先异或和后异或都是一样的，因此这个算法显然正确。

2. 从头到尾异或一遍，你就得到了需要求的两个数异或后的值。这两个数显然不相等，异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位，然后把所有这n个数分成两类，在那一位上是0的分成一类，在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。

题目来源：http://groups.google.com/group/pongba/browse_frm/thread/f4a080edbe3ce0e1

查看更多 »

    早晨7:40的闹铃。到36楼下面见到了我的两个队友后，随便吃了点东西就出发了。
    计算中心门前特别热闹，N多人围在一张大桌子前，好像是在签到。我挤进去找了半天发现没我的名字，名单上全是信科的人。我抬头问，中文的在哪儿呢。一个美女姐姐用手指了远处的一个几乎没人的地方说“中文的在那边”，并说了一句“哇，中文的呀，太牛B了”。我顺着她手指的方向望过去，另一张小桌子前面贴了“中文”二字，桌子后面没有人，估计是交给了旁边负责数院和元培的人，让他们顺便管一下。从我目前所了解的情况来看，那张桌子应该是特别为我准备的，它在历史上很可能是第一次出现。

      
    第四题是做得最顺利的一道题。我把所有题粗略看了一遍后，首先决定就想这道题。题目描述巨简单，就是问你沿对角线把一个正n边形剖分成三角形和四边形有多少种方法。上图显示了n=5时所有的10种方法。熟悉组合数学的人都知道，三角形剖分方案对应的是Catalan数列，其递推公式的推导相当经典。设C(n)表示凸n+2边形的剖分方案数，枚举底边和哪一个点相连（下图左），容易看出C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... + C(n-1)*C(0)。
    
    现在，如果剖分中允许有四边形的出现，又该怎么办呢？看看数据规模n≤5000，估计应该是叫我们寻找类似的递推公式。容易想到，我们可以枚举底边与哪一个点相连构成三角形，统计出底边属于某个三角形的剖分方案T(n)=ΣC(i)C(j), i+j=n-1；再枚举底边和哪两个点相连构成四边形，统计底边在一个四边形上的剖分数Q(n)=ΣC(i)C(j)C(k), i+j+k=n-2。但是，枚举四边形需要O(n^2)的时间，这样的话整个程序就是O(n^3)的了，n=5000绝对超时。那怎么办呢？两分钟后，我想到了一个具有决定意义的点子：计算Q(n)可以直接利用以前算过的T(i)。枚举四边形的两个顶点时，固定四边形的左边那个顶点，你会惊奇地发现右半部分的所有情况加起来正好就是一个T(i) （上图右）。因此，ΣC(i)T(n-i-1)就是我们所需要的Q(n)。
    一个有趣的细节是，这道题要求选手输出结果除以2^64的余数，不知道会不会有人想不到这个该怎么处理；事实上只需要直接用64位无符号类型来运算就可以了，超界了后计算机储存的本来就已经是2^64的余数了。

查看更多 »