计算机学院 李乐强
解题报告
SOJ1002：大数加法：利用字符串来存储加数及结果。在做加的过程中模拟人作加法的过程，得到结果。
SOJ1003：大数乘法：利用长整型数组来进行存储。做乘法时，用乘数一位一位地乘以被乘数，结果累加存到结果数组地相应位中。
SOJ1005：移动卡片：当读入并存储好每一堆卡片的数量后，从左向右作扫描（移动次数count置0），并遵从以下规则：
（1）：当当前堆的卡片数是平均数时继续扫描，否则，用start指针指向该堆，使计数指针j继续向下扫描。
（2）：当start和计数指针j之间的卡片和等于算法完成后应有的数目时，使start＝j＋1（指向下一堆），count＋＝j－start；如大于，则将多余卡片移入下一堆后，使start＝j＋1，count＋＝j－start＋1；如小于，则循环执行本步。
（3）：打印结果。
SOJ1006：建立密码表，查表即可。
SOJ1009：钱的找法：建立二维表，以哈西存储的方式来存储某种数量的钱有多少种找法，用递推的方式填好该表，在读入数据后查表即可。
SOJ1010：模拟机器人行走：用二维数组存储地图，用变量currentx，currenty来记录机器人当前坐标，currentd记录方向。按输入的指令串进行模拟，并得出结果。
SOJ1013：帽中猫：根据给出的数据，利用等比数列求某一元素的公式，可求N，再利用求和公式得相应结果。（不干活儿的猫个数，及所有猫的高度和）
SOJ1018：模拟大师：模拟PinBall的玩儿法。根据要求，求出最终得分。
SOJ1019：TSP：典型动规。用数组记录每一步的最优决策序列（多个），下一步的决策序列以之为基础生成，最终得出一个最优解。（就本题而言，是最短路径）
SOJ1020：与1010同
SOJ1023：素数：先生成1～1000的素数表，再跟据输入既要求查表即可。
SOJ1025：大数连加：与1002思想同。
SOJ1027：LOTTO：找几个数字的不同组合，循环即可。
SOJ1035：能源危机：用约瑟夫算法，循环找最小符合要求间隔。
SOJ1036：Dole Queue：用约瑟夫算法。
SOJ1039：贪心的送礼者：读入数据，边读边计算，最终得结果。
SOJ1051：回文：建立字符表，安要求匹配即可。
SOJ1052: MASH: 类似于约瑟夫算法，只是每次数的个数不同。
SOJ1059: 圆周率：求出一组数中互质的数有几对，然后根据题意导出一个公式，可求得Pi。
SOJ1067：Word-Search: 将字母矩阵和要找的自串读入，然后在字母矩阵中匹配查找。
SOJ1071：巴比伦塔：利用动态规划的思想。保持两个数组来记录前一状态和当前要求的状态。再根据题意，不断的将Block 加在前一状态所表示的tower 上，使之成为所有在该层数上最终以此block为顶的 tower中高度最大的，并记录其状态。不断执行（即更新状态），直到所有的状态不能再改变为止，此时找出所有记录中高度最大的，即为最优解。
SOJ1072: 外接圆周长：三角形的外接圆圆心是三角形任意两边的中垂线的交点。应用相关平面几何公式，可求得圆心及半径，周长也可求出。
SOJ1073：Knight Moves: 用二位数组表示棋盘，从给定的初始位置开始，对棋盘进行广度优先遍历，当当前节点为终点时结束遍历，遍历层数即为所求步数。
SOJ1074：实际上是大数减法问题。当结果为负或零时，输出指定语句，否则输出结果。
SOJ1075: 此题可以用拓扑排序思想，建立不同apple 间的顺序关系，进行拓扑排序即可。
SOJ1076：解此题可用字符串的有关方法（匹配），计数即可。
SOJ1077：解此题可利用二维数组存储“数据库”中的数据，再对应于每个用户“请求”在每一个数据记录中查找，若找到，则出现次数加一；否则不做操作。再转到下一记录继续查找。最后得出结果。
SOJ1078：解此题，先读入所有“事件”的时间段，然后进行扫描：总是将没扫描过的，且开始时间在前一选定事件之后，且结束最早的事件选定，做标记，然后计数加一。最终不能再按上述条件选定时为止。计数结果即为答案。
SOJ1080：这是一道模拟题，在读入每关的数据后，按题设条件对每关进行模拟，并根据剩余生命值对能否过关作出判断。
SOJ1120: (01串压缩编码)按题意模拟编码及转换过程即可。
SOJ1156：（Complete the sequence）是一个关于数列的问题。算法的原理是由于任意阶数列的公差序列的阶数比原数列小1。通过不断地求差序列，可以得到一个常数列。具体方法是建立二维表，将数列的公差以倒三角的形式存放，直到某一行所有差为常数为止。然后，从末行起自下而上累加当前最末的数，加到首行即为答案。若要求多个数，则重复上述累加过程。
SOJ1106：（Dweep）此题可用广度搜索+剪枝。先读入地图，从起始点开始广搜（将起始点入队，访问时出队），并根据题的条件来更新地图上遍历到的每一点的深度（初始均为极大值），方法是：如果当前得到的遍历深度严格小于原来记录的深度，则更改之，并将改点入队；否则，跳过该点，读取对中下一点，直到读到队列空为止。在这一过程中，不断的记录到某一点的“get wet”的次数，如该点以前未访问或其“get wet”的次数严格大于当前得到的次数，则更新之。最后以次数最小为结果。如无解，则输出-1。
SOJ1092：（欧几里得算法）根据题意，模拟推导过程可得答案。
SOJ1115：（阶乘）处理尾数，并注意不要超界即可。
SOJ1118：（上车人数）根据题意，列出求解方程，并模拟上下车过程，求出方程参数，解方程即可。
SOJ1150：（Labyrinth）读入地图，从一个起点（不是中间某一点）开始深度搜索，到末点后，在反过来深度搜索一次，搜索深度即为解。
SOJ1116：（回文数）模拟转换及加法过程，判断并记录步数即可。
SOJ1114：（数字三角）解法与TSP 同（动规）。
SOJ1151：（Piggy-Bank）建立表，并按题意，更新表项即可。（运用动规的思想）
SOJ1084：（滑雪比赛）将二维地图按高度排序，降成一维表，利用动规的方法填表即可。
SOJ1081: (SARS)模拟Conway 的Game of Life。
SOJ1082：此题可用递归，记录合法情况的次数即可。
gmail.com
|