LCP 66. 最小展臺(tái)數(shù)量

【哈希表】記錄每個(gè)字母的最大值即可，結(jié)果為所有字母最大值的和。注意到Counter本質(zhì)上表示的是一個(gè)多重集，用 | 可以計(jì)算并集。

LCP 67. 裝飾樹

【DFS】按題意遞歸即可。

LCP 68. 美觀的花束

【雙指針】如果一個(gè)區(qū)間是美觀的，那么這個(gè)區(qū)間的子區(qū)間也是美觀的，枚舉區(qū)間右端點(diǎn)，去看左端點(diǎn)最遠(yuǎn)（最?。┦嵌嗌?，那么[l, r] [l + 1, r] [l + 2, r] ... [r, r]都是合法的，右指針移動(dòng)時(shí)，左指針不會(huì)左移。

LCP 69. Hello LeetCode!

【狀壓DP】1.用位運(yùn)算表示字母選擇情況，由于一個(gè)字母可以選多個(gè)，因此要對(duì)二進(jìn)制分區(qū)，每個(gè)區(qū)域表示對(duì)應(yīng)字母的個(gè)數(shù)。2.寫一個(gè)記憶化搜索，f(i, mask)表示從第i個(gè)單詞開始選，已經(jīng)選擇的單詞為mask時(shí)，后續(xù)消耗代幣的最小值。枚舉words[i]的所有合法選擇方案轉(zhuǎn)移到f(i+1，mask)。3.因此需要預(yù)處理每個(gè)words[i]的每種選擇字母的方案所消耗的代幣的最小值，由于字符串很短，直接寫個(gè)暴搜即可。

LCP 70. 沙地治理

【找規(guī)律】可證最少需要?(n^2 + 3n + 2) / 4?個(gè)三角形。

LCP 71. 集水器

【并查集】1.判斷能否容納水：第i行的水，在不走到第i-1行的前提下，無法觸及左、右、下邊界。2.轉(zhuǎn)換成連通性問題，用并查集處理。3.為了方便判斷是否觸及邊界，還需要在左、右、下各加一條格子。4.根據(jù)1，我們可以從最后一行往上計(jì)算。5.用并查集合并當(dāng)前行各個(gè)區(qū)域，以及邊界。6.如果合并完了，枚舉當(dāng)前行的各個(gè)區(qū)域，如果不和邊界相連，那么該區(qū)域能容納水。7.邊界、最上面一層和超級(jí)匯點(diǎn)0相連。8.最后判斷的時(shí)候，如果該區(qū)域能容納水，且和超級(jí)匯點(diǎn)相連，那么不是閉合區(qū)域，就真的有水。9.統(tǒng)計(jì)真的有水的格子，即為答案。10.代碼實(shí)現(xiàn)時(shí)，把每個(gè)格子劃分四個(gè)區(qū)域，相對(duì)兩個(gè)區(qū)域，代碼寫起來要容易一些。