博主在使用 RMBP 一段时间后得到了大多数人对于 Apple 产品的体验感。的确很好用，这一点主要是针对 linux 来说的。但是呢，工欲善其事，必先利其器。单纯的 OS X 能力毕竟有限，无论你是设计师还是Coder同样要懂得配置利于自己的环境。我并不是设计师，只简单聊聊我自己作为coder的环境体验：
TAOMP第一章题目选解
问题概述1
习题4：假设你是最近被捕的P个囚犯之一。监狱长是个疯狂的计算机科学家，他给出了以下启示：
- 你们今天可以在一起商定一个策略，但是从今天以后，你们将会被隔开关在不同的房间，相互间无法再进行交流。
- 我们建造了一种“开关房间”，里面有一个灯开关，这个开关只能为开和关，且没有和任何东西相连。
- 我将不时地从你们中间随机选择一位到“开关房间”里来。这名囚犯可以拨动开关（从开到关、或相反），也可保持开关的状态不变。其他人这时都不能进入房间。
- 每一名囚犯都将任意多次地进入开关房间。更确切地说，对于任意的N，你们中得每个人最终都至少进入这个房间N次。
- 任何时刻，任意一名囚犯都可以宣布：“我们所有的人都已经至少到过开关房间一次了。”如果该断言是对的，我将释放你们。如果错了，我就把你们全都送去喂鳄鱼。谨慎抉择吧！
CPU缓存命中优化之循环交换
USACO 6.1.2 Vans
题目解答
找规律。第一张图和第二张图其实已经暗示了这道题目的潜在规律。注意到从一个第一行的点横向出发再回到这个点只有从这个点下面的点回来。定义F[i]表示从前i列中第i列的第2个点到第1个点共有多少合法路径，根据这个定义F[n]即为所求。G[i]表示前i列中第i列的第1个点到第4个点共有多少路径。因此可以推出F[i] = F[i-1] + G[i-1] (画图找规律)。
下面我们仔细观察这两个方程的定义，从而化简方程，如下图：
G[i] = F[i-1] * 2 + G[i-2] + G4[i] (1)
G4[i] = F[i-2] * 2 + G4[i-1] (2)
由(1)化简(2)式得到：G4[i] = G[i-1] - G1[i-1] - G2[i-1] - G3[i-1] + F[i-2] * 2 = G[i-1] - G[i-3]
所以G[i] = F[i-1]*2 + G[i-1] + G[i-2] - G[i-3] (3)
又由F[i] - F[i-1] = G[i-1] (4)
最终我们得到 F[n] = 2F[n-1] + 2F[n-2] - 2F[n-3] + F[n-4] (n>=5)
初始值：F[1] = 0; F[2] = 2; F[3] = 4; F[4] = 12。
USACO 5.5.1 Picture
题目解答
其实边界需要统计的是上下左右4个方向没有被覆盖到的边长的总和。这个问题的难点是怎样使得需要判断检索重叠的复杂度尽量小，我们先简化问题，假设所有矩形都是A情况的，也就是宽度都一样并且垂直排列，这样的话我们就将矩形的情况分为不相交，交叠，包含几种情况。先从横向的边开始看，如图所示，如果只考虑蓝色和浅绿色这两个矩形因为没有任何与其相交的其他矩形，直接统计横向边长，然而交叠和包含要怎么办呢。如图红色和黄色的矩形有橙色的部分，那么也就是说我们只用统计红色的上边长和黄色的下边长了。而浅蓝色和紫色的关系也是类似只用统计紫色的两个边。
从这里我们得到一些启发，假设所有边长都是1个单位长度，显然我们只是统计一个覆盖域的上下两个边界，那么这从抽象意义上很类似括号匹配的问题，下面的这些矩形块可以抽象成()()(())(())注意观察它们的特点，可以发现跟真实的配对没有关系，也就是()()(())(())，我们用一个栈依次压入括号，每次出现()的配对就出栈。然后要统计这些，当压入后(且栈只有这一个元素)时计数器加一，当弹出元素后栈空时计数器加一。这样我们就相当于统计出了所有的该纳入计算的边界，由这个思考点出发，我们要对所有的矩形边进行离散化，同时要区别上下边界，抽象成“左右括号”。这个时候有个细节，对于横向边我们按纵标排序，如果纵标一样谁在前？其实这也是交叠的一种情况，如果纵标一样，先要把左括号排在前，也就是如果我们按纵标由小到大排，下边界应在前，不然会使得周长变大。
具体实现时我们看B图，因为配对不只是一种情况，而且坐标很大，这时候我们可以使用线段树来辅助数据结构的部分，需要横着纵着处理两次。也就是对于类似括号匹配中栈的操作，真正实现用的是线段树。
这样本问题就解决了，算法是离散化+线段树。这个算法的正确性是我们已经排好了序，而且每个方向的边都是成对出现的。
USACO 5.4.4 Betsy
题目解答
问题的本质是求所有的可能的哈密顿路径的情况，可以使用DFS+剪枝求解。
本问题的考点也是剪枝，有以下两种情况：
孤立区域的形成:
如图所示，孤立区域也就是被划分成了两个域的情况，这个时候无论走哪个区域另一个区域都无法访问，那么一个剪枝就可以是判断当前有无孤立区域的形成，这个产生条件比较多，有一种基本情况就是如果当前点上下（包括边界）被访问过了，而左右没被访问则必产生孤立，另一个情况则正好相反。理由是当前点上下如果被访问了，而这两个访问过的点都是由起点走过来的，也就是都连通到起点，意义就是这两个点本身是连通的。我们不能穿过被访问过的路径走交叉路线，所以说这样无论走哪里都会被包住再也出不来了。这是一个情况。进入死胡同:
我们考虑类似围棋中的气，每个格子不需要一进一出，也就是至少有两个度，如果只有一个度则走进去后就再也出不来了，我们不必要碰到度为一的点再去回溯。而是一开始就避免度为一的点产生。剪枝方式是：除去起点和终点外如果当前点的周围未被访问的格子中有度为一的点(也就是连通到另外一个未被访问的格子)，那么这个点必须要访问，理由是这个点如果被访问，就相当于他的一个入度被利用了，如果不访问则就浪费掉了。浪费之后他的度为1，以后则会只进不出。因此必须要访问，所以可以推出另一个关于度的剪枝，如果存在两个以上的度为1的点则回溯，因为不能两个同时都选，选了一个，另一个必然是死胡同。
转：俄罗斯TC三冠王ACM顶尖选手Petr感悟
Do not spend all your time on training or studying - this way you will probably become very exhausted and unwilling to compete more. Whatever you do - have fun. Once you find programming is no fun anymore – drop it. Play soccer, find a girlfriend, study something not related to programming, just live a life - programming contests are only programming contests, and nothing more. Don’t let them become your life - for your life is much more interesting and colorful.
2012新年前最后的文章
这里说的新年特指中国农历龙年，明天就是除夕夜，所以在此说说。很久不更新blog是因为的确没什么好更新的。我喜欢将自己的研究项目，解题报告发到博客上，可是，上了大学，这方面的事情少很多。要说研究还是有的，但是直观价值不大。我不想总结这一学期，ms是小小的延续了一下高中的状态。可是愈到期末愈好了。所以可以预见到下个学期会好很多。
要说我特别想说的就是，在某些方面有预见性的进步。对于个人能力，潜力我都表示无所顾忌。也不需要，不必要。能开心的“娱乐”、“玩”就很好了（想不到有什么其他更好的词了，如果想到我一定会写上的）。然后呢，说说成果，这个学期积累多成果少。这种状态就很不错，至少我比较满意了，比高中强。高中嘛积累不算少，成果也不多，可就是不及大学。