soj题目报告(编辑修改稿)

soj题目报告(编辑修改稿)内容摘要：

.................................... 25 1121 最短路径★ ........................................................................................................... 25 1123 球钟 ...................................................................................................................... 25 1124 回文数 II .............................................................................................................. 26 1125 恺撒的规划 ........................................................................................................... 26 1128 控制棋 .................................................................................................................. 26 1133 Billiard★ ................................................................................................................ 26 1134 One Person The Price is Right★ ............................................................................. 26 1136 Factoring Large Numbers .......................................................................................... 27 1138 Wall ....................................................................................................................... 27 1139 Flip Game★ ........................................................................................................... 27 1140 Buffer Manager ....................................................................................................... 27 1142 Binary Search .......................................................................................................... 27 1145 Disk Tree★ ............................................................................................................. 27 1147 Equipment Box ........................................................................................................ 28 1153 Play on Words ......................................................................................................... 28 1154 Simple Arithmetics ................................................................................................... 28 1162 IKeyboard★★ ....................................................................................................... 28 1163 Cash Machine .......................................................................................................... 29 1167 Game★★ ............................................................................................................... 29 1168 Manager ................................................................................................................. 30 1169 Networking ............................................................................................................. 31 1184 Symbolic Derivation................................................................................................. 31 1185 Rectangles............................................................................................................... 31 1189 P,MTHBGWB ......................................................................................................... 31 1197 Multiplication Puzzle................................................................................................ 31 1001 A + B Problem 几乎每个 Online Judge 的第一道题目都是这个（好像 UVA除外 ^_^）。 用于试验服务端环境的题目，主要考查 scanf 的用法。 1002~1004 Big integer calculation 主要考查高精度运算的知识 ，并没有太多的技术含量。 1005 Move cards★★ 首先要判断点数总和能否被堆数整除，如果不能，就没有必要进行下面的操作了。 由于队列两端的卡片只能移到相邻的一个方向，这样我们在进行卡片移动操作的 时候不得不考虑端点的情况，于是，程序变得不够统一，不统一的程序往往是没有通用性和不稳定的。 为了构造统一的程序，我只 考虑每个卡片堆右边的情况。 基于以上考虑，我将队列分为两个部分：一堆卡片与这堆卡片右边的部分。 显然，这里的“一堆卡片”不包括最右边的那堆。 表示如下 P R 分别表示 Pile Right 我定义 Average 为达到平衡的时候每堆卡片的张数，于是出现三种情况： 一、 Pile = Average，此时不需要动这堆卡片。 二、 Pile Average，此时需要将这堆卡片中比 Average 多的部分移走，由于 我只考虑向右的情况，所以 Pile 将 (Pile – Average)张卡片移给 Right（只能移给 Right 而不是Right + 1 或是其他是由规则决定的）。 三、 Pile Average, 此时需要从别的卡片中移一些卡片给 Pile，让 Pile = Average，显示，需要 (Average – Pile)张卡片。 这种情况与 [情况二 ]不一样，情况二只是把 Pile 多余的卡片分给右边，但 [情况三 ]也许需要将多堆卡片中多余的部分一起分为 Pile。 于是，当出现这种情况时，需要从 Pile 的右边开始搜索。 显然，对于张数 小于或等于 Average 的堆是不能够分卡片给 Pile 的，所以，需要从所有张数大于 Average的堆中分卡片给 Pile，直到 Pile 张数等于 Average，也就是说，搜索的最后一堆也许不会将所有的多余卡片分给 Pile。 由于我的操作是从左至右进行的，所以，当出现这种情况的时候，一定可以从 Pile的右边找到多余的卡片，使 Pile = Average。 重复考虑这三种情况，直到达到平衡为止。 1006 The Hardest Problem Ever 很简单的一道题，原理就是查密码表。 注意读入的时候不要用 scanf(“%s”, … )读入，用 gets。 另外就是注意输入数据的格式。 1007 Rubik39。 s Cube Solver 题目很简单，但程序很麻烦，主要操作在于写出魔方在各种操作下的变换，没有什么算法。 1008 Climbing Trees★ 给定一颗树，然后再给出两个结点，要求得到这两个结点的关系。 这个问题主要是基于树结构的操作，基本操作是先找出两个结点的最近的公共祖先，再根据两个结点与它们的公共祖先的关系来判断两个结点的关系。 这道题的关键在于找出两个结点的公共祖先，我用的方法是： 假设两个结点是 A和 B，先找出从根到 A的路径，再找到从根到 B的路径，再找到两条路径中离根最远的公共点即可。 两个结点一定会有公共祖先（至少是根）。 1009 Dollars★ “生成类”动态规划的题目。 从 0 元开始，不断地生成，直到生成到 元。 在实际操作的时候，先将浮点数乘以 100，转换为整数，这样再进行后面的运算便不会出现精度问题。 这道题在刚开始的时候会遇到精度问题，即在将读入的钱数乘以 100得到整数的时候会出现得到的结果 N % 5 = 1 或 N % 5 = 4 的问题。 在这道题里，我通过以下的方法避免此问题：判断 N是否能被 5 整除，如果不能，则考虑 N + 1 和 N – 1哪个能被 5 整除，则取哪个（ N + 1 和 N – 1 中只可能有一个被 5 整除）。 1010 Mutant Flatworld Explorers★ 模拟题。 关键在于理解题意：机器人在一个位置 fall off 之前，会在该位置留下标记，后面的机器人在走到该位置，如果下一条指令会导致它 fall off，它会忽略掉该指令。 注意，这里的 fall off 并不包含对方向的限制，也就是说，机器人留下的标记只是说明该位置有机器人 fall off 过，并没有记录是在哪个方向 fall off 的。 1011 The Skyline Problem 又是一道模拟题。 先按矩形的左坐标排序会简化程序的操作。 排序后，从最小的坐标开始扫描，发现高度变化，就记录下来，最后将这些“变化点”打印出来就行了。 1013 The Cat in the Hat★ 数学题。 为了叙述方面，我定义 Cat 帽子里的 Cat 为 ChildCat。 根据题意，每只 Cat 有 N 只 ChildCat， ChildCat 的高度为 Cat 的 1/(N+1)。 题目的输入告诉了 initial Cat 的高度和 worker cat 的数目，也就是说，告诉了最大 的那只猫的高度和最小的猫的数目。 基于 Cat 和 ChildCat 的高度、数量关系，假设所有的猫堆起来有 n 层，则有： (N + 1) ^ n = initial Cat 的高度 N ^ n = worker cat 的数目 搜索到第一个满足条件的 n 后，再进行以后的计算。 题目要求得出 nonworker cat 的数目和猫叠起来的高度。 得到 n 值以后，这两个值就很容易算了。 Nonworker cat 的数目就是 cat 的总数目 – worker cat 的数目（已经在输入中告诉了） 算猫叠起来的高度利用等比数列的求和公式就 行了。 1014 Maximum Sum 最大子矩阵和的问题，动态规划的的经典题目。 1015 History Grading★ 模拟 ＋ 最长公共子序列。 关键还是在于理解题意 ，也就是得分的两种情况：一种是数字相同，位置也相同；另。