我：爸，你听过 Paul Potts 的歌么？

我爸：他是谁呀？你听过陈楚生的歌么？

我：……这就是代沟啊。-_____-

坦率讲，并没有在省队集训中真正“学到”什么东西。最大的收获是在九场测试中得到的临场经验，以及Emacs的学习和应用。

遇到会做的题，应该用迭代开发/代码复查/生成数据等各种方法保证正确性。Coding也不宜太快，毕竟NOI的时间是充足的。

遇到大致知道方法但是写起来很麻烦的题目，不妨先花几分钟写一个Brute Force的程序放到那儿，然后在埋头Coding。那种麻烦题目一定要把思路完全理清楚了再去写，千万不要写到一半写不下去了，那是最得不偿失的。

遇到暂时想不出来的题，不用慌，慢慢分析，或者从一个垃圾程序开始慢慢迭代开发。相信自己的实力。

遇到一看便知很麻烦很麻烦的题，大胆放弃，但写个Cheat程序还是必不可少的（至少可以稳定情绪）。

注意先写程序后优化。程序的每个重要版本都要备份一下，例如第一个可以编译的版本，第一个过样例的版本，某次大改之前的版本等等。

在准备在程序中大量加入调试代码之前，先看看变量、数组的声明是否正确，看看有没有弱智错误。

近几天的安排：

任务一，每天写二至三道NOI难度或略低的题目，保持状态。

任务二，精炼一下几个（不太常写的）最基础的东西的代码：quicksort、heap、highprecition等。

任务三，打印自己写过的文章/代码看。

就这样吧。

（不知道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 Cover：流找出图的最小路径覆盖（用匹配），这就是Minimum Clique Cover了。这个值同样等于Independent Set的值。

Interval Graph Recognition：
(1) 一个图是Inverval Graph当且仅当它是Chordal Graph且它的补图是Comparability Graph。
(2) 一个图是Interval Graph当且仅当它的所有Maximal Clique可以被指定一个顺序，满足任何属于其中两个Clique的顶点也属于序列中处于这两个Clique中间的Clique。
算法是找出所有Maximal Clique并判断是否能如此排序。
用Chordal Graph的方法找出所有Maximal Clique。前述Chordal Graph的Clique形式Pred(v)∪{v}不是Clique当且仅当存在一个v的后继w，使v是w的最后一个前驱，且indeg(w)=indeg(v)+1。
然后要用PQ-Tree了，还不会呢……

Perfect Graph：满足团数等于色数且所有生成子图也满足的图。上面提到的一堆图都属于Perfect Graphs。
完美图的补图也是完美图。所以完美图（及其所有子图）满足：团数等于色数，独立数等于最小团覆盖数。这些数对于完美图都可以多项式地求出，但是我都不会求。

Intersection Graph：每个点代表一个集合，两个点有边当且仅当两个集合有公共元素。
所有图都是Intersection Graph，这是显然的。
一个图是Chordal Graph当且仅当它可以表示成一棵树的若干个子树的Intersection Graph。

Interval Graph的扩展：
(1) Circular-arc Graph就是将Interval Graph中的区间改成圆上的圆弧。
Circular-arc Graph不一定是Chordal Graph，也不一定是Perfect Graph。
(2) Boxicity Graph，将Interval Graph中的区间改成多维矩形。每个图都是Boxiicity Graph，对于适当的维d。对于Boxicity-2 Graphs，Clique是P的（算法？），但Independent Set依然NP-Hard。
(3) k-Interval Graph 每个点表示至多k个区间。没什么用的东西。

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了，就应该这样。
3. 第三题题意太不清，忽略。

7月19日

1. 提交答案题。出现一个重大失误，在算后面的数据时由于编程序的失误把前面已经算出来的解给覆盖了……看来以后要把已经算出来的解妥善保存好。还有就是对于今天这种很可做的提交答案题，要记得分配两个小时左右的时间。
2. 交互题浪费了太多时间，似乎还是因为没有完全想清楚就开始编程的缘故。（竟然是60分而且跑出了5个极限数据中的3个？我也很惊讶……）
3. 如果有巨BT的模拟，像今天第一题那样的，放弃是最明智的选择。

以学习为主。知道自己来这里干嘛的。

上午仔细做题，注意时间分配，练Emacs，练GDB。

中午另安排。

下午要把上午的所有题都搞清楚，除非公认不可能搞清楚。

晚上总结一天。

注意珍惜时间。

根据明天的情况再细化。

保持神秘是不厚道滴。发照片吧，哪怕冒着颜面尽失的风险……

到了101中学，刚打开电脑就被偷拍。

和魂牛合照，表情严肃。

站起来的我好低呀。

瞬间长高啦。

来参加传说中的河南省队集训。

电脑竟然比我们学校机房的电脑还烂。

我一来魂牛就偷拍我……

以前我爱用Vim，总觉得编写代码得心应手，编译调试就力不从心。特别是Vim到底怎么样能够在不用插件的情况下跟gdb完美结合，我到现在也没搞定。偶尔听到有人说Emacs+gdb很爽，就试了一下。按下M-x gdb后，我决定叛变了。

近段用Emacs写几个程序练练手吧，还好Vim没有我想象的那般在我脑中根深蒂固。

首先（不严谨地）定义自动机：自动机就是一堆状态的组合，给某个状态的自动机一个输入，它会按照自己的转移规则变到一个新的状态。事实上，可以把状态理解成顶点，把状态的转移理解成上面标着符号的边，在某个状态得到了某个符号的输入时，就转移到那条边指向的状态去。

先介绍单串匹配的自动机。对于M个字符的串S[1..M]，一个用这个串进行模式匹配的自动机需要M+1个状态。设状态i输入ch时的转移为auto[i][ch]。状态转移时要满足：若当前在状态i，说明已输入的最后i个字符是S[1..i]，若有多个状态满足这个定义，则应该在编号最大的状态。如何保证上述条件始终被满足呢？首先，auto[i][S[i+1]]=i+1，这是明显的。如果ch!=S[i+1]，则auto[i][ch]肯定应该转移到某个小于等于i的状态，这个状态j应该满足：它是串S[1..j]是S[1..i]+ch的后缀，且j是最大的。找出j的方法是：计算每个i的“后缀状态”，也就是给自动机输入S[2..i]后自动机应该在的状态suffix[i]，则当输入ch时应该转移的状态就是auto[suffix[i]][ch]的转移。计算suffix的方法是：suffix[i+1]=auto[suffix[i]][S[i+1]]，suffix[1]=0。单字符串的自动机就是这样构造的。每次转移到状态M时，就找到了一个匹配。

值得注意的是，上述suffix数组所含的信息和KMP算法求出的所谓next数组其实是完全一致的。其实CLRS上也说，KMP算法就是通过少量的预处理实时地均摊O(1)地求出自动机的状态转移（大意）。也就是说，串匹配自动机也可以这样实现：首先通过预处理求出suffix数组，然后在状态i输入了字符ch时，需要转移到状态auto[i][ch]，但是具体转移到哪个状态我们并没有预处理求出，我们只知道：若S[i+1]==ch则转移到i+1，否则转移到auto[suffix[i]][ch]。利用这两个条件，前者可以看做递归边界，就可以递归的求出每个需要的转移。可以证明的是这种求的复杂度是均摊O(1)的。

然后来看多字符串匹配的情况，其实和单字符串的时候差别不大，只不过状态之间不再是一个简单的线性结构了，而是一个Trie的结构，要根据刚才那个“后缀状态”的定义求出所有没有在Trie中直接出现的边应该转移到什么地方，同样也可以像KMP算法实时地计算那些转移。具体的方法都跟单串的没什么差别。

SPOJ上有两道题可以练习自动机：PSTRING是利用单串匹配自动机（或者KMP）进行状态转移的DP，WPUZZLES则是直接的多串自动机应用。

关于字符串匹配自动机，更详细的说明和更多应用可以找Maigo（王赟）关于Trie图的论文。