數(shù)組中不等三元組的數(shù)目

【暴力】考試專用三重for循環(huán)。

也可以調(diào)庫。

【排序 + 枚舉】排序后aabbbc。枚舉中間的數(shù)x，x對(duì)答案的貢獻(xiàn)為小于x的數(shù) × 等于x的數(shù) × 大于x的數(shù)，統(tǒng)計(jì)三部分的個(gè)數(shù)。 記a開頭idx = start，計(jì)最后一個(gè)b的idx = i，計(jì)第一個(gè)c的idx = n - 1- i。

【容斥原理】

二叉搜索樹最近節(jié)點(diǎn)查詢

【中序遍歷 + 二分查找】因?yàn)轭}目沒說BST是平衡的，最壞情況會(huì)退化成鏈，所以不需要在二叉搜索樹上找，可以中序遍歷一次，把所有值取出來，得到一個(gè)有序數(shù)組，直接二分。

到達(dá)首都的最少油耗

【DFS】把一升油耗看作消耗一輛車，求返回首都最少的總車數(shù)（車流量）。設(shè)子樹大小為size，則至少需要?size/seats?輛車。

完美分割的方案數(shù)

【DP + 前綴和優(yōu)化】定義f[i] [j]為把s的前j個(gè)字符分割成i段的方案數(shù)，定義j為分割點(diǎn)，等價(jià)于s[j]不是指數(shù)且s[j + 1]是指數(shù)，j是分割點(diǎn)則考慮枚舉第i-1段和第i段的分割點(diǎn)j - l。需u滿足l ≥ minlength。累加所有f[i-1] [j - l]。加上剪枝和前綴和優(yōu)化。