**以下解答主要来自出题者提供的解题报告（可能略有改动）。由于本人能力的限制，可能对于很多数据结构和算法的理解存在偏差（如果发现什么问题，十之八九不是出题者的问题，而是我自己的理解有问题，因此写得不对），欢迎大家指正。:)
Ridiculous Addition
这个是一个比较简单的题目，要算出和的每一位，就需要两个数列的每一位，所以问题转化为能够在短时间内回应关于数列第k位的询问。
其实很简单：首先利用组合计数算出那个数字所在的整个数字的位数；然后组合计数算出结果。
举个例子 K=30 那么看第一个数列一位数有9个共9位，两位数有90个共180位所以是一个两位数，然后可以知道是第11个两位数的第1位是20的第一位，也就是2；同样的得出第二个数列的第30位是6，然后得出结果8。
不过还有进位的问题，解决的问题很简单：看它的后一位就可以了。
有人会问：那会不会循环得很长？其实不会的，有一个整数的Hash算法叫做平方取中法就是一个数的平方取中间部分，所以可以看出平方数的中部分类似于随机数所以进位情况不确定。
Birthday Cake
问题大意：计算F(k) = 1 ^ k + 2 ^ k + ... + n ^ k，n可能很大。
设G(s, k) = k!C(s, k) = s (s – 1) ... (s – k + 1) = s ^ k + a1 * s ^ (k –
1) + ... + ak, 那么
F(k) + a1 * F(k – 1) + ... + ak * F(0) = G(1, k) + G(2, k) + ... + G(n, k)
= k! (C(1, k) + C(2, k) + ... + C(n, k)) = k! C(n + 1, k + 1)
k! C(n + 1, k + 1)很容易计算，因此已知F(0), F(1), ..., F(k – 1)的值就可以推出F(k)的值。
Minimum Cost
显然不同商品之间是相互独立，可以把每种商品的最小费用加起来就是总费用最小。注意到商品的总数量不大而且都为整数，转化成二分图最小匹配来做。二分图左边为需求,右边为供货：比如有一个需求
3个i
商品，我们就把它拆成三个结点放于二分图的左边，有一个供货
4 个 i商品，我们就把它拆成4个结点放于二分图的右边，这样就构好了二分图。它们之间的边的权值对应于费用。只要求这个二分图的最小匹配就行了，累加起来就是最小费用。
Cover
本题限制矩形面积的主要目的是卡贪心算法。由于每个格子的费用都是正数，本题可以基于枚举做到O(N
^ 4)。
考虑最上，最下，最左，最右的四个’*’（有可能相同，可以先看作不同），这四个’*’都必须被某个矩形覆盖，所以就一定有一个矩形盖住两个’*’（抽屉原理），也就是说这个矩形有两条边已经确定了，然后枚举另外两条边，余下的问题就化为两个矩形覆盖的问题了。
两个矩形覆盖用同样的思路可以做到O(N ^ 2)。这样总的复杂度为O(N
^ 4)，常数比较大。
Little guys' game
对于此题一般的想法是bfs搜索，如果关注所有的格子的话，状态会很多。我们可以分别关注A，B，C，D（考虑一个字母的时候，别的字母都可以看成一样的），分别计算A，B，C，D达到赢的状态时需要的最少交换步骤以及在此最小交换步骤下的方法数，最后取四个中的最小值。这样的话状态就会一下子变得很少，为C(16,
4)。当然，我们可以把计算好的结果存起来，以后的查询就可以直接查询了而不用每次都要bfs了。
一共有9种位置可以赢，可以开个数组f[9][C(16,4)]表示四个相同类型的字母在任何位置达到赢的状态的最小步骤以及相应的方法数。复杂度是O(9*2^16)。
Cutting Necklace
这题算法大概就是，先转换成前缀和（P[i]表示前i个数的和）序列P[0]
~ P[2N]（因为是环，所以尾部复制一份），然后扫描P[i]，维护P[i
- U] ~ P[i - L]之间的下凸包序列，每次向凸包中加入点P[i - L]和去掉点P[i
- U]（这个需要一些技巧），然后二分法找与P[i]成斜率最大的点就可以得到终点是i的所有数串中平均值最大的串了。
DNA Sequence Alignment
这题的大体算法大概就是剪枝的递推。可以一行一行的递推，每次访问一个结点时，就和同一行下一个结点和下一行当前最后一个结点比较，看看是否有扩展的意义。如果有扩展的意义，再利用相似度大于0.9的条件进行判断，最后再扩展就行了。
How much did the businessman lose?
只要冷静分析，搞清楚3个变量之间的关系，应该很快能解出来：
商人每次的总成本为： N （商品成本价）+ C（找给客人的零钱）
商人每次的收入：M + C （客人总共给商人的钱）- P（假钞）
这样商人亏： N+C-(M+C-P) = N-M+P
如果值为负就表示商人赚钱。
|