近期必须要提高效率。用二至三天的时间详细记录时间表，以提高效率。每天早计划晚总结。 必须要做的是把Linux装好，Emacs和Vim都试试。总结一下自己用Dev-C++时需要的全部功能，然后用某种编辑器全部替代了。GDB也可以试试，如果真的很爽的话就用Emacs了。Vim最无奈的就是编译了，感觉上比较好的解决方案还是写makefile，这样的话多Tab要搞清楚。 算法方面，一个必须要掌握的就是块状链表，考的可能性很大，所以说完全可以花一两天甚至更多时间仔细研究仔细实现，除了NOI2005那个题以外还得找别的练习一下。网络流再写一两遍relabel-to-front，感觉一下，有空的话写个HLPP也行，Dinic写不写似乎都没关系，毕竟距离标号已经写得很熟了。 平衡树是另外一个大重点，一定要多练些麻烦的题练熟了。把递归Treap和Buttom-Up Splay要练到十分钟/十五分钟能默写的程度。 字符串处理方面。Trie图的相应的那几道题目做了也就没什么需要多说的了。最好搞懂“扩展KMP”是什么东西。后缀数组，如果遇到了非得O(N)的题再考虑学Skew Algorithm，否则就把nlogn的好好掌握就行了。 做题的话，SGU应该在一周内告一段落。下一步就去SPOJ攻难题吧，也可以照着网上的题目推荐内容做些POJ/Ural之类的补充。另外发现TopCoder的题目很不错，对照着题目/题解欣赏下似乎很好。 效率，一定要注意效率。珍惜时间，绝对不启动浪费大块时间的娱乐计划。
最近大部分人可能上不去OIBH。所以ioiforum的猫欢迎OIers前去讨论OI问题。据我所知，ioiforum是有神牛出没的。所以说若你有疑难问题希望得到指点，到那里发帖应该是个不错的选择。 地址：http://ioiforum.bytecool.com/ （本文为友情广告）
最大权二分匹配问题就是给二分图的每条边一个权值，选择若干不相交的边，得到的总权值最大。解决这个问题可以用KM算法。理解KM算法需要首先理解“可行顶标”的概念。可行顶标是指关于二分图两边的每个点的一个值lx[i]或ly[j]，保证对于每条边w[i][j]都有lx[i]+ly[j]-w[i][j]>=0。如果所有满足lx[i]+ly[j]==w[i][j]的边组成的导出子图中存在一个完美匹配，那么这个完美匹配肯定就是原图中的最大权匹配。理由很简单：这个匹配的权值之和恰等于所有顶标的和，由于上面的那个不等式，另外的任何匹配方案的权值和都不会大于所有顶标的和。 但问题是，对于当前的顶标的导出子图并不一定存在完美匹配。这时，可以用某种方法对顶标进行调整。调整的方法是：根据最后一次不成功的寻找交错路的DFS，取所有i被访问到而j没被访问到的边(i,j)的lx[i]+ly[j]-w[i][j]的最小值d。将交错树中的所有左端点的顶标减小d，右端点的顶标增加d。经过这样的调整以后：原本在导出子图里面的边，两边的顶标都变了，不等式的等号仍然成立，仍然在导出子图里面；原本不在导出子图里面的边，它的左端点的顶标减小了，右端点的顶标没有变，而且由于d的定义，不等式仍然成立，所以他就可能进入了导出子图里。 初始时随便指定一个可行顶标，比如说lx[i]=max{w[i][j]|j是右边的点}，ly[i]=0。然后对每个顶点进行类似Hungary算法的find过程，如果某次find没有成功，则按照这次find访问到的点对可行顶标进行上述调整。这样就可以逐步找到完美匹配了。 值得注意的一点是，按照上述d的定义去求d的话需要O(N^2)的时间，因为d需要被求O(N^2)次，这就成了算法的瓶颈。可以这样优化：设slack[j]表示右边的点j的所有不在导出子图的边对应的lx[i]+ly[j]-w[i][j]的最小值，在find过程中，若某条边不在导出子图中就用它对相应的slack值进行更新。然后求d只要用O(N)的时间找到slack中的最小值就可以了。 如果是求最小权匹配，只需要把那个不等式反一下就行了。算法需要作出的改变是：lx的初值为所有临界边中的最小值，find中t反号。 示例程序(Ural 1076)： ural1076.cpp
当在程序中使用滚动数组之类的优化手段时，一般我们会先写出不用滚动数组的程序，用小数据调试、验证后再将它改成用滚动数组实现。这时，你会如何实现这样的改动呢？好吧，请看看，使用C++，可以将滚动数组实现得多么优雅，如何将一个只改声明部分、不改实现部分就引入滚动数组的优化。 程序请见：http://ddsgu.yo2.cn/183.html
NOI2003的editor（文本编辑器）一题的标准解法是“块状链表”。这个东西我以前没有写过，怎么想都觉得无法将这个东西妥帖地实现。找到的一个这道题的C++程序竟然有三百多行，让我看得着实很恶心。这道题能不能不用这种很不优美的数据结构来解决呢？答案是肯定的！ 我把我解决这个问题时使用的技术称为“实时离散化”。首先解释离散化，一种合适的理解就是将需要处理的序列中的某些连续的区间当作一个元素来操作，以减少总的元素数量。对于这道题而言，如果我们事先能够知道“在哪些字母的前后会插入一个区间”“在哪些字母的前后会有区间被删除”，把这些字母称为“关键字母”，用一个关键字母来代表它与它后面的所有非关键字母，就可以大大的降低时间复杂度了。因为INSERT和DELETE的操作总数不超过4000次，“关键字母”的总数也不会超过4000*2个，这样就相当于所有的插入删除操作都在最多8000个（而非2000000个）元素组成的串上进行，当然就会很快了。问题是，我们无法在一个字母被插入时判断出它是否会在将来成为“关键字母”，也就是说，无法像某些题目一样只做一次初始的离散化，我们的“离散化”必须是“实时”的，也就是，必须实时的维护可以被一同处理的区间。 听上去有点玄妙，其实很简单。用一个很长的字符数组保存曾经被插入的所有字符串，当前正在编辑的文本用一个区间的数组来表示，每个区间代表它在前述字符数组中的位置。当需要在某个区间的中间插入时，只需按照这个被插入的位置将这个区间分裂成两个，再在两个新形成的区间的中间插入就可以了。同样，删除时也只需要按照需要被删除的文本两端将它们所在的区间分裂成两个，然后删除连续的若干个区间就可以了。设修改操作一共做了M次，则任何时候的区间总数不会超过2M个，所以每次操作的时间复杂度都是O(M)，所有修改操作的总时间复杂度是O(M^2)，而且常数很小，由于M<=4000，是完全可以承受的。INSERT和DELETE都实现了，GET也很好实现，挨个输出就行了，PREV和NEXT更是常数时间而已，最多可达到50000次的MOVE呢？如果每个MOVE的复杂度也都是O(M)似乎会有超时的危险。注意到这样一个明显的事实：若有连续的MOVE操作，只需要做最后一次的操作即可。经过这样的处理，需要实际做的MOVE操作大约也只是O(M)的级别。 对于这类在序列上进行添加、删除、反序等修改的题目来说，设修改操作有M次，序列的最大长度为N，块状链表的复杂度是O(M*N^0.5），“实时离散化”的复杂度是O(M^2)或者O(M^2+N)，可见它在很多情况下是很有代替块状链表的可能的。对于某些题目而言，我认为它是相对于块状链表的一个更高层的抽象，所以编程要简单优雅很多（我的堆砌着大堆短函数的拖沓程序用了156行，其中核心的部分仅有不到100行），也不失效率。对于本题来说，我的程序可以P4 2.oG的电脑上最大数据1.6s左右，是可以AC的。但是，“实时离散化”还是不能完全代替块状链表，比如说当M与N同阶的时候就会退化成O(N^2)（因为已经失去了离散化的意义了），而块状链表仍然保持着O(N^1.5）。 示例程序： editor.cpp