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

The 3n + 1 problem
 UVA 100      PKU 1207

一个正整数按照一定规则可以变成1，问一个区间内变换步骤最长多少

直接枚举，不需要记录，而且根据试验，记录后耗时更长。要注意输入的两个数据

==================================================================================

The Blocks Problem
 UVA 101     PKU 1208

机器人移动方块，定义放回木块为把木块i放到位置i上。 1 把A上木块放回 B上木块放回 A放到B上；2 把A上木块放回 A放到B堆上；3把B上木块放回 把A及以上放到B上；4把A及以上放到B堆上

直接模拟，对于放回操作，可以肯定直接放回即可
==================================================================================

Ecological Bin Packing
 UVA 102

三个回收箱里面有玻璃，三类玻璃分类回收，最少要移动多少玻璃

枚举三个回收箱里分别哪一类
==================================================================================

Stacking Boxes
 UVA 103

N维向量定义比较规则，然后找到最长的向量递增序列

可以知道向量之间的关系是传递的，不可逆的，那么把每个向量内部排序，直接可以比较
得到一个有向图，对其进行拓扑排序。从射入边数（入度）为0的点开始访问，用opt[i]表示到节点i的最长递增序列，pre[i]表示节点i取最优时的前驱。直到没有入度为0的点为止。
==================================================================================

Arbitrage
 UVA 104      PKU 1238

已知汇率，要求找到兑换次数小于等于n的方法，使得货币i回到货币i时，得到超过1%的收益，有多种方案时输出任意最少次数的

对于矩阵G_0表示最初汇率 G_i表示经过i次兑换后的最高“汇率” 那么G_i = G_0 @ G_i-1
A@B = C  C[i][j] = max{A[i][k]*B[k][j]}
==================================================================================

The SkyLine Problem
 UVA 105

已知建筑的信息，求正视图边界

用H[i]表示第i个位置上的最高高度，在输出的时候，如果最高高度变化了 就要输出横坐标、纵坐标
==================================================================================

Fermat vs. Pythagoras
 UVA 106     PKU 1305

求出范围内的互素的毕达哥拉斯数的组数，和不属于任何毕达哥斯数三元组的数的个数

将三元的枚举转化成两元
a^2+b^2=c^2
假设 x = a/c;  y = b/c;
     x^2+y^2=1
     y^2=(1-x)(1+x)=> y/(1+x) = (1-x)/y
设 t = y/(1+x)
   tx-y=-t;  x+ty=1;
另 t = u/v   [t为有理数]
   a/c = (v^2 - u^2)/(u^2+v^2)
   b/c = (2uv)/(u^2+v^2)
u,v互素 且有一个奇数 v>u, a = v^2 - u^2; b = 2uv c = u^2 + v^2
==================================================================================

the Cat in the Hat
 UVA 107     PKU 1289

猫的帽子里总有n个小猫，小猫又有小小猫，小猫的高度是猫的1/(n+1)，最小的猫高为1，已知最大的猫高度和最小的猫数，求除了最小猫的数量和所有猫的高度和

H0 = (N+1)^dep;
workNum = N^dep;
ln(H0) = dep*ln(N+1); ln(workNum) = dep*lnN;
ln(H0)/ln(workNum) = ln(N+1)/ln(N); [此方程y -> 1 精度会有问题]

ln(H0)/ln(H0/workNum) = ln(N+1)/ln((N+1)/N) = ln(N+1) / ln(1 + 1/N)
y = ln(N+1) / ln(1+ 1/N)  [增函数]
用Newton-Raphson 牛顿迭代法解（随便一个初始值，从函数上此点作切线，和x轴交点为新的值）
x = x0 - f(x0)/f’(x0) 迭代几次就可以了

notWorkNum = 1 + N + N^2 + … + N^(dep-1) = (N^dep - 1)/(N-1) = (workNum - 1)/(N-1);
HSum = 1 + (N+1)+(N+1)^2 + … + (N+1)^dep = ((N+1)^(dep+1) - 1)/N = (H0*(N+1) - 1)/N;
==================================================================================

Maximum Sum
 UVA 108     PKU 2479

一个含负数矩阵，求最大和的子矩阵，即该矩阵元素和最大

可以得到opt[i][j][k]表示第i行的第j个元素到第k个元素和，然后枚举j和k，求这个序列中的最大和
Kadane算法：对于一维数组求最大子段和，从头开始，用a记录加到此的值，用b记录目前最大值；如果a小于0的话，就清为0，表示从此开始重新取段，这样更划算
最后注意，如果值为0 ，判断矩阵中有无负数；如果有，找一个最大的负数
==================================================================================

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

SCUD Busters
 UVA 109     PKU 1264

已知一个王国的点，王国范围为包含所有点的最小凸多边形，轰炸时，如果导弹落在王国内，就可以毁灭王国，求最后毁灭的面积

用Graham求凸包，找到最下的点，然后按照顺时针方向排序，然后将最下点和逆时针第一点压入栈，然后枚举后面的点，如果栈顶点射向此点形成的向量，在 栈第二顶点射向顶点的向量 的逆时针方向(左边)，即可继续；否则不停弹出栈顶点，直到满足条件
如果 向量a叉乘向量b为正 则a在b的顺时针方向(右边)
判断点是否在凸包中，可以用用随机的方法从点射出若干条射线，如果该射线和凸包有奇数个交点，在形内，否则在形外。关于判相交的方法，假设射线为很长的线段，然后注意排除线段的重合，端点重合，端点在线段上等问题之后，若两线段相交，那么某线段的端点射向另一线段两端点形成的向量非别在某线段的逆时针方向和顺时针方向。
或者我们可以将地图大方格纸染色。首先沿着凸包的边添，逆时针方向走如果向量射向右边，涂这个线段上方的点，反之亦然。如此就可以得到边界，然后直接涂。

===================================================================================

分析
 100      AC1 0.590s      不敢枚举
 101      WA3 0.030s      没有理解题目中”return”的意思
 102      AC1 0.280s
 103      AC1 0.020s      调试慢
 104      WA4 0.120s      在记录路径时忘记记录方式
 105      AC1 0.030s      生成思路慢
 106      AC1 0.410s      没能自己推出公式
 107      AC1 0.460s      运算过程中未考虑到方程趋向1的精度问题
 108      AC1 0.030s      忘记Kadane算法
 109      WA4 0.000s      凸包排序过程中没有找最低点WA次 排序时没把最低点单列WA 填充方格思路慢 不敢写判点在形内算法

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