A. ASC(簽到題)

已知大寫字母 A 的 ASCII 碼為 65，請(qǐng)問(wèn)大寫字母 L 的 ASCII 碼是多少？

時(shí)間復(fù)雜度: O(1)

B.空間(簽到題)

小藍(lán)準(zhǔn)備用?256MB?的內(nèi)存空間開(kāi)一個(gè)數(shù)組，數(shù)組的每個(gè)元素都是?32?位 二進(jìn)制整數(shù)，如果不考慮程序占用的空間和維護(hù)內(nèi)存需要的輔助空間，請(qǐng)問(wèn)?256MB?的空間可以存儲(chǔ)多少個(gè)?32?位二進(jìn)制整數(shù)？

分析: 我們知道8個(gè)bit為一個(gè)字節(jié)byte, 所以一個(gè)32位二進(jìn)制數(shù)需要 4 個(gè)字節(jié), 而 256MB 相當(dāng)于 256 * 1024 * 1024 個(gè) byte, 所以直接利用除法就可以得出答案了:

時(shí)間復(fù)雜度: O(1)

C.卡片(模擬)

小藍(lán)有很多數(shù)字卡片，每張卡片上都是數(shù)字?0?到?9。

小藍(lán)準(zhǔn)備用這些卡片來(lái)拼一些數(shù)，他想從?1?開(kāi)始拼出正整數(shù)，每拼一個(gè)，就保存起來(lái)，卡片就不能用來(lái)拼其它數(shù)了。

小藍(lán)想知道自己能從?1?拼到多少。

例如，當(dāng)小藍(lán)有?30?張卡片，其中?0?到?9?各?3?張，則小藍(lán)可以拼出?1?到?10，

但是拼?11?時(shí)卡片?1?已經(jīng)只有一張了，不夠拼出?11。

現(xiàn)在小藍(lán)手里有?0?到?9?的卡片各?2021?張，共?20210?張，請(qǐng)問(wèn)小藍(lán)可以從?1?拼到多少？

提示：建議使用計(jì)算機(jī)編程解決問(wèn)題。

分析: 我們可以用一個(gè)數(shù)組存放各卡片的個(gè)數(shù)， 然后進(jìn)行模擬統(tǒng)計(jì)各卡片的個(gè)數(shù), 當(dāng)有卡片的數(shù)量為 0 時(shí)當(dāng)前數(shù)字就是最大的了。

時(shí)間復(fù)雜度: O(n)

D.相乘 (模擬)

【問(wèn)題描述】小藍(lán)發(fā)現(xiàn)，他將 1 至 1000000007 之間的不同的數(shù)與 2021 相乘后再求除以

1000000007 的余數(shù)，會(huì)得到不同的數(shù)。小藍(lán)想知道，能不能在 1 至 1000000007 之間找到一個(gè)

數(shù)，與 2021 相乘后再除以 1000000007 后的余數(shù)為 999999999。如果存在，請(qǐng)?jiān)诖鸢钢刑峤贿@個(gè)數(shù)；如果不存在，請(qǐng)?jiān)诖鸢钢刑峤?0

1000000007 * 2021 可能會(huì)溢出, 所以要用到乘法取模的數(shù)學(xué)性質(zhì)避免數(shù)據(jù)溢出:

(a * b) % p = ( (a % p) * (b % p) ) % p

算法復(fù)雜度: O(n)

E.路徑(動(dòng)態(tài)規(guī)劃 || 圖論)

小藍(lán)學(xué)習(xí)了最短路徑之后特別高興，他定義了一個(gè)特別的圖，希望找到圖 中的最短路徑。

小藍(lán)的圖由 2021 個(gè)結(jié)點(diǎn)組成，依次編號(hào) 1 至 2021。

對(duì)于兩個(gè)不同的結(jié)點(diǎn) a, b，如果 a 和 b 的差的絕對(duì)值大于 21，則兩個(gè)結(jié)點(diǎn) 之間沒(méi)有邊相連；如果 a 和 b 的差的絕對(duì)值小于等于 21，則兩個(gè)點(diǎn)之間有一條 長(zhǎng)度為 a 和 b 的最小公倍數(shù)的無(wú)向邊相連。

例如：結(jié)點(diǎn) 1 和結(jié)點(diǎn) 23 之間沒(méi)有邊相連；結(jié)點(diǎn) 3 和結(jié)點(diǎn) 24 之間有一條無(wú) 向邊，長(zhǎng)度為 24；結(jié)點(diǎn) 15 和結(jié)點(diǎn) 25 之間有一條無(wú)向邊，長(zhǎng)度為 75。

請(qǐng)計(jì)算，結(jié)點(diǎn) 1 和結(jié)點(diǎn) 2021 之間的最短路徑長(zhǎng)度是多少。

分析: 求最短路徑的算法有很多， 其中最簡(jiǎn)單的就是 Floyd 暴力法了(也是對(duì)我來(lái)說(shuō)最好理解的)， 算法復(fù)雜度為 O(n^3) (這是一道填空題不害怕超時(shí)...).

我們根據(jù)題意進(jìn)行建樹, 這里我用了鄰接矩陣的方式， 定義鄰接矩陣map, 每個(gè)節(jié)點(diǎn)的邊權(quán)就是最短路徑,?那么我們的答案就是 map[1][2021]了。

最后提一下Floyd的基本核心, 就是先枚舉每一個(gè)節(jié)點(diǎn)看看是不是"中轉(zhuǎn)站"， 如果是的話則進(jìn)行松弛操作， 這樣我們就保證了最短路徑的子路徑是最短的, 核心代碼如下:

那么完整代碼為:

當(dāng)然，單源最短路徑建議還是用 Dijkstra:

時(shí)間復(fù)雜度: O(n^2):

下面我們考慮用動(dòng)態(tài)規(guī)劃, 我們先定義我們的狀態(tài):

dp[i] : 從 1?到 i?的最短路徑，我們用閆式dp法來(lái)分析一下(最近跟y總學(xué)的dp小技巧),?首先我們的問(wèn)題是要在一個(gè)包含所有路徑的有限集合(集合)中找到一條最短路徑(屬性),?我們現(xiàn)在來(lái)考慮最后一個(gè)合法的狀態(tài)，對(duì)于 dp[i] 包含了21個(gè)子集(因?yàn)轭}目說(shuō)兩個(gè)節(jié)點(diǎn)大于 21，則兩個(gè)結(jié)點(diǎn)之間沒(méi)有邊相連), dp[i] 是從 dp[i - 1], dp[i - 2] , ... , dp[i - 21] 轉(zhuǎn)移過(guò)來(lái)的 (滿足不重不漏), 這是變化的部分(因?yàn)閐p[i]表示的子集最后一個(gè)元素一定是 i (也就是本題中路徑的終點(diǎn)一定是 i),?而前面部分不是固定的)。假設(shè)從 k 轉(zhuǎn)移過(guò)來(lái), 那么不變的部分就是 lcm(k, i)了.

當(dāng)dp[i]為空時(shí)代表我們還沒(méi)有訪問(wèn)過(guò)這條路徑, 那么此時(shí) dp[i] = lcm(k, i)。

當(dāng)dp[i]不為空時(shí) dp[i] = min(dp[k], dp[k] +?lcm(k, i))

時(shí)間復(fù)雜度: O(n ^ 2)