题目概述

一天，鬼谷子随意从2~99中选取了两个数。他把这两个数的和告诉了庞涓， 把这两个数的乘积告诉了孙膑。孙膑和庞涓彼此不知到对方得到的数。第二天， 庞涓很有自信的对孙膑说：虽然我不知到这两个数是什么，但我知道你一定也不知道。随后，孙膑说： 那我知道了。庞涓说：那我也知道了。

Read More

博主在使用 RMBP 一段时间后得到了大多数人对于 Apple 产品的体验感。的确很好用，这一点主要是针对 linux 来说的。但是呢，工欲善其事，必先利其器。单纯的 OS X 能力毕竟有限，无论你是设计师还是Coder同样要懂得配置利于自己的环境。我并不是设计师，只简单聊聊我自己作为coder的环境体验：

Read More

问题概述1

习题4：假设你是最近被捕的P个囚犯之一。监狱长是个疯狂的计算机科学家，他给出了以下启示：

1. 你们今天可以在一起商定一个策略，但是从今天以后，你们将会被隔开关在不同的房间，相互间无法再进行交流。
2. 我们建造了一种“开关房间”，里面有一个灯开关，这个开关只能为开和关，且没有和任何东西相连。
3. 我将不时地从你们中间随机选择一位到“开关房间”里来。这名囚犯可以拨动开关（从开到关、或相反），也可保持开关的状态不变。其他人这时都不能进入房间。
4. 每一名囚犯都将任意多次地进入开关房间。更确切地说，对于任意的N，你们中得每个人最终都至少进入这个房间N次。
5. 任何时刻，任意一名囚犯都可以宣布：“我们所有的人都已经至少到过开关房间一次了。”如果该断言是对的，我将释放你们。如果错了，我就把你们全都送去喂鳄鱼。谨慎抉择吧！

   Read More

概述

这是一道来自《多处理器编程的艺术》(TAOMP)的题目：习题222：

考虑一个具有16个缓存块的直接映射高速缓存，索引为0~15，每个缓存块包含32个字。考虑一个32x32的二维字数组a。该数组在内存中被排列为a[0,0]的下一个元素时a[0,1]，以此类推。假设该高速缓存初始为空，但a[0,0]被映射到0号缓存块的第一个字。(注意字与字节的不同之处)

Read More

引论

我觉得这个话题说大不大，说小不小。引发我思考的根源是无意中看到的一篇知乎上的讨论，有人推荐酷壳中的一篇相关的文章可以参考。对于他人的回答我不做过多评论，怎么看待就见仁见智了。回过头说话，无上心法终究是谁提出的不太清楚，但是来源于武林这是八九不离十。武林中的武功修为与现在大多数技术圈的修炼异曲同工，都是需要一定的积累方可成就，怎么去积累就有怎样的成就。也会延伸出诸多的领域，就说计算机科学无外乎以下几类(参考Wiki)：

• 理论计算机科学
  • 计算理论
  • 算法与数据结构
  • 程序设计语言理论
  • 信息与编码
  • 并发与分布式系统
  • 数据库与检索
  • 形式化方法

    Read More

维护自己的日志是一个很有意思的活动，我第一次接触个人独立Blog是在高三的的下学期，因为大学有了着落，借此机会抛弃掉以前的什么XX空间，就把Blog搬到了 WordPress 上，还为此买了虚拟主机和域名（对于个人网站来说备案真是一件既麻烦又浪费时间的事儿）。但是呢，移植完文章后的很长一段时间都没有好好更新，域名到期后就关闭掉那个旧的Blog了。

Read More

题目解答

找规律。第一张图和第二张图其实已经暗示了这道题目的潜在规律。注意到从一个第一行的点横向出发再回到这个点只有从这个点下面的点回来。定义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。

Read More

题目解答

其实边界需要统计的是上下左右4个方向没有被覆盖到的边长的总和。这个问题的难点是怎样使得需要判断检索重叠的复杂度尽量小，我们先简化问题，假设所有矩形都是A情况的，也就是宽度都一样并且垂直排列，这样的话我们就将矩形的情况分为不相交，交叠，包含几种情况。先从横向的边开始看，如图所示，如果只考虑蓝色和浅绿色这两个矩形因为没有任何与其相交的其他矩形，直接统计横向边长，然而交叠和包含要怎么办呢。如图红色和黄色的矩形有橙色的部分，那么也就是说我们只用统计红色的上边长和黄色的下边长了。而浅蓝色和紫色的关系也是类似只用统计紫色的两个边。

从这里我们得到一些启发，假设所有边长都是1个单位长度，显然我们只是统计一个覆盖域的上下两个边界，那么这从抽象意义上很类似括号匹配的问题，下面的这些矩形块可以抽象成()()(())(())注意观察它们的特点，可以发现跟真实的配对没有关系，也就是()()(())(())，我们用一个栈依次压入括号，每次出现()的配对就出栈。然后要统计这些，当压入后(且栈只有这一个元素)时计数器加一，当弹出元素后栈空时计数器加一。这样我们就相当于统计出了所有的该纳入计算的边界，由这个思考点出发，我们要对所有的矩形边进行离散化，同时要区别上下边界，抽象成“左右括号”。这个时候有个细节，对于横向边我们按纵标排序，如果纵标一样谁在前？其实这也是交叠的一种情况，如果纵标一样，先要把左括号排在前，也就是如果我们按纵标由小到大排，下边界应在前，不然会使得周长变大。

具体实现时我们看B图，因为配对不只是一种情况，而且坐标很大，这时候我们可以使用线段树来辅助数据结构的部分，需要横着纵着处理两次。也就是对于类似括号匹配中栈的操作，真正实现用的是线段树。

这样本问题就解决了，算法是离散化+线段树。这个算法的正确性是我们已经排好了序，而且每个方向的边都是成对出现的。

Read More

题目解答

问题的本质是求所有的可能的哈密顿路径的情况，可以使用DFS+剪枝求解。
本问题的考点也是剪枝，有以下两种情况：

1. 孤立区域的形成:
   如图所示，孤立区域也就是被划分成了两个域的情况，这个时候无论走哪个区域另一个区域都无法访问，那么一个剪枝就可以是判断当前有无孤立区域的形成，这个产生条件比较多，有一种基本情况就是如果当前点上下（包括边界）被访问过了，而左右没被访问则必产生孤立，另一个情况则正好相反。理由是当前点上下如果被访问了，而这两个访问过的点都是由起点走过来的，也就是都连通到起点，意义就是这两个点本身是连通的。我们不能穿过被访问过的路径走交叉路线，所以说这样无论走哪里都会被包住再也出不来了。这是一个情况。

2. 进入死胡同:
   我们考虑类似围棋中的气，每个格子不需要一进一出，也就是至少有两个度，如果只有一个度则走进去后就再也出不来了，我们不必要碰到度为一的点再去回溯。而是一开始就避免度为一的点产生。剪枝方式是：除去起点和终点外如果当前点的周围未被访问的格子中有度为一的点(也就是连通到另外一个未被访问的格子)，那么这个点必须要访问，理由是这个点如果被访问，就相当于他的一个入度被利用了，如果不访问则就浪费掉了。浪费之后他的度为1，以后则会只进不出。因此必须要访问，所以可以推出另一个关于度的剪枝，如果存在两个以上的度为1的点则回溯，因为不能两个同时都选，选了一个，另一个必然是死胡同。

Read More

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.