前言
这周很忙，但是越忙的时候反而越喜欢抽空做算法题。
欢迎关注algorithm文集。
这次A、B、C都是很合适的面试题。
正文
A. Memory and Crow
题目链接
题目大意：
给出n个数字。（a[1], a[2], ..., a[n]）
a[i]和b[i]的关系如下。
a[i] = b[i] - b[i+1] + b[i+2] - b[i+3]....
给出数组a[i]，求数组b[i]。
n (2 ≤ n ≤ 100 000)
a[i] ( - 1e9 ≤ a[i] ≤ 1e9)
** Examples**
** input**
5
6 -4 8 -2 3
** output**
2 4 6 1 3
** input**
5
3 -2 -1 5 6
output
1 -3 4 11 6
题目解析：
根据通项公式，知道b[n] = a[n]；（因为不能存在b[n+1])
然后倒着求b[i], b[i] = a[i] + a[i+1]；
B. Memory and Trident
题目链接
** 题目大意：**
输入一个字符串s，由 'L', 'R', 'U', or 'D'组成，分别表示点P在原点的向左、右、上、下前进一步。
修改字符串的序列，每次操作能修改一个字符为其他字符（L/R/U/D），问点P按照字符串s移动后能回到原点的最小操作次数；
如果可以，输出做小操作次数；
如果不能，则输出-1；
** Examples**
** input**
RRU
** output**
-1
** input**
UDUR
** output**
1
** 题目解析：**
先考虑不能情况。
如果字符串的长度为奇数，那么必然不能回到原点。
如果字符串的长度为偶数，那么必然有解。（最多把所有的字符串变成UDUD）
然后分开考虑，L 和 R 相对， U 和 D 相对。
求出在x方向和y方向的需要修改的字符数量。
容易知道我们可以把需要修改的数量加起来，然后除以2可以得到修改的次数。（两个方向的需要修改数量，必然为偶数）
C. Memory and De-Evolution
题目链接
题目大意：
有两个正三角形，边长分别为x，y。
现在可以对三角形进行操作，每次操作可以改变三角形的一条边长度（为整数），变成另外一个三角形。
问让正三角形x 变成 正三角形y 的最小操作次数。
x and y (3 ≤ y < x ≤ 100 000)
** Examples**
** input**
6 3
** output**
4
样例解释：666 -> 663 -> 643 -> 343 -> 333 总共需要操作4次
** 题目解析：**
三角形的性质:两边之和大于第三边。
反过来考虑，把三角形y变成三角形x。（操作步数是一致的）
那么自然可以想到一种贪心：每次把最小的边变得最大。
每次操作完排序，再对最小的进行变大。
直到最小的边也等于x。
D. Memory and Scores
题目链接
** 题目大意：**
A 和 B玩一个游戏，游戏分成t轮。
初始时，A和B的分数为a和b；
每轮游戏，A和B都可以从[-k, k]的区间里面选择一个整数加到自己的分数；
问最后有多少种可能，A的分数大于B的分数。
（只要某一轮A或者B的分数不同，即视为不同的可能）
a, b, k, and t (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100)
结果mod 1 000 000 007 (1e9 + 7)。
Example
** input**
1 2 2 1
** output**
6
** 样例解释：**
In the first sample test, A starts with 1 and B starts with 2. If B picks - 2, A can pick 0, 1, or 2 to win. If B picks - 1, A can pick 1 or 2 to win. If B picks 0, A can pick 2 to win. If B picks 1 or 2, A cannot win. Thus, there are 3 + 2 + 1 = 6 possible games in which A wins.
** 题目解析：**
容易知道，每次的选择都是[-k, k]，那么总共就有(2k + 1)个选择；
t轮之后就是(2k+1)^t个选择。
接下来考虑去重，存在一轮分数不同，即是在第i轮的时候，选择不同的数字。
那么，我们用dp[i][j]来表示 前i轮，分数等于j的选择个数。
这样就可以统计出t轮之后，分数为j的不同选择个数。
先是对A dp出t次后的结果，再对B dp出t次后的结果。这两个都是O(NK^2)。
最后再对dpB[n][j] 统计下所有∑dpA[n][c]，c > j，然后相乘，得到B为j的时候，A赢的选择数。
最后累加j = [-k * k / 2, k * k / 2]的和即可。
** 小技巧：**
1、为了方便计算，把所有的状态都加上一个offset，这样-k*k/2 就变成正数，避免dp过程中访问到下标是负的情况；
2、为了状态转移更快，dpA[i][j] 可以存分数为1到j的和，这样分数为j的值可以通过dpA[i][j] - dpA[i][j - 1]求出。
总结
趁着写文章，回顾下这四个题目，发现A/B/C对于我来说都是很简单题目，D需要一些思考和细节的考虑，算中等题。
但是对某些牛，可能他做D的难度就和我做前三个的难度差不多。
差距是哪里？？
1、角度，大牛思考更全面，能用最适当的思路去解决问题；
2、熟练度，像offset、mod、累加这些trick大牛一眼就看穿并且熟练地实现；
3、复杂度，大牛经常面对很多更复杂的情况，再回过来处理这些题目就更为容易；
或许还有其他原因，但是就这三点就值得深思。
如果是要做题目，应该先看到出题人的思路，顺着这个方向查看设置的trick，在有具体的解法后要完善好细节再实现；
如果是工作开发，则是要理解产品的需求，从用户的角度观察未来可能的变化，在设计好具体的解决方案后，再进行开发；
三思而后行，这是非常难以坚持的要求。
