文章来源: http://thunderfyc.wordpress.com.cn/ 

Meta-Loopless Sorts
 UVA 110

输出Pascal的排序程序

简单递归实现 在第i层时 用判断来枚举 第i个元素的位置

——————————————————————————————
History Grading
 UVA 111

已知正确的排列顺序 要求判断给出排列的最长的符合正确的序列

用LIS 或者LCS简单实现 用Opt[i]表示到第i个位置的最长，然后对于Opt[i+1] 枚举前面的Opt[1..i]即可
注意题目给出的第i个数字是第i个时间处于哪个位置

——————————————————————————————
Tree Summing
 UVA 112  PKU 1145

统计从根到叶子的节点的路径和 有无满足条件的

用堆栈或者递归可以实现从根到叶子的访问过程 注意是叶子节点 不是只有一个孩子的节点 注意负数的可能性

——————————————————————————————
Power of Cryptography
 UVA 113  PKU 2109

根幂转换

直接数学搞 不过不知道为什么floor(tmp+0.5)要WA

——————————————————————————————
Simulation Wizardry
 UVA 114  PKU 1216

题意 (1,1)是墙 (m,n)也是墙，首先需要1时间去撞墙 然后 如果还活着 可以得分 然后减去损失

——————————————————————————————
Climbing Trees
 UVA 115

已知 家族树(单亲) 求两个人的关系

LCA问题 如果两个人有人不在数据中 或者祖先不同 无关系 然后如果LCA为其中一个 直系亲属 否则为cousin 计算时用DFS记录到LCA的高度
LCA的Tarjan算法 用递归 对于节点X 先标记祖先为自身 去访问每个孩子 访问完之后 孩子的祖先记为X X标记为已访问。 然后去寻找每个已访问的节点，和X的LCA为X目前能找到的祖先(注意更早的祖先还没有标识)

——————————————————————————————
Unidirectional TSP
 UVA 116

已知一个矩阵 找到一条从第一列到最后一列的路径 和最小 有多条时输出以行为关键字字典序最小的

以列为决策层 用opt[i][j]表示到i列j行的最小值， 如果从左往右DP的话 最后得不到最小字典序 所以要从右往左DP 当有相同时 记录较小的行。

——————————————————————————————
The Postal Worker Rings Once
 UVA 117  PKU 1237

已知邮递员线路 且组成的网络可一笔走完 求走完所有路回到起点的最少时间
如果无奇度数点 直接加起来 如果有 找到这两个点的最短距离 然后把边长相加再加距离

——————————————————————————————
Mutant Flatworld Explorers
 UVA 118

机器人按指令行进 可以掉出地图 掉出的地方 如果另外一个机器人路过也要从这里掉出去 他会无视命令

——————————————————————————————
Greedy Gift Givers
 UVA 119

每个人要给其他人钱 平分 如果有的多 没法平分的 自己留着 最后把自己得到的钱和手上留着的钱减去给出的钱

文章来源: http://thunderfyc.wordpress.com.cn/ 

——————————————————————————————

分析
 110 AC1 0.730s  代码大规模修改多 敲的速度慢
 111 AC1 0.040s  理解题意错
 112 TLE1 WA1 0.240s  未考虑负数 在处理到叶子节点是错误
 113 WA1 0.020  费解的精度问题
 114 AC1 0.140  理解题意困难
 115 RE1 WA1 0.020  memset string的时候RE 计算深度时错误 输出cousin错误
 116 WA1 0.460  一开始从左往右DP
 117 CE1 0.010  用了一个名为link的数组
 118 WA1 0.010  没大写
 119 WA1 0.010  输出格式错 没考虑不给钱的人

文章来源: http://thunderfyc.wordpress.com.cn/