| Profil de Matrix67Matrix67's SpaceBlogListes |  Outils  Aide |
|
15 décembre 给大家推荐一些书 近来有很多问该看什么书的。我说一下个人意见（仅代表个人意见）。大家可以按照这样的顺序来阅读这些书（时间足够的话）：
《算法导论》
《数据结构与算法分析——C语言描述》
《组合数学》
这三本书必看，都是机械工业出版社出版的，翻译质量嘛——尽管有些别扭（翻译的东西都这样），但肯定看得懂。
第一本的中译本是才出版的，比原来那个盗版的要好得多。
第二本是Mark Allen Weiss写的，第二版。
第三本是Richard A.Brualdi写的，第四版。
如果你英文好的话，最好看原版。
有人会问我为什么喜欢国外的教材。这是因为，国外的教材各个章节安排得很好，体系性更强，看起来更轻松（保证你能看懂），而且更具有启发性。这些教材的习题安排得很好，绝对是可以经过独立思考想出来的题目。和国内很多教材扔出一大堆概念和公式不同，阅读国外教材是循序渐进的一个学习过程。
以下两本书的话，有兴趣就看吧。
《离散数学》，第六版，Richard Johnsonbaugh，电子工业出版社。
《How to Ace Calculus: The Streetwise Guide》系列，中译本叫做“微积分之XXXX”，湖南科学技术出版社。当成看小说吧，很有意思，是我见过的最不像教材的教材了。
最后需要看的是刘汝佳和黄亮的《算法艺术与信息学竞赛》。这里面有很多概念上的讲解是错误的，但是题目讲解的资源很丰富。当前面的书看完了后，拿最后这一本当作题库来实战演练吧。书里的概念讲解部分就不必看了，直接消化里面的例题，一道一道地消化。第三部分的计算几何可以仔细学习一下，因为这部分内容之前的书好像涵盖得不多。
还有，选择什么样的题库。个人首推USACO。大家可以自己了解一下这个与众不同的OJ，它基本上是一个“个人的教练”，并不参与网络排名。你大概需要话半年的时间完成所有的题目。做USACO需要你的认真态度和耐心。千万别看中译和别人的解答。整个USACO的任务完成之后，你基本上就无敌了。 14 décembre X200果然跑不动Xgl 这几天没更新是因为我在搞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，争取做一份过年大礼。 2 décembre Matrix67的OI点滴（四）：König定理的证明 如果你看不清楚第二个字母，下面有一个大号字体版本：
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个点（用“√”表示）。那么，用红色圈起来的三个点就是我们的最小覆盖点集。 首先，为什么这样得到的点集点的个数恰好有M个呢？答案很简单，因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的，那么它早就当成起点被标记了；如果左边的哪个点是没有匹配过的，那就走不到它那里去。而一个匹配边又不可能左端点是标记了的，同时右端点是没标记的（不然的话右边的点就可以经过这条边到达了）。因此，最后我们圈起来的点与匹配边一一对应。 其次，为什么这样得到的点集可以覆盖所有的边呢？答案同样简单。不可能存在某一条边，它的左端点是没有标记的，而右端点是有标记的。原因如下：如果这条边不属于我们的匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果这条边属于我们的匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的（想想匹配的定义），左端点就应该有标记。 最后，为什么这是最小的点覆盖集呢？这当然是最小的，不可能有比M还小的点覆盖集了，因为要覆盖这M条匹配边至少就需要M个点（再次回到匹配的定义）。 证完了。 Matrix67原创
做人要厚到 转贴请注明出处 29 novembre Matrix67的OI点滴（三）：KMP算法 如果机房马上要关门了，或者你急着要和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算法。 假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A[i-j+1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当i=j=5时的情况。
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7 此时，A[6]<>B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j'。j'可能是多少呢？仔细想一下，我们发现，j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）。这个j'当然要越大越好。在这里，B[1..5]="ababa"，头3个字母和末3个字母都是"aba"。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了4：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7 从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]<>B[j+1]的情况： i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7 由于P[5]=3，因此新的j=3：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7 这时，新的j=3仍然不能满足A[i+1]=B[j+1]，此时我们再次减小j值，将j再次更新为P[3]：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b … B = a b a b a c b j = 1 2 3 4 5 6 7 现在，i还是7，j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样，j必须减小到P[1]，即0：
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b … B = a b a b a c b j = 0 1 2 3 4 5 6 7 终于，A[8]=B[1]，i变为8，j为1。事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。
这个过程的代码很短（真的很短），我们在这里给出： j:=0;
for i:=1 to n do begin while (j>0) and (B[j+1]<>A[i]) do j:=P[j]; if B[j+1]=A[i] then j:=j+1; if j=m then begin writeln('Pattern occurs with shift ',i-m); j:=P[j]; end; end; 最后的j:=P[j]是为了让程序继续做下去，因为我们有可能找到多处匹配。
这个程序或许比想像中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。
现在，我们还遗留了两个重要的问题：一，为什么这个程序是线性的；二，如何快速预处理P数组。
为什么这个程序是O(n)的？其实，主要的争议在于，while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略，简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环中后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。
预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],...,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb"，假如我们已经求出了P[1],P[2],P[3]和P[4]，看看我们应该怎么求出P[5]和P[6]。P[4]=2，那么P[5]显然等于P[4]+1，因为由P[4]可以知道，B[1,2]已经和B[3,4]相等了，现在又有B[3]=B[5]，所以P[5]可以由P[4]后面加一个字符得到。P[6]也等于P[5]+1吗？显然不是，因为B[ P[5]+1 ]<>B[6]。那么，我们要考虑“退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到，即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下：
1 2 3 4 5 6 7
B = a b a b a c b P = 0 0 1 2 3 ? P[5]=3是因为B[1..3]和B[3..5]都是"aba"；而P[3]=1则告诉我们，B[1]和B[5]都是"a"。既然P[6]不能由P[5]得到，或许可以由P[3]得到（如果B[2]恰好和B[6]相等的话，P[6]就等于P[3]+1了）。显然，P[6]也不能通过P[3]得到，因为B[2]<>B[6]。事实上，这样一直推到P[1]也不行，最后，我们得到，P[6]=0。
怎么这个预处理过程跟前面的KMP主程序这么像呢？其实，KMP的预处理本身就是一个B串“自我匹配”的过程。它的代码和上面的代码神似： P[1]:=0;
j:=0; for i:=2 to m do begin while (j>0) and (P[j+1]<>P[i]) do j:=P[j]; if P[j+1]=P[i] then j:=j+1; P[i]:=j; end; 最后补充一点：由于KMP算法只预处理B串，因此这种算法很适合这样的问题：给定一个B串和一群不同的A串，问B是哪些A串的子串。
串匹配是一个很有研究价值的问题。事实上，我们还有后缀树，自动机等很多方法，这些算法都巧妙地运用了预处理，从而可以在线性的时间里解决字符串的匹配。我们以后来说。
昨天发现一个特别晕的事，知道怎么去掉BitComet的广告吗？把界面语言设成英文就行了。
还有，金山词霸和Dr.eye都可以去自杀了，Babylon素王道。 Matrix67原创 转贴请注明出处 22 novembre 这几天过得有些颓废 小时候家离交行最近，以我妈的名义办了一张太平洋卡，后来卡长期不用，搞丢了。前段时间没事干了的时候，拿自己的身份证去搞了一张，当天晚上就后悔了：太平洋卡在重庆还不支持网上支付。今天我的IBM赠送的Norton已经过期了半个月了，我不得不为了网上续订升级服务，换家银行再办一张卡。网上查了一下，阳光卡看起来最阳光，就到光大去搞了张卡。回家整了N久，装了N多光大的IE插件，得到的结论是：（在我看来）光大的貌似也不支持网上支付，虽然银联网上支付系统声称它支持。最后，我不得不放弃了，又颓废了一次：搞了NAV 2005续订日期延长破解补丁，省了80块钱。破解得貌似不是很好，号称能延长150年但我这里只延长到了今年年底。明天把阳光销了再去试试工商行的。网上支付还是有用的，除了Norton的续订号，有些东西你也不得不在网上买，比如跳蛋或者充气娃娃。
每年的这个时候过得都有点阴暗。前几天MSN上收到了半打人的告别，有几只牛（水牛也算牛）也打算回归高考了。感觉很悲哀，自己也会莫名地伤感起来。OI的变数太大了，我本以为很有希望的人都考栽了，倒是平时不太注意的人突然来了个RP++。最后仍然是几家欢乐几家愁，只是谁乐谁愁很出乎意料。论坛上发愁的比较多，乐的都偷着乐去了。昨天晚上和MM吵架，还好是用短信吵的，内容（或者说起因）大概也和NOIp有关。后来我怕她了，让。男的和女的吵架时男的要让着点，毕竟女的有一些麻烦事，比如每个月心情都会周期性地烦躁一次。 再说点别的。那天从CSC出来，听到一首很好听的歌，一听就喜欢上了。回去一查，韩雪，竹林风。我下了韩雪这个人（名字不错）的第一张专辑，真的很好听。很喜欢《飘雪》和《想起》。CSC还喜欢放《爱我就自首》，也有点意思。CSC很有商业头脑，每个学校旁都立一个，就是冲着学生来的，放学时间赚得盆满钵满。十周年了，难得啊，我初恋才四周年呢（不算小学不懂事乱来的那种）。现在生活很没规律（或者说很有规律），下午3:00起床（大家上午想找我的就不用费心了），去CSC吃饭，顺便外面逛逛，晚上总有美剧可以看，然后当夜猫子搞到个凌晨四五点。下午的时候去CSC很有情调，那时为了节电要关灯，往里面走很幽暗。经常会看到有人阴在角落里接吻的。 明天开始，不浪费时间了，写点关于OI的东西，或者继续搞电子书，或者泡MM。有点出去打工的欲望。 16 novembre 祝福所有人这段时间相当忙，因此没有更新我的Space
但从统计上来看，仍然有相当数量的人在访问
在这里感谢你们的支持，祝你们NOIp 2006成功
等NOIp过去了，这里将继续更新 18 octobre 最长公共上升子序列的另一个O(mn)的算法 我在这个帖子里说过nlogn求最长上升子序列的方法：
http://www.oibh.org/bbs/viewthread.php?tid=10682 下面引用我自己的发言：
这里要说的这个算法利用了nlogn的最长上升子序列(LIS)的技巧：用f[k]表示长度为k的上升子序列最后一个数最小是多少。
在最长公共上升子序列中，令f[i,j][k]表示A串前i个数字，B串前j个数字，长度为k的公共上升子序列中，最后一个数最小是多少。 当A[i]=B[j]时，像nlogn的最长上升子序列一样把A[i]插入到f[i-1,j]中，这需要线性的时间扫一遍f[i,j]；
当A[i]<>B[j]时，我们需要合并f[i-1,j]和f[i,j-1]，使得对于每个k满足f[i,j][k]:=min{ f[i-1,j][k],f[i,j-1][k] }。这需要线性的时间扫一边f[i-1,j]和f[i,j-1]并取k相同时的较小值。 最后输出f[n,m]的长度（使f[n,m][k]有意义的最大的k）。 这样的复杂度是三方的，我们需要优化。
考虑A[i]=B[j]的情况。当i固定时，随着j的增加，插入的位置一定也在后移，因为同样是插入的A[i]，但j的增加（B串长度的增加）使得f[i,j]更优，因此可以更新的值就更靠后。于是，对于每个i，我们可以按照k的顺序扫描f[i-1,j][k] 并在A[i]可以插入f[i-1][j]的k位置时增加j，从而预处理所有A[i]=B[j]时A[i]应该插入的位置。
再考虑A[i]<>B[j]的情况。从定义看，f[i-1,j-1]和f[i-1,j]只有一个地方不一样，因为多一个数最多只能造成一个k的值变小；同样地，f[i-1,j-1]和f[i,j-1]也只有一个地方不一样。因此，f[i-1,j]和f[i,j-1]最多只有两个k所对应的值不相同，且当有两个不同的值时，总是f[i-1,j]中的某个值较小，f[i,j-1]中的某个值较小。这给我们优化的余地。在每次处理完f[i,j]时，我们可以记录一个值x[i,j]表示f[i,j][k]与f[i-1,j][k]中值不一样的k是多少，在A[i]=B[j]时直接赋值为插入的位置，在A[i]<>B[j]时待后文说明。以后合并时，先让f[i,j]:=f[i-1,j]（由于此时的f[i-1,j]已经没有别的用处了，因此可以用滚动数组记录，直接令f[i-1,j]是f[i,j]，避免实际的赋值操作），然后将新的f[i,j]中的，使f[i,j-1][k]比f[i-1, j][k]小的k所对应值更新。这个k是多少呢？显然应该是x[i,j-1]。这样的操作同时可以确定x[i,j]=x[i,j-1]。 这样，复杂度就达到了平方。
附参考的资料（原来从这篇论文里学到的，不知道有没有此类的中文资料，估计没有才在这里写了一个，感兴趣的话可以下载附件仔细研究）
http://matrix67.51.net/2005_IPL_LCIS.pdf Matrix67原创
转载请注明出处 Matrix67's SpaceShut down... moved to matrix67.com |
||||
|
|
