Content Preview: rss
1082 days ago
近来有很多问该看什么书的。我说一下个人意见（仅代表个人意见）。大家可以按照这样的顺序来阅读这些书（时间足够的话）： 《算法导论》 《数据结构与算法分析——C语言描述》 《组合数学》 这三本书必看，都是机械工业出版社出版的，翻译质量嘛——尽管有些别扭（翻译的东西都这样），但肯定看得懂。 第一本的中译本是才出版的，比原来那个盗版的要好得多。 第二本是Mark Allen Weiss写的，第二版。 第三本是Richard A.Brualdi写的，第四版。 如果你英文好的话，最好看原版。 有人会问我为什么喜欢国外的教材。这是因为，国外的教材各个章节安排得很好，体系性更强，看起来更轻松（保证你能看懂），而且更具有启发性。这些教材的习题安排得很好，绝对是可以经过独立思考想出来的题目。和国内很多教材扔出一大堆概念和公式不同，阅读国外教材是循序渐进的一个学习过程。 以下两本书的话，有兴趣就看吧。 《离散数学》，第六版，Richard Johnsonbaugh，电子工业出版社。 《How to Ace Calculus: The Streetwise Guide》系列，中译本叫做“微积分之XXXX”，湖南科学技术出版社。当成看小说吧，很有意思，是我见过的最不像教材的教材了。 最后需要看的是刘汝佳和黄亮的《算法艺术与信息学竞赛》。这里面有很多概念上的讲解是错误的，但是题目讲解的资源很丰富。当前面的书看完了后，拿最后这一本当作题库来实战演练吧。书里的概念讲解部分就不必看了，直接消化里面的例题，一道一道地消化。第三部分的计算几何可以仔细学习一下，因为这部分内容之前的书好像涵盖得不多。 还有，选择什么样的题库。个人首推USACO。大家可以自己了解一下这个与众不同的OJ，它基本上是一个“个人的教练”，并不参与网络排名。你大概需要话半年的时间完成所有的题目。做USACO需要你的认真态度和耐心。千万别看中译和别人的解答。整个USACO的任务完成之后，你基本上就无敌了。
1082 days ago
这几天没更新是因为我在搞Linux。我的本本硬盘小，当初装系统时没有狠下心；前几天看到了Mandriva 2007的新特性，经不住诱惑，一狠心就把我IBM的隐藏分区格了，我知道这意味着如果我的Win系统坏了的话就没救了（隐藏分区里的可是正版XP啊），不过想到XP坏了就装Vista，也就坦然了。 说到Vista，不过就是多了个Aero。如果你不用Aero的话，自己滚回XP去。但是，你有见过Linux的Xgl+Compiz吗？这是Mandriva 2007最大的新特性了：集成了3D桌面。如果你还没见过的话，第一次看到这些特效会让你大吃一惊，这个和Aero根本不是一个档次的。最终结果是：我的ATI X200不支持:( 有用X200的同志看到这个帖子以后，你就不必再去试了，我各种方法都试过了，系统都重装了好几次。乖乖地等官方驱动来支持吧。 这几天我已经完全变成夜猫子了，早上6:30睡觉，下午4:30醒，一到晚上精神就来了。幸好附近有一个24小时营业的吃的地方，不然我准被饿死。 说到24小时，一个月后的今天，呵呵！想起就激动！（有没有跟我一样激动的？） 接下来的安排：写完生成函数的讲解，然后重返OCR，争取做一份过年大礼。
1094 days ago
如果你看不清楚第二个字母，下面有一个大号字体版本： Matrix67的OI点滴（四）：König定理的证明 本文将是这一系列里最短的一篇，因为我只打算把König定理证了，其它的废话一概没有。 以下五个问题我可能会在以后的文章里说，如果你现在很想知道的话，网上去找找答案： 1. 什么是二分图； 2. 什么是二分图的匹配； 3. 什么是匈牙利算法；( http://matrix-67.spaces.live.com/Blog/cns!1p4LfxPH2nEZ7Y2ZGSNt_Llw!201.entry ) 4. König定理证到了有什么用； 5. 为什么o上面有两个点。 König定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小点覆盖数。如果你还不知道什么是最小点覆盖，我也在这里说一下：假如选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。比如，下面这个图中的最大匹配和最小点覆盖已分别用蓝色和红色标注。它们都等于3。这个定理相信大多数人都知道，但是网络上给出的证明并不多见。有一些网上常见的“证明”明显是错误的。因此，我在这里写一下这个定理的证明，希望对大家有所帮助。 假如我们已经通过匈牙利算法求出了最大匹配（假设它等于M），下面给出的方法可以告诉我们，选哪M个点可以覆盖所有的边。 匈牙利算法需要我们从右边的某个没有匹配的点，走出一条使得“一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现”的路（交错轨，增广路）。但是，现在我们已经找到了最大匹配，已经不存在这样的路了。换句话说，我们能寻找到很多可能的增广路，但最后都以找不到“终点是还没有匹配过的点”而失败。我们给所有这样的点打上记号：从右边的所有没有匹配过的点出发，按照增广路的“交替出现”的要求可以走到的所有点（最后走出的路径是很多条不完整的增广路）。那么这些点组成了最小覆盖点集：右边所有没有打上记号的点，加上左边已经有记号的点。看图，右图中展示了两条这样的路径，标记了一共6个点（用“√”表示）。那么，用红色圈起来的三个点就是我们的最小覆盖点集。 ...1097 days ago
如果机房马上要关门了，或者你急着要和MM约会，请直接跳到第六个自然段。 我们这里说的KMP不是拿来放电影的（虽然我很喜欢这个软件），而是一种算法。KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？” 解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O(mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A="aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设m<=n），即传说中的KMP算法。 之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。这时，或许你突然明白了AVL树为什么叫AVL，或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过，那怎么命名呢？通常这个东西干脆就不用人名字命名了，免得发生争议，比如“3x+1问题”。扯远了。 个人认为KMP是最没有必要讲的东西，因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift)”、“Next函数”等概念，这非常容易产生误解（至少一年半前我看这些资料学习KMP时就没搞清楚）。在这里，我换一种方法来解释KMP算法。 ...
