程序道

106 - Fermat vs. Pythagoras

冯博文 — Tue, 19 Jan 2010 21:41:00 +0800

此题实际上是求本原勾股数组（Primitive Pythagorean Triple, PPT）。稍用一点数论的经典知识就可以得到非常高效的解法。我的程序排名18，头一次进第一页：）

105 - The Skyline Problem

冯博文 — Tue, 05 Jan 2010 14:53:00 +0800

此题比较简单，直接扫描线法处理就可以了。先把每个楼的三元组 (left, height, right) 转化为两个事件：left 转化为进入事件，right 转化为离开事件。然后对所有的事件进行排序后从左向右进行扫描处理：一个楼进入扫描线：加入到“活动楼列表”，如果其 height > currentSkylineHeight，则修改 currentSkylineHeight 为 height 一个楼离开扫描线：从“活动楼列表”删除之，如果其 height == currentSkylineHeight，则在“活动楼列表”中找到最高的一个，若最高的那一个的 height’

10033 - Interpreter

冯博文 — Tue, 05 Jan 2010 00:21:00 +0800

简单模拟题，主要就是“地址”，“地址的地址”，“地址里的数据”这几个概念别搞乱脑子就好。C/C++老手应该闭着眼睛也能写出正确的程序来：）

10267 - Graphical Editor

冯博文 — Mon, 04 Jan 2010 23:49:00 +0800

此题其实是一个简单的模拟题，但经过多次WA后，我终于写对了其中的floodfill算法，要写一个正确的floodFill算法要非常小心。 Floodfill 一般过程就是：将起始点染色，并压入队尾从队列中取出一点 p:(x,y) 检测 p 周围4点（或是8点，取决于题目要求是八向还是四向），并将那些可以到达的点染色，并压入队尾循环2~3直到队空我在实现时，出现了几个问题：每个点要染色后再入队。如果把点入队了但没染色，会导致一个点被从多个方向检测到，从而多次入队。这会直接导致TLE。最重要的一点是：一开始要检测起始点原始颜色与新染的颜色是否一样，如果一样就不做floodfill，否则死循环，TLE。边界检查，超出边界不要再继续，不然会越界。在四周加一圈哨兵会大大简化算法实现。

UVa Online Judge - Volume CII 题目和解答索引

冯博文 — Mon, 04 Jan 2010 23:48:00 +0800

UVa Online Judge - Volume CII 题目和解答索引。前面为原题链接，后面为我的解答链接。

104 - Arbitrage

冯博文 — Mon, 04 Jan 2010 23:20:00 +0800

这道题费了我相当的时间。题目要求找到一个profit > 1.01的套汇序列，但有多个的情况时，要求输出序列最短的一条。开始觉得很像Floyd-Warshall 算法，但试着开写了才发现，对于怎么控制得到最短序列非常有玄机。最后还是在UVa的论坛里找到了一个好帖，给出了一个 O(n4) 的算法，并给了非常详细的解释。原帖在这里，请看 gits 的回帖。用 profit(i, j, step) 存放“由 i 经过 step 步套汇得到 j 可以得到的最大profit值”。则有以下递推式： profit(i, j, step) = profit(i, k, step-1) * profit(k, j, 1); // 当profit(i, k, step-1) * profit(k, j, 1) > profit(i, j, step) 递推初始值：profit(i, i, 1) = 1.0 另外，使用 Floyd-Warshall 算法往往要记录回溯路径（除非不需要得到的序列）。这里使

挑战编程程序设计竞赛训练手册（Programming Challenges）

冯博文 — Mon, 04 Jan 2010 17:12:00 +0800

前一阵子到手这本书，一翻开就合不上了，发现书的内容编排非常紧凑，讲解清晰。每一章内容不多，可以一口气读完，每章后面的习题又是从UVa Online Judge上精心挑选的8个题目，自己可以写程序提交验证。可以说是非常适合自学的一本书，强烈推荐！这本是一本小册子，但看这本书一定要“把书看厚”。每一章的知识点其实都是很大一堆内容。从这一本小书出发，可以引出算法、数据结构、图论、数论、离散数学、组合数学、概率论、线性代数等内容。可以说，想要看完这本书很快，但想要真正学通这本书很难。我看完了第一遍，边看边买书，已经买了一堆书了，准备先看一阵子相关内容，把知识点重温一下，到时再回头再看几遍这书。

706 - LCD-Display

冯博文 — Mon, 04 Jan 2010 16:44:00 +0800

简单模拟题，设计一个好的数据结构来方便的表达每个数字的输出方式。我的不是最好的，后来还看到 Kaipeng Liu 的方法，写起来更利索一些;)

UVa Online Judge - Volume VII 题目和解答索引

冯博文 — Mon, 04 Jan 2010 16:38:00 +0800

UVa Online Judge - Volume VII 题目和解答索引。前面为原题链接，后面为我的解答链接。

10137 - The Trip

冯博文 — Mon, 04 Jan 2010 16:18:00 +0800

此题涉及浮点数运算，所以要格外小心。题目大意是要求出最小的匀钱方案，精确到分。因此，求出平均数后，用多的减平均数得到的值，和用平均数减少的得到的值可能会有不同。取其中较小的就可以了。特殊情况在于算出的较小的值可能是0，那么就得用较大的值了。