A. Password

小 M 有一個(gè)四位數(shù)的密碼，每位都是數(shù)字 0 - 9，他忘記了密碼，但是他記得密碼用了兩種數(shù)字，每種用了 2 個(gè)，且記得沒用哪些數(shù)字（n 個(gè)，會(huì)從輸入給出），求可能的密碼的數(shù)量。

比如，沒用 1，2，4，5，6，8，9，0，那么剩下 3，7，有 3377，3737 ... 等可能。

思路：

簡單數(shù)學(xué)題，看密碼可能是怎么樣的有兩步，第一步是從剩下的 10 - n 個(gè)數(shù)字中選出兩個(gè)數(shù)字，然后排列這兩種共四個(gè)數(shù)字，可以用公式直接算出來:?,組合數(shù)直接遞推預(yù)處理出來，右邊的式子直接手算出來是 6.

B. Permutation Value

給定一個(gè)長度為 n 的排列 （1 - n 的排列），現(xiàn)在定義一個(gè)排列的值為：它的所有也是排列的連續(xù)子序列的個(gè)數(shù)。一個(gè)長為 s 的序列需要包含 1 - s 各一次。比如排列 [2, 1, 3]，有連續(xù)子序列 [2],[1],[3], [2, 1], [2, 3], [2, 1, 3]，其中有: [1], [2,1], [2, 1, 3] 是排列，因此值為 3. 現(xiàn)在給定一個(gè)整數(shù)，輸出一個(gè)使得排列的值最小的長度為 n 的排列。

思路：

注意到，如果把 1 放在第一個(gè)位置，2 放在最后一個(gè)位置，那么顯然只有 [1] 這個(gè)子序列和 [1, ....., 2] 這個(gè)子序列是排列，因?yàn)槠渌魏伍L度小于 n 的子序列都不會(huì)同時(shí)包含 1，2。而在任何排列中，[1], 和 長度為 n 的子序列都會(huì)是排列，因此 2 是排列的值的下界。因此上述的方案會(huì)給出一個(gè)最小的值的排列，也就是 [1, ...,...,.., ... ,..., 2]

C.?Save the Magazines

小 M 要給大家送報(bào)紙，一條街上有 n 個(gè)箱子，小 M 在第 i 個(gè)箱子塞進(jìn)???份報(bào)紙?，F(xiàn)在突然下雨了，有的箱子沒蓋子，有的箱子有蓋子，有蓋子的箱子可以保護(hù)箱子里的報(bào)紙，沒蓋子的箱子里的報(bào)紙會(huì)濕透?，F(xiàn)在假設(shè)小 M 可以在一瞬間進(jìn)行任意的蓋子移動(dòng)，但是在 i 位置的蓋子只能移到 i - 1 位置，且每個(gè)蓋子只能被移動(dòng)一次，問小 M 最多能救過來多少報(bào)紙？

思路：

從左到右來考慮，如果第一個(gè)箱子是被蓋著的，那么直接把其中的報(bào)紙份數(shù)加入答案，并往后考慮。如果一個(gè)箱子是沒被蓋著的，且它下一個(gè)箱子也沒蓋子，那么直接跳過這個(gè)箱子。如果當(dāng)前箱子沒蓋子，下一個(gè)箱子有蓋子，考慮這樣的一種情況: 01...1，當(dāng)最前面的箱子把后一個(gè)的蓋子奪走，有可能下一個(gè)箱子也可以再搶它下一個(gè)箱子的蓋子，容易看出按這種辦法可以讓 01....1 中任意一個(gè)位置為 0，也就是放棄這個(gè)箱子。顯然要放棄這里面報(bào)紙最少的箱子，做法是統(tǒng)計(jì)這一段的和與最小值，用和減去最小值就是這一段的最大挽救的報(bào)紙份數(shù)。通過這種方法線性的掃一遍就求出答案了。