这次的题目还是不错的，有梯度，我的最终成绩是200/400。

第一题是简单的枚举，注意是可以翻转的。我错了10分是因为“Impossible”写成了“impossible”……汗一个……

第二题其实是贪心，先把所有的东西排一序从大往小了吃就行了。我考试时理解错题意了……只得了10分……这真的太不应该了。

第三题要判断树的同构。我是这样做的：求出树中每对节点间的最短距离，对于每个节点的序列先排序再hash得到一个数，再对现在的n个数先排序再hash，就是这棵树的hash值。就这样AC了。

第四题是一数学题……不说了。

很容易看出来这几天的效率降低了，似乎已经没有了那么多的算法要学，也没有那么多题目可写。是调整状态和心境的时候了。

消除了写并查集时的一个重大缺陷，值得微笑。

初步掌握了用矩阵乘法优化的DP，第一次写这种题目就AC了呢！实在是太高兴了。

掌握了求凸包的Gramham’s Scan的简便实现方法，大大缩短了代码长度。

认识了一位伊朗同学，呵呵，练了练英语，体验了不太寻常的经历，是很有意思的放松方式。

做了几套题目。山东04day2很有意思的说：prz是区间加法，lan我用了记忆化搜索（又很练了下静态调试），pro考到了并查集，最后作了一个不太严谨的优化，不过还是过了，呵呵。浙江05day1有广搜，有矩乘的DP，有思路特别的DP（其实还是跟背包相关）。这两套题目做的时候好像分别都放弃了一题，但基本保证了剩下的题目不出错（除了没辙的思路方向问题），这样也是值得的。学会细心，学会取舍。

做USACO的feb07gold也很有收获。newbarn是对中位数的比较强的考察，我更加理解了这个概念和应用，不过我还是觉得标程的算法有洞；lilypad是点带权值的最短路，给了我最短路模型构图的新思路；csort考到了置换群，算是对这个生僻的东西再用了一下。这次比赛的题目很有些“剑走偏逢”，真是收获不小。

下面这几天保证一天至少做一套题目就行，看看比较重要的代码，再编几遍重要的东西，比如说平衡树什么的；每天晚上可以看看小说放松自己，尽量午休，千万别把自己累着了；基本上没什么新东西需要学了。

异或方程组就是形如这个样子的方程组：

M[0][0]x[0]^M[0][1]x[1]^…^M[0][N-1]x[N-1]=B[0]
M[1][0]x[0]^M[1][1]x[1]^…^M[1][N-1]x[N-1]=B[1]
…
M[N-1][0]x[0]^M[N-1][1]x[1]^…^M[N-1][N-1]x[N-1]=B[N-1]

其中“^”表示异或(XOR, exclusive or)，M[i][j]表示第i个式子中x[j]的系数，是1或者0。B[i]是第i个方程右端的常数，是1或者0。

解这种方程可以套用高斯消元法，只须将原来的加减操作替换成异或操作就可以了，两个方程的左边异或之后，它们的公共项就没有了。

具体的操作方法是这样的：对于k=0..N-1，找到一个M[i][k]不为0的行i，把它与第k行交换，用第k行去异或下面所有M[i][j]不为0的行i，消去它们的第k个系数，这样就将原矩阵化成了上三角矩阵；最后一行只有一个未知数，这个未知数就已经求出来了，用它跟上面所有含有这个未知数的方程异或，就小觑了所有的着个未知数，此时倒数第二行也只有一个未知数，它就被求出来了，用这样的方法可以自下而上求出所有未知数。

示例程序：t3.cpp
(HAOI 2005  t3)

昨天晚上快睡的时候收到了伊朗同学的邮件，他告诉了我他的MSN，果然今天下午我就在线上见到了他。

我问他的第一个问题就是“Are you a boy or a girl?”回答是不出所料的“boy”。然后我又问了他一些关于伊朗的问题，包括猫让我问的“Do you live Demoncrazy and Freedom?” （回答是so so……）我问他对China的印象，他说“a country with more than 1000000000 people”，然后就nothing else了。他问我关于伊朗同样的问题，我先恭维了一些（比如说“sea of oil”，回答是“sure”）以后就说“girls with cloth covered their faces”，因为我在电视上看到的阿拉伯国家好像的确是这样的；结果他说“about girls your view is for 100 years ago”，汗一个……

他是伊朗IOI集训队的一员，但他也坦言说没有我强。另外，他们二十六人的集训队里有三个MM呢！过两天我一定设法搞到一个伊朗MM的联系方式。原来伊朗MM仅仅是用布遮住头发而已。（不过想想那小子从小就没在现实中见过任何MM的头发也挺悲哀的。）

他课余时间喜欢play football，还喜欢伊朗的传统音乐（这个地址，我是实在欣赏不了）。

最后呢，我将最近困扰我的一道题目跟伊朗同学讨论了一下。今天大致就这么多内容，等我要到伊朗MM的PP再来show。

另外，伊朗的Internet显然不怎么好。他一会儿跑到MSN上说他的Yahoo坏了，一会儿跑到Yahoo上说他的MSN坏了，要不就是消失好几分钟然后说刚刚Internet坏了……他的Internet大约15分钟掉线一次……汗……

一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了。

求凸包有很多方法，不过最适合OI的估计还是Graham’s Scan这个方法了。它的大致方法是这样的： 首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极角（atan2(y-y0,x-x0)），并按照极角对这些点排序，前述基准点在最前面，设这些点为P[0]..P[n-1]；建立一个栈，初始时P[0]、P[1]、P[2]进栈，对于P[3..n-1]的每个点，若栈顶的两个点与它不构成“向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凸包了。

如何判断A、B、C构成的关系不是向左转呢？如果b-a与c-a的叉乘小于0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x。

上面的这个Graham的实现比我原来按照USACO里的课文写得简单多了，主要是它通过简单的预处理保证了P[0]、P[1]以及P[n-1]肯定是凸包里的点，这样就可以避免在凸包“绕回来”的时候繁杂的处理。

示例程序：fc.cpp
(USACO Training: fc)

昨天在我的另一个博客“DD的USACO征程”里看到了一个人的留言，留言是英语，大意是说那道题我的程序看不明白，希望我能给他发邮件讲解一下。我没在意，就发邮件给他大致说了一下。结果今早看到邮箱里有这样一封回复：

can you say it in english.
I am not chinese.
I am iranian.
thanks.

这太神奇了！伊朗同学也能看到我的blog？（后来我发现，在Google里搜索“USACO”，我的blog是很靠前的。）于是我拿出做英语试卷最后一道题的劲头给伊朗同学写了一封热情洋溢的回信，不仅告诉他（不会是“她”吧……）我对那道题的思路，还告诉他我从未在Internet上遇到过foreign friends，还写了一堆什么“I am very interested in the culture of your nation”，还告诉了他我的MSN。看看能不能和这个伊朗同学有进一步的交流。

记得Yang Zhe同学也曾告诉过我类似事件，我忘了是哪国的，反正是直接找到了MSN上向他问题，当时我还调笑他说“看来你已经有国际声誉了”，没想到我也会遇到……我只能说：OI无国界，C++ Language无国界。

事态仍在进行中，请不断关注我关于伊朗同学的最新报道。

矩阵乘法的定义很简单，比如说S=X*Y，那么就有S[i][j]=sum(X[i][k]*Y[k][j])。

利用矩阵乘法，可以解决一类DP问题。这一类问题的特点是：状态的某一维特别巨大，但是沿着这一维的决策过程是完全重复或者循环的。

比如说这个问题：一个有向图，沿着每条边走过去的时间都为1，问时刻0在在S点，时刻t在T点共有多少种不同的路径（不一定是简单路径）。

很容易想到的思路是DP，设v[i][j]表示时间i时在v顶点的路径数，边界条件是v[0][S]=1，只需求解v[t][T]即可。由于v[i]之与v[i-1]有关，可以很方便地将状态的储存空间压缩从O(nt)为O(n)，但是如果t特别大（比如说1e9）O(n^2*t)的时间还是要TLE的（最一般的状态转移是需要n^2时间的）。这时就可以使用矩阵乘法来优化。

将v[i]这个一维数组想成一个1*n的矩阵，我们会发现v[i+1]=v[i]*M，其中M是有向图的n x n的邻接矩阵。为什么是这样不大好单纯用语言解释，如果你深刻理解了矩阵乘法的意义，再考虑一下前面的问题的状态转移的过程就会明白。所以说我们要求解的v[t]其实就是v[0]*M*M*M…（t个M）。根据矩阵乘法的结合律，它也就是v[0]*M^t。而M^t这个东西是可以利用类似于快速幂取模的方法在O(log t)的时间内计算出来的（把矩阵乘法当作元运算）。这样我们就把上述时间复杂度变成了O(log t * n^3)，在n不太大，而t可能非常大时，这是非常好使的优化。

更多时候问题没有这么简单，比如说图的顶点可能按照某周期禁止到达啊（ZJOI 2005 day1 swamp），也就是说图的邻接矩阵会随着t而变化。但只要它是周期性的，还是可以直接使用矩阵来优化。只是实现时要注意矩阵乘法是不满足交换律的。

示例程序：swamp.cpp
(ZJOI 2005 day1 swamp)

并查集，就是Union-Find Set，也称不相交集合 (Disjoint Set)。这在数据结构中本是很简单的一种东西。当然，我是指算法的实现简单，而非其理论分析简单。但我今天还是要扯一下这个，因为我突然发现我这几天写的并查集都是错的，今天做题时才发现。所以还是把这个很简单的数据结构总结一下。

正如它的名字揭示的，并查集的基本操作有两个：Union和Find。其中Find(x)返回元素x所在的集合的编号，Union(i,j)将i与j所在的集合合并，也就是说在此之后对它们中的每一个调用Find的返回值必须是一样的。

实现时采用父亲表示法的树结构，保证所有在一个集合里的元素都在一棵树内，集合的代表元素就是根。初始时所有节点的父节点都是自身，查找时只须沿着向上的路径查找即可；如果要将两棵树合并只须将其中一棵的根的父节点设为另一棵树的根即可。最主要的优化是所谓路径压缩。简言之，就是在Find的实现时并不简单的return find(U[x]); 而是 return U[x]=find(U[x]); 这样就将当前节点到根的路径上的所有节点的父亲都设为了根，将原本可能比较长的路径“压缩”了。当然这是递归的实现，非递归的话需要沿路径走两次，第一次找到根，第二次再改变。

union操作更简单，只是U[find(x)]=find(y);一句而已。我前两天写Tarjan算法时把这一句错写成U[x]=find(y)，竟然也AC了……汗……不过今天做另一道需要并查集的题目就没那么幸运了。

路径压缩的并查集n个操作的序列的均摊复杂度为O(nα(n))，其中 α是阿柯曼函数的一个反函数，增长极慢，在可以想象的n的范围内不超过5，故可视为常数。

并查集的一般用途就是用来维护某种具有自反、对称、传递性质的关系的等价类。

实现并查集只需要一个数组和两个分别是两行和一行的函数，故不再发示例代码了。

这两天里又学了好几个新的算法，做了好几套题目，还是蛮充实的呢。

Hungary算法现在已经可以熟练快速地一次写对了，对它的理解也有更深入哦。

RMQ问题掌握了线段树和ST算法两种方法，应该是够用啦，不过ST还没到能够一次写对的程度。

KMP算法虽然早就知道是第一次写，呵呵，还抄袭了libg++。反正就那几行，大不了打印了背下来嘛。

LCA问题的Tarjan算法基本上掌握了，不过还是要找时间再看看。

图的割顶与桥已经理解的比较深刻了，其实只要记住Low的定义以及充要条件就好了啊。

又做了好几套题了，有必要总结一下。

写了浙江2006二试。题真的很难呢，得了200左右/400。kaj不用说，xn就不多研究了，polygon和gen（特别是前者）有空还是争取能写满分。

写了好几套USACO月赛。jan07gold里面的lineupg就是RMQ；psolve是一道较难的DP，有点像多进程，应该用心体会；schul就不研究了……nov06silver里面badhair一次写对的，自己设计的借鉴了最小前缀和的算法，与标准答案不太相同哦；bigsq只要想到了枚举对角线，加上我的无敌的剪枝，还是相当容易的，第一次错了几个，原因是没有考虑到某些两个点是不能作为合法的对角线的；rndnum是组合数学，自己调试了半天，最后还是出了一点点低级错误挂两个点，不过这类题目应该已经比较熟练了。nov06gold里的plank就是一合并果子，太水了一次AC；block是第二最短路，不知道在哪里听来的可以用SPFA解，自己写了一下一次AC了呢，看来我对SPFA的理解已经比较深入了；cowfood初看时不知道怎么做，看了analysis才知道是状态压缩的DP，应该由“放了以后四周就不能放”这个条件联想到，照着标程画瓢了一个程序，还要仔细体会。

接下来几天一是要做真题，二是要做USACO月赛，均摊每天不少于两套嘛。最近没怎么做搜索题好像，要找一两倒做做，特别是广搜。好像想不到什么需要学的新算法了，树状数组是需要再写写的。

图的割顶即删掉之后图就不连通的顶点，桥即删掉之后图就不连通的边。

求图的割顶与桥都需要对图的DFS进行简单扩充，即在DFS过程中求出每个顶点的Low值，Low的定义是：

Low[v]=min{
　　Num[v],
　　Num[w], ( link[v][w] && Num[w] < Num[v] && Par[v]!=w ， 后向边)
　　Low[w], ( link[v][w] && Num[w] > Num[v] ，树边)
}

其中Num[v]表示每次DFS到v顶点时标记的时间戳，Par[v]是DFS树中v的父节点。

(v,w)是桥当且仅当Num[v]<Low[w]。

v是割顶当且仅当v不是根且Num[v]<=Low[w]或v是根且DFS树中v有不止一个的子节点。

（以上Par[w]==v）

示例程序（求图的桥）：
zju2588.cpp