A.約數(shù)個(gè)數(shù)(簽到題)

1200000?有多少個(gè)約數(shù)（只計(jì)算正約數(shù)）。

分析: 我們可以?xún)?yōu)化一下求因子的過(guò)程, 讓i只循環(huán)到sqrt(num), 為了防止重復(fù)計(jì)數(shù)放入 set 即可:

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

B: 門(mén)牌制作(模擬)

【問(wèn)題描述】

小藍(lán)要為一條街的住戶(hù)制作門(mén)牌號(hào)。

這條街一共有 2020 位住戶(hù)，門(mén)牌號(hào)從 1 到 2020 編號(hào)。

小藍(lán)制作門(mén)牌的方法是先制作 0 到 9 這幾個(gè)數(shù)字字符，最后根據(jù)需要將字

符粘貼到門(mén)牌上，例如門(mén)牌 1017 需要依次粘貼字符 1、 0、 1、 7，即需要 1 個(gè)

字符 0， 2 個(gè)字符 1， 1 個(gè)字符 7。

請(qǐng)問(wèn)要制作所有的 1 到 2020 號(hào)門(mén)牌，總共需要多少個(gè)字符 2？

分析: 模擬即可，時(shí)間復(fù)雜度為 O(nlgn):

C: 跑步鍛煉(模擬)

【問(wèn)題描述】

小藍(lán)每天都鍛煉身體。

正常情況下，小藍(lán)每天跑 1 千米。如果某天是周一或者月初（1 日），為了

激勵(lì)自己，小藍(lán)要跑 2 千米。如果同時(shí)是周一或月初，小藍(lán)也是跑 2 千米。

小藍(lán)跑步已經(jīng)堅(jiān)持了很長(zhǎng)時(shí)間，從 2000 年 1 月 1 日周六（含）到 2020 年

10 月 1 日周四（含）。請(qǐng)問(wèn)這段時(shí)間小藍(lán)總共跑步多少千米？

分析: 從2000年開(kāi)始一天一天算即可,?要依次更新天數(shù)，星期數(shù)，年數(shù) (還要判斷日期是否合法(閏年)):

D: 平面分割(幾何?+ 遞推)

【問(wèn)題描述】
20條直線和20個(gè)圓最多能把一個(gè)平面分割成多少部分？

分析: 這種題一般都是規(guī)律題，要用數(shù)學(xué)推出關(guān)系式

設(shè) a[i][j] 為 i 條直線, j 個(gè)圓時(shí)的分割平面的數(shù)量

假設(shè)只有直線: 要使得平面盡可能被分割, 我們要讓第 i 條直線與之前的直線相交, 通過(guò)作圖可以發(fā)現(xiàn)每次會(huì)新增 i 個(gè)平面.

當(dāng)我們添加圓時(shí), 如果要使平面盡可能被分割, 我們要使第 i 個(gè)圓盡可能與之前的直線和園相交， 通過(guò)作圖發(fā)現(xiàn)會(huì)增加??2 * i + 2 * (j - 1) 個(gè)平面.

E: 蛇形填數(shù)(模擬)

如下圖所示，小明用從 1 開(kāi)始的正整數(shù)“蛇形”填充無(wú)限大的矩陣。

1 2 6 7 15 :::

3 5 8 14 :::

4 9 13 :::

10 12 :::

11 :::

:::

容易看出矩陣第二行第二列中的數(shù)是 5。請(qǐng)你計(jì)算矩陣中第 20 行第 20 列

的數(shù)是多少 ?

分析: 通過(guò)觀察可以發(fā)現(xiàn)每次填數(shù)?row, col 都會(huì)加一，起點(diǎn)或終點(diǎn)是 a[row][1] (第奇數(shù)次) 或 a[1][col]?(第偶數(shù)次),于是開(kāi)始模擬"對(duì)角循環(huán)":

F: 成績(jī)統(tǒng)計(jì)(模擬)

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB

本題總分：15 分

【問(wèn)題描述】

小藍(lán)給學(xué)生們組織了一場(chǎng)考試，卷面總分為 100 分，每個(gè)學(xué)生的得分都是一個(gè) 0 到 100 的整數(shù)。

如果得分至少是 60 分，則稱(chēng)為及格。如果得分至少為 85 分，則稱(chēng)為優(yōu)秀。

請(qǐng)計(jì)算及格率和優(yōu)秀率，用百分?jǐn)?shù)表示，百分號(hào)前的部分四舍五入保留整數(shù)。

分析: c++中可以用 %.0f 四舍五入保留整數(shù)

G: 單詞分析(模擬 || 優(yōu)先隊(duì)列)

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB

本題總分：20 分

【問(wèn)題描述】

小藍(lán)正在學(xué)習(xí)一門(mén)神奇的語(yǔ)言，這門(mén)語(yǔ)言中的單詞都是由小寫(xiě)英文字母組成，有些單詞很長(zhǎng)，遠(yuǎn)遠(yuǎn)超過(guò)正常英文單詞的長(zhǎng)度。小藍(lán)學(xué)了很長(zhǎng)時(shí)間也記不住一些單詞，他準(zhǔn)備不再完全記憶這些單詞，而是根據(jù)單詞中哪個(gè)字母出現(xiàn)得最多來(lái)分辨單詞。

現(xiàn)在，請(qǐng)你幫助小藍(lán)，給了一個(gè)單詞后，幫助他找到出現(xiàn)最多的字母和這個(gè)字母出現(xiàn)的次數(shù)。

當(dāng)然，求優(yōu)先級(jí)問(wèn)題也可以用優(yōu)先隊(duì)列，效率會(huì)更高:

?I: 作物雜交(dp超時(shí)，寄)

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB

本題總分：25 分

作物雜交是作物栽培中重要的一步。已知有 N 種作物 (編號(hào) 1 至 N )，第i 種作物從播種到成熟的時(shí)間為 Ti。作物之間兩兩可以進(jìn)行雜交，雜交時(shí)間取兩種中時(shí)間較長(zhǎng)的一方。如作物 A 種植時(shí)間為 5 天，作物 B 種植時(shí)間為 7 天，則 AB 雜交花費(fèi)的時(shí)間為 7 天。作物雜交會(huì)產(chǎn)生固定的作物，新產(chǎn)生的作物仍然屬于 N 種作物中的一種。

初始時(shí)，擁有其中 M 種作物的種子 (數(shù)量無(wú)限，可以支持多次雜交)。同時(shí)可以進(jìn)行多個(gè)雜交過(guò)程。求問(wèn)對(duì)于給定的目標(biāo)種子，最少需要多少天能夠得到。

如存在 4 種作物 ABCD，各自的成熟時(shí)間為 5 天、7 天、3 天、8 天。初始擁有 AB 兩種作物的種子，目標(biāo)種子為 D，已知雜交情況為 A × B → C，

A × C → D。則最短的雜交過(guò)程為：

第 1 天到第 7 天 (作物 B 的時(shí)間)，A × B → C。

第 8 天到第 12 天 (作物 A 的時(shí)間)，A × C → D。

花費(fèi) 12 天得到作物 D 的種子。

有大佬看一下這里 dp 有什么問(wèn)題嗎，這里調(diào)試了很久題目的測(cè)試過(guò)了但結(jié)果還是 WA 。。。

H: 數(shù)字三角形(dfs || 動(dòng)態(tài)規(guī)劃)

時(shí)間限制: 1.0s 內(nèi)存限制: 512.0MB

本題總分：20 分

【問(wèn)題描述】

上圖給出了一個(gè)數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。

對(duì)于每條路徑，把路徑上面的數(shù)加起來(lái)可以得到一個(gè)和，你的任務(wù)就是找到最大的和。

路徑上的每一步只能從一個(gè)數(shù)走到下一層和它最近的左邊的那個(gè)數(shù)或者右邊的那個(gè)數(shù)。此外，向左下走的次數(shù)與向右下走的次數(shù)相差不能超過(guò) 1。

分析: 挺經(jīng)典的 dp, 注意相差不能超過(guò) 1，所以最大一定落再最后一行的中位數(shù):

寫(xiě)了個(gè)暴力寫(xiě)法，順便練一下dfs騙分技巧(比賽并不容易想出 dp...):

J: 字串分值和(數(shù)學(xué) || 暴力)

暴力寫(xiě)法(能拿一半分):

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

那么拿滿(mǎn)分的方法是什么呢? 首先我們計(jì)算出如果所有字符都不相同的答案, 那么此時(shí)問(wèn)題就轉(zhuǎn)化為求一個(gè)字符串的所有子串, 對(duì)于一個(gè)字符串，我們截取出長(zhǎng)度為 i 的字符串, 此時(shí)的子串?dāng)?shù)量與長(zhǎng)度 i - 1的關(guān)系為:

dp[i] = dp[i - 1] + i;

那么我們對(duì) dp[i] 求和就可以得到最大的答案(就是字符串中全部字符都不同)

接下來(lái)我們要看有相同字符對(duì)我們答案的影響:

a b a b c

^? ? ^

通過(guò)枚舉我們發(fā)現(xiàn)a對(duì)答案的貢獻(xiàn)為 -3, 也就是有 3 個(gè)字串會(huì)受到影響, 所以要減去 3

再來(lái)看看 b

a b a b c

? ?^? ? ?^

通過(guò)枚舉我們會(huì)發(fā)現(xiàn)b對(duì)答案的貢獻(xiàn)為?-4, 也就是有 4?個(gè)字串會(huì)受到影響, 所以要減去 4

我們?cè)倮^續(xù)深入地想一想， 實(shí)際上受到影響的字串的個(gè)數(shù)與與兩邊字符串的個(gè)數(shù)有關(guān):

我們記第一次出現(xiàn)的下標(biāo)為 last[i]: 那么所有受到影響的個(gè)數(shù)為:

last[i] * (n - i)

于是我們將最理想的情況減去受到影響的個(gè)數(shù)就是答案了: