[Soj]解题报告

Soj解题报告

           Liulike

           2003年8月

SOJ1147              Equipment Box:

题目类型  简单的计算几何

总结      该题不但要考虑内部矩形和外部矩形平行的情况，而且要考虑内部矩形内接于外部的情形．然后用简单的三角函数计算即可。注意计算前限定一下长和宽。

SOJ1148              Secret Code：  

题目类型  一般模拟

总结      该题模拟复数的除法，注意复数能够整除的条件是除得的商的实部和虚部均为整数。

SOJ1149              Labyrinth：  

题目类型  图论 ＋ 深度优先搜索

总结      该题用到一个结论： 在一棵树中构造一条最长路径的方法如下，在树中任意选择一个结点，找出与它距离最远的叶节点，然后找与该叶节点距离最远的叶节点，其距离就是树中最长路径的长度。算法的实现方法用两次深度优先搜索即可。

SOJ1150              piggy-bank: 

题目类型  动态规划

总结      该题是比较常见的动规，利用已经生成的货币来递推出新的货币。可以用一个数组来标记已经生成的货币，同时用另一数组来存储已经生成的货币，可以达到优化的目的。

SOJ1152              Lifting the Stone

题目类型  简单的计算几何

总结      该题是已知一个多边形，求它的重心。由于输入的点本身是有序的，所以，利用第一个点为基准点，将多边形划分为若干小三角形，求出每个小三角形的“力矩”，其和除以三角形的“重量和”即得。

SOJ1153              Play on Words 

题目类型  图论

总结      首先用一次深度优先搜索，判断图是否连通，然后利用欧拉道路的判断条件判断即可。

SOJ1154                  Simple Arithmetics

题目类型   模拟题

总结       空格的处理比较麻烦，分清各种情况讨论即可。

SOJ1156                   Complete the sequence!

题目类型   模拟题

总结       该题需要注意到一个重要条件：P(n) = a_D.n^D+a_D-1.n^D-1+...+a₁.n+a₀ ，所以数列经过若干次求导后会成为常数数列，再积分还原， 即可得到所求的项的系数。虽然该题是一道数学题，但是实际上模拟求导和积分的过程即得。

SOJ1157              Complicated Expressions

题目类型     模拟题

总结         利用产生式的原理，构建一个表达式树，然后遍历该树，同时去掉多余的括号即可。

1159            Factorial 

题目类型     数学

总结         设f(x)表示x！的末尾0的个数，有f(x) = x/5 + f(x/5)，注意边界条件。

SOJ1163   Cash Machine

题目类型     动态规划

总结         递推，每得到一种货币就递推出新的货币，同时做标记加快速度。

SOJ1169Manager 

题目类型     模拟题

总结         利用队列模拟。

SOJ1170Area2

题目类型     数学

总结         该题用到一个公式：网格形成的多边形，其面积等于它完成占有的点的个数。

SOJ1173   Cog-Wheels

题目类型   

利用已知的齿轮，在一定范围内生成新的齿轮，检验比率能不能实现时，注意不断扩大倍数后再检验。       

SOJ1174              Cube  

题目类型     模拟题

总结         做法是先用4个拼成一个“环”，然后加上两个“盖子”。注意实际是一个6重循环，每个已知面都要尝试每个位置。

SOJ1180              StrategicGame

题目类型     图论

总结         先根据输入数据构建一棵树，然后前序遍历一遍，保存在一个一维数组中。然后从数组最后一个元素开始扫描，如果发现它的父亲和它均没有标记，则标记它的父亲，结果＋＋。最后输出结果即可。

SOJ1181              Multiple

题目类型     数论

总结         利用 (a * 10 + b) % n == (a % n + b ) % n，进行广度优先搜索，每个节点保存一个数字，该数字的前面一个数字的序号，该数字与前面数字组成多位数对N的余数，当余数为0的时候结束搜索。同时给已经生成的余数做标记，因为如果相同的余数出现，那么后出现的一定不是最优，可以大大减少搜索量。

1182        Girls and Boys

题目类型   图论

总结        和1186相识，只是划分2分图的时候小心，可以用深度优先搜索实现。

SOJ1186             Courses

题目类型    图论

总结        用到2分图的匹配，用匈牙利算法即可，有两种比较经典的实现方法。网络流也可实现。

SOJ1187             closest common ancestors

题目类型      模拟题

总结          利用给出的树，对要求的两个节点的中任意一个以及它的父亲，做标记，然后给父亲节点的父亲做标记，直到根节点为止，然后找另外一个节点的父亲节点，看其有没有被标记过，直到根节点为止。

SOJ1191                 Bode Plot

题目类型      物理

总结          求出常数角tri = atan(1/(C*R*w)),再令时间为2（其他值也可）有VR = VS * C * w * R * sin(2*w) /( C * w * R * sin(2 * w + tri) - cos(2 * w + tri))，

SOJ1192             follow my logic

题目类型       模拟题

总结：         递归的实现，主要注意遇到电路的时候可以另外写个递归，与逻辑门的递归加以区别。