程序员进阶之算法练习（四）
前言
我认为的编程能力：
- 基础知识：数据库、操作系统、网络原理等；
- 编码能力：软件架构（MVVM、MVP）、设计模式、编程语言（C、JAVA、C++）等；
- 思考能力：分析需求、算法设计、数学基础等；
其中非常重要的一个就是算法。 一个算法浓缩了程序员对一个问题的解读、分析、思考、推论、实现。 工作之后遇到的所有问题，难度都不如之前遇到过的算法题目。 那么，这些问题也会被我迎刃而解。
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
本篇因为篇幅，不贴代码实现。
A
题目大意：输入三个整数t, s, x。问输入的整数x等于 t, t + s, t + s + 1, t + 2s, t + 2s + 1... 中的一个。
题目解析：
分类讨论
偏移量：ret = x - t。
如果 ret < s， 只有 ret = 0；
如果 ret >= s， 满足 ret % s = 0或者1 即可。
是否觉得题目过于简单？
B
题目大意：输入一个科学计数法的数字，输出一个十进制计数的数字。
比如
输入8.549e2，输出854.9；
输入8.549e3，输出8549；
题目解析：
科学计数法的e，如果不为零，那么会对小数点的位置造成影响，比如：整数部分存在前导零、小数部分全部为零、整数小数部分全部为零的情况；
对着多种情况进行分类讨论即可。
有另外一种的方式，
scanf("%[^e]%ne%d",d,&l,&b);，利用scanf直接读取整数部分、小数部分的值，然后分类讨论。 可能这个才是正解。
C
题目大意：在自然数中，数i到数2i存在一条边，数i到数2i+1存在一条边。
输入有两类型：
1、在u到v的最短路径上每条边的费用都加w；
2、求u到v的最短距离；
当输入为类型2的时候，输出u到v的最短距离。
题目解析：
对于每个自然数i，会和比自己小的自然数构成一条边，比自己大的自然数构成两边条，那么可以把边的费用存在中较大数。
对于u到v的最短路径，必然存在的k，路径为(u, k) + (k, v)，k=lca(u,v)。（lca是最近公共祖先）
在此题目中，每次对u、v中的较大值/2，即可得到lca(u, v)。
D
题目大意：n个点形成一棵树，根节点为1。以1为起点，对树进行dfs遍历，current_time为访问到的时间。
求每个点的current_time期望值。
样例输入：
7
1 2 1 1 4 4
样例输出：
1.0 4.0 5.0 3.5 4.5 5.0 5.0
样例输入：
12
1 1 2 2 4 4 3 3 1 10 8
样例输出：
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0
DFS算法实现
let starting_time be an array of length n
current_time = 0
dfs(v):
current_time = current_time + 1
starting_time[v] = current_time
shuffle children[v] randomly (each permutation with equal possibility)
// children[v] is vector of children cities of city v
for u in children[v]:
dfs(u)题目解析：
对于点u有的若干个子节点，有：
如果v是u的子节点，那么starting_timev = 所有其他子树的和/2 + starting_timeu + 1。
推论：
如果u只有一个子树，那么starting_timev = starting_timeu + 1;
如果u有多个子树，如果先遍历其他子树，再遍历v所在子树，starting_time会加上其他子树的节点和；
由题目可知，遍历是随机的，那么相对子树v，先遍历某个子树的概率为1/2；
（如果难以理解，可以枚举abc、abcd的全排列，b在a前面的概率为1/2。
E
题目大意：有三个一模一样盒子从左到右排列。中间的盒子有一个特殊物品，每次操作随机选择左右两边的盒子和中间交换。
问n次操作后，中间盒子有特殊物品的概率。答案按照最简分数化简后，分子分母再mod值10E9+7。
题目解析：
给盒子编号1、2、3，那么盒子的排列有：
123、132、213、231、312、321；其中123、321是中间有特殊物品。
假设di是第i次操作后，盒子排列为j的次数。
di = di-1 + di-1;
di = di-1 + di-1;
di + di + di + di + di + di = 2 ^ i。（每次操作产生2种可能）
令fi = di + di。
fi = di-1 + di-1 + di-1 + di-1
= 2 ^ (i - 1) - di-1 - di-1
= 2 ^ (i - 1) -fi-1.
其中f0 = 1;
当i=2k的时候，f2k = 2^(2k-1) - 2^(2k-2) + 2^(2k-3) ... + 2^1 - 2^0 + 1;
f2k+1 = 2^(2k) - 2^(2k-1) + 2^(2k-2) ... - 2^1 + 2^0 - 1;
等比数列求和，化简后有：
f2k = (2^(2k)+2)/3;
f2k+1 = (2^(2k+1)-2)/3;
最终的答案为: ans = fn / 2^n.
当n=2k的时候，ans = f2k / 2^(2k) = (2(2k-1)+1)/(2(2k-1)*3);
当n=2k+1的时候，ans = f2k+1 / 2^(2k+1) = (2(2k)-1)/(2(2k)*3);
ans = x / y;
统一下，当n为奇数，x = (2^(n-1)+1) / 3, y = 2^(n-1);
当n为偶数， y = (2^(n-1)-1) / 3, y = 2^(n-1);
性质：如p是质数，且gcd(a,m)=1，那么 a^(m-1)≡1（mod m）。 （费马小定理）
推论：(a/b) % m = (a/b * 1) % m
= (a/b * b^(m-1)) % m
= (a * b^(m-2)) % m
= a%m * b^(m-2)%m
2^(n-1) % m = (2^n / 2) % m
= 2^n % m * 2^(m-2)%m
备注：感谢胡浩大神提供最后推论的思路。
总结
有思考，才会有收获。多次的苦思冥想，最后解决问题的那一刻，很刺激。
E题推论出公式很快，最后在化简卡住了很久，演算了多张草稿纸都没有思路，最后猜测应该是数论的知识，询问了数学系的一个朋友，最后得到了费马小定理可以用来化简分数的mod。