（不知道Paul Potts是谁的请自行Google） Pual Potts出专辑了，名叫One Chance，我正在下载（当然，等国内有了我也会去买正版碟的）。 我喜欢Paul Potts，因为他与我一样，外表平凡，内心有着非凡梦想。 唯一不同的是，Paul遇到了他的One Chance，他的梦想已然照进现实。而我的梦想，正在路上。 在路上，我知道，我的One Chance，就在前方不远。
Chordal Graph：图中任何长度不小于4的环都存在弦（连接两个在环中不相邻顶点的边）。 Interval Graph：将图的每个顶点定义成一个区间，顶点间有边当且仅当两个区间相交。 Interval Graphs都是Chordal Graphs。 Perfect Elimination Order：无向图的顶点的一个排序，将这个作为拓扑序给边定向。满足每个点的前驱集合在原图中都是一个Clique。 图存在PEO当且仅当它是Chordal Graph。 当图存在PEO时，可以用贪心策略线性地解决几个在一般图中NP-Hard的问题。（Pred(v)表示PEO中在v点之前且与v点有边的顶点集合。） (1) Coloring：按照PEO的顺序考察每个点，给它染没有被前驱用掉的最小颜色，也就是说：Color[i]=mex{Color[j]|j∈Pred(i)}。 (2) Clique：一定具有Pred(v)∪{v}的形式。 (3) Independent Set：按照PEO的逆序考察每个点，若当前它没有邻接点被选择，就选择它。 PEO的求法： (1) Maximum Cardinality Search：每次找与当前序列中邻接的点数最多的点并加入序列中。O(V+E) (2) lexBFS：不好实现，略。 对于给定的图和顶点序列，判断是否是PEO：对于序列中的每个点v，找它最靠后的那个前驱u，并判断u是否与v的所有其它前驱有边。O(V+E) Chordal Graph Recognition：首先用MCS求出一个序列，再用上述方法判断它是不是PEO。 Simplicial Vertex: 邻接点的集合是一个Clique的顶点。 Chodal Graphs中肯定存在Simpicial Vertex（PEO的最后一个点）。所以PEO也可以通过不断找Simplicial Vertex并删除的方法求出（复杂度大）。事实上，只要Chodal Graphs不是完全图，至少存在两个Simplicial Vertices（PEO的最后一个点，以及不与最后一个点邻接的最靠后的点）。 Comparability Graph：存在满足无环(acyclic)和传递性(transitive)的边定向方式的无向图。其中传递性指：若存在边(u,v)和(v,w)则必存在边(u,w)。 Inverval Graph的补图是Comparability Graph（存在边的两个顶点的区间都是不相交的，按照区间的左右关系定向即可），逆命题不成立。Comparability Graphs与Chordal Graphs没有什么特别的关系。 Comparability Graph Recognition：暂略。 在Comparability Graph上可以定义每个顶点的Layer：L(v)=1+max(L(w)|w->v)。 L就是图的一种最优Coloring，同样选择L不同的顶点就是最大Clique。图的色数和团数都是最大的L值。 Minimum Clique [...]
GDB的确是调试程序的强力工具，感觉又找到了除了已经很熟悉的静态调试以外的另外一把利器。 关于GDB的基本用法，我是看巫山霏云的GDB不完全手册入门的。我本来也想写个帖子总结一下，不过看到了Evalls写的相当完善的总结，就不再重复劳动了。
See Also: http://blog.sina.com.cn/xjoxjoxjo http://blog.sina.com.cn/marforever 7月11日 1. Emacs+GDB的确是正确的选择。 2. 代码复查是好习惯。 3. 双向搜索、或者说折半搜索的思想。（第三题） 7月12日 1. 越是简单的题，越是需要用DataMaker、代码复查等各种手段反复查错，保证AC。例如今天的第一题，写错太不应该了。一定要警惕在某道题上花费时间太少的情况。 2. 出现访问段异常时，如何在GDB中定位到异常的那一行？ 3. 第三题那个AC程序的随机化——不断缩小随机的范围，相当神奇。 7月13日 1. emacs -nw 更好用。 2. 第三题文件名写错，300分变成200分，攒RP了。 7月14日 1. 第一次见的经典网络流题AC了还是很高兴的。Dinic果然无敌。 2. DP题还是要先慎重确定方程无误后再下手。注意贪心（第三题）。 7月15日 1. 第三题绝对是太贪了，考虑太复杂。不过也怨题目没有给出更详细的数据范围。否则我就很可能Brute Force了。 2. 第二题独立想到，图论基础还是可以的。 3. 第一题策略严重不当，想的二分答案，等二分答案的所有步骤都写完了才意识到不能直接二分（也没想到yxy那种找单调性的上下界然后二分的方法）。 4. 强调一下：先把算法想清楚再下手。 5. 细节的确决定成败，第三题明明想到了Fibnacci数，也想到了那个唯一分解的定理，但由于错误的“负Fibnacci数”的想法，导致满盘皆输。只是一个小小的偏移量就可以避免麻烦的负数。真是心有不甘啊。 7月17日 1. 多日以来攒的RP终于在今天短暂爆发，拿到了第一个真正的300。不过就像别人说的那样，这导致我今天的收获远不如前几天。但也不一定，前几天得到的是“教训”，今天得到的就是“经验”了，例如：高度模块化（大不了最后再改成inline、define），坚持迭代式的编程（滚动数组、最优性剪枝、常数优化之类的东西都一定防盗最后再搞）。看到其他几个人的代码风格真是惨不忍睹。 2. 你以为会个最短路、会个网络流就是会图论算法了吗？看看Graph-Theoric Algorithms吧。太优美了，真的。 3. Emacs学习告一段落。GDB还是做不到熟悉的静态调试那样得心应手。 7月18日 1. 第一题正确的贪心策略没有想到，用加卡时的乱搞得了一半的分数，还是很满足的。 2. 第二题做过的题20mins就写AC了，就应该这样。 [...]
(defun cpp-mode() ;; tab相关的设置 (setq indent-tabs-mode nil) (setq default-tab-width 4) (setq tab-width 4) ;; 高亮匹配括号 (show-paren-mode t) (setq show-paren-style ‘parentheses) ;; 换行的同时对齐 (define-key c-mode-map [return] ‘newline-and-indent) ;; C编辑风格 (c-set-style “stroustrup”) (c-toggle-hungry-state) (c-toggle-auto-state) ) (add-hook ‘c++-mode-hook ‘cpp-mode) 因为目前我只用emacs写C++，所以也就只设置了c++-mode，用起来真是非常非常舒服。感觉key-in和debug的效率都很有提高。不过问题是，到了福州以后，难道还得在开始写程序前用一分钟写个.emacs？