程序员进阶之算法练习（四）

前言

我认为的编程能力：

• 基础知识：数据库、操作系统、网络原理等；
• 编码能力：软件架构（MVVM、MVP）、设计模式、编程语言（C、JAVA、C++）等；
• 思考能力：分析需求、算法设计、数学基础等；

其中非常重要的一个就是算法。
一个算法浓缩了程序员对一个问题的解读、分析、思考、推论、实现。
工作之后遇到的所有问题，难度都不如之前遇到过的算法题目。
那么，这些问题也会被我迎刃而解。

看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
文集：
程序员进阶之算法练习（一）
程序员进阶之算法练习（二）
程序员进阶之算法练习（三）
本篇因为篇幅，不贴代码实现。

A

题目链接
题目大意：输入三个整数t, s, x。问输入的整数x是否等于 t, t + s, t + s + 1, t + 2s, t + 2s + 1... 中的一个。
t, s and x (0 ≤ t, x ≤ 1e9, 2 ≤ s ≤ 1e9)

Examples
input
3 10 4
output
NO
input
3 10 3
output
YES

代码实现
题目解析：
分类讨论
偏移量：ret = x - t。
如果 ret < s， 只有 ret = 0；
如果 ret >= s， 满足 ret % s = 0或者1 即可。

是否觉得题目过于简单？

B

题目链接
题目大意：输入一个科学计数法的数字，输出一个十进制计数的数字。
比如
输入8.549e2，输出854.9；
输入8.549e3，输出8549；

数字的输入形式是：a.deb
(0 ≤ a ≤ 9, 0 ≤ d < 10100, 0 ≤ b ≤ 100)

Examples
input
8.549e2
output
854.9
input
8.549e3
output
8549

代码实现
题目解析：
科学计数法的e，如果不为零，那么会对小数点的位置造成影响，比如：整数部分存在前导零、小数部分全部为零、整数小数部分全部为零的情况；
对着多种情况进行分类讨论即可。

有另外一种的方式，scanf("%[^e]%ne%d",d,&l,&b);，利用scanf直接读取整数部分、小数部分的值，然后分类讨论。

C

题目链接
题目大意：在自然数中，数i到数2i存在一条边，数i到数2i+1存在另一条边，如下：

现在有q个输入，每个输入有两类型：
1、在u到v的最短路径上每条边的费用都加w；（1 u v w）
2、求u到v的最短距离；（2 u v）
当输入为类型2的时候，输出u到v的最短距离。
q (1 ≤ q ≤ 1 000)
(1 ≤ v, u ≤ 1e18, v ≠ u, 1 ≤ w ≤ 1e9)

Example
input
7
1 3 4 30
1 4 1 2
1 3 6 8
2 4 3
1 6 1 40
2 3 7
2 2 4
output
94
0
32

代码实现
题目解析：
对于每个自然数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

n (1 ≤ n ≤ 1e5)

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_time[v] = 所有其他子树的和/2 + starting_time[u] + 1。
推论：
如果u只有一个子树，那么starting_time[v] = starting_time[u] + 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是中间有特殊物品。
假设d[i][j]是第i次操作后，盒子排列为j的次数。
d[i][123] = d[i-1][213] + d[i-1][132];
d[i][321] = d[i-1][231] + d[i-1][312];
d[i][123] + d[i][132] + d[i][213] + d[i][231] + d[i][312] + d[i][321] = 2 ^ i。（每次操作产生2种可能）

令f[i] = d[i][123] + d[i][321]。
f[i] = d[i-1][213] + d[i-1][132] + d[i-1][231] + d[i-1][312]
= 2 ^ (i - 1) - d[i-1][123] - d[i-1][321]
= 2 ^ (i - 1) -f[i-1].
其中f[0] = 1;

当i=2k的时候，f[2k] = 2^(2k-1) - 2^(2k-2) + 2^(2k-3) ... + 2^1 - 2^0 + 1;
f[2k+1] = 2^(2k) - 2^(2k-1) + 2^(2k-2) ... - 2^1 + 2^0 - 1;
等比数列求和，化简后有：
f[2k] = (2^(2k)+2)/3;
f[2k+1] = (2^(2k+1)-2)/3;

最终的答案为: ans = f[n] / 2^n.
当n=2k的时候，ans = f[2k] / 2^(2k) = (2^(2k-1)+1)/(2(2k-1)*3);
当n=2k+1的时候，ans = f[2k+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。