前言

我認(rèn)為的編程能力：

• 基礎(chǔ)知識：數(shù)據(jù)庫、操作系統(tǒng)、網(wǎng)絡(luò)原理等；
• 編碼能力：軟件架構(gòu)（MVVM、MVP）、設(shè)計模式、編程語言（C、JAVA、C++）等；
• 思考能力：分析需求、算法設(shè)計、數(shù)學(xué)基礎(chǔ)等；

其中非常重要的一個就是算法。
一個算法濃縮了程序員對一個問題的解讀、分析、思考、推論、實現(xiàn)。
工作之后遇到的所有問題，難度都不如之前遇到過的算法題目。
那么，這些問題也會被我迎刃而解。

看完題目大意，先思考，再看解析；覺得題目大意不清晰，點擊題目鏈接看原文。
文集：
程序員進(jìn)階之算法練習(xí)（一）
程序員進(jìn)階之算法練習(xí)（二）
程序員進(jìn)階之算法練習(xí)（三）
本篇因為篇幅，不貼代碼實現(xiàn)。

A

題目鏈接
題目大意：輸入三個整數(shù)t, s, x。問輸入的整數(shù)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

代碼實現(xiàn)
題目解析：
分類討論
偏移量：ret = x - t。
如果 ret < s， 只有 ret = 0；
如果 ret >= s， 滿足 ret % s = 0或者1 即可。

是否覺得題目過于簡單？

B

題目鏈接
題目大意：輸入一個科學(xué)計數(shù)法的數(shù)字，輸出一個十進(jìn)制計數(shù)的數(shù)字。
比如
輸入8.549e2，輸出854.9；
輸入8.549e3，輸出8549；

數(shù)字的輸入形式是：a.deb
(0?≤?a?≤?9,?0?≤?d?<?10100,?0?≤?b?≤?100)

Examples
input
8.549e2
output
854.9
input
8.549e3
output
8549

代碼實現(xiàn)
題目解析：
科學(xué)計數(shù)法的e，如果不為零，那么會對小數(shù)點的位置造成影響，比如：整數(shù)部分存在前導(dǎo)零、小數(shù)部分全部為零、整數(shù)小數(shù)部分全部為零的情況；
對著多種情況進(jìn)行分類討論即可。

有另外一種的方式，scanf("%[^e]%ne%d",d,&l,&b);，利用scanf直接讀取整數(shù)部分、小數(shù)部分的值，然后分類討論。

C

題目鏈接
題目大意：在自然數(shù)中，數(shù)i到數(shù)2i存在一條邊，數(shù)i到數(shù)2i+1存在另一條邊，如下：

現(xiàn)在有q個輸入，每個輸入有兩類型：
1、在u到v的最短路徑上每條邊的費用都加w；（1 u v w）
2、求u到v的最短距離；（2 u v）
當(dāng)輸入為類型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

代碼實現(xiàn)
題目解析：
對于每個自然數(shù)i，會和比自己小的自然數(shù)構(gòu)成一條邊，比自己大的自然數(shù)構(gòu)成兩邊條，那么可以把邊的費用存在中較大數(shù)。
對于u到v的最短路徑，必然存在的k，路徑為(u, k) + (k, v)，k=lca(u,v)。（lca是最近公共祖先）
在此題目中，每次對u、v中的較大值/2，即可得到lca(u, v)。

D

題目鏈接
題目大意：n個點形成一棵樹，根節(jié)點為1。以1為起點，對樹進(jìn)行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算法實現(xiàn)

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)

代碼實現(xiàn)
題目解析：
對于點u有的若干個子節(jié)點，有：
如果v是u的子節(jié)點，那么starting_time[v] = 所有其他子樹的和/2 + starting_time[u] + 1。
推論：
如果u只有一個子樹，那么starting_time[v] = starting_time[u] + 1;
如果u有多個子樹，如果先遍歷其他子樹，再遍歷v所在子樹，starting_time會加上其他子樹的節(jié)點和；
由題目可知，遍歷是隨機(jī)的，那么相對子樹v，先遍歷某個子樹的概率為1/2；

（如果難以理解，可以枚舉abc、abcd的全排列，b在a前面的概率為1/2。

E

題目鏈接
題目大意：有三個一模一樣盒子從左到右排列。中間的盒子有一個特殊物品，每次操作隨機(jī)選擇左右兩邊的盒子和中間交換。
問n次操作后，中間盒子有特殊物品的概率。答案按照最簡分?jǐn)?shù)化簡后，分子分母再mod值10e9+7。

代碼實現(xiàn)
題目解析：
給盒子編號1、2、3，那么盒子的排列有：
123、132、213、231、312、321；其中123、321是中間有特殊物品。
假設(shè)d[i][j]是第i次操作后，盒子排列為j的次數(shù)。
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。（每次操作產(chǎn)生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;

當(dāng)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;
等比數(shù)列求和，化簡后有：
f[2k] = (2^(2k)+2)/3;
f[2k+1] = (2^(2k+1)-2)/3;

最終的答案為: ans = f[n] / 2^n.
當(dāng)n=2k的時候，ans = f[2k] / 2^(2k) = (2^(2k-1)+1)/(2(2k-1)*3);
當(dāng)n=2k+1的時候，ans = f[2k+1] / 2^(2k+1) = (2^(2k)-1)/(2(2k)*3);

ans = x / y;
統(tǒng)一下，當(dāng)n為奇數(shù)，x = (2^(n-1)+1) / 3, y = 2^(n-1);
當(dāng)n為偶數(shù)， y = (2^(n-1)-1) / 3, y = 2^(n-1);

性質(zhì)：如p是質(zhì)數(shù)，且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

備注：感謝胡浩大神提供最后推論的思路。

總結(jié)

有思考，才會有收獲。多次的苦思冥想，最后解決問題的那一刻，很刺激。
E題推論出公式很快，最后在化簡卡住了很久，演算了多張草稿紙都沒有思路，最后猜測應(yīng)該是數(shù)論的知識，詢問了數(shù)學(xué)系的一個朋友，最后得到了費馬小定理可以用來化簡分?jǐn)?shù)的mod。