一最多的行

【遍歷】找最多1，而矩陣只包含01，即求和最大的行。遍歷每一行，統(tǒng)計一整行的元素和的最大值及其下標。由于是從上到下遍歷行的，所以找到的最大值下標是最小的。

找出可整除性得分最大的整數(shù)

【暴力枚舉】遍歷每個divisors[i]，統(tǒng)計它能被幾個nums[j]整除。出現(xiàn)次數(shù)相等時，保存最小的divisor。

構造有效字符串的最少插入數(shù)

【貪心】用一個i指針遍歷字符串，分類討論，如果是“abc"就移3格，是”ab“、"ac"、"bc"就移2格，其余情況移1格。

【貪心】最終需要一個"abc"的周期字符串，設“abc"的周期為t，需要插入的字符數(shù)=3×t-len(word)。如何求周期——如果后一個字符大于前一個字符，說明需要新增一個周期，t+=1。

【數(shù)學】對于兩個相鄰字母a和b（a在b左邊），使word有效需要插入ord(b) - ord(a) - 1個字母（比如"ac"需要補一個"b"，"ca"不需要補）。防止負數(shù)，寫成(ord(b) - ord(a) - 1 + 3) mod 3。

最小化旅行的價格總和

【DFS】數(shù)據(jù)范圍較小，對每個trips[i]跑一遍dfs，把從start到end路徑上點x的經(jīng)過次數(shù)cnt[x]都加1。計算每個點被經(jīng)過的次數(shù)，更新price[i]為price[i]×cnt[i]，問題變?yōu)橛嬎銣p半后的price[i]之和的最小值。從任意節(jié)點出發(fā)DFS（如節(jié)點0），對于節(jié)點x和其兒子y，分類討論：price[x]不變，那么price[y] 可以減半或不變，取最小值；如果price[x]減半，price[y]只能不變。因此子樹x需要返回兩個值：price[x]不變時子樹x的最小價值總和，price[x]減半時的子樹 x 的最小價值總和。

【Tarjan 離線 LCA + 樹上差分】利用樹上差分打標記，再通過一次 DFS 算出 cnt值。從x = start到y(tǒng)=end的路徑可以視為從x向上到某個點“拐彎”，再向下到達y，這個拐點就是x和y的LCA。把路徑視為x-lca'-lca-y，其中l(wèi)ca'是lca的兒子，由于更新的是點，拆分成x-lca'和y-lca，那么自底向上更新差分diff值，對于x-lca'，更新diff[x]+=1，diff[lca] -= 1，對于y-lca，更新diff[y]+=1,diff[father[lca]] -=1。LCA可以用tarjan離線算法計算，再dfs，歸的過程中累加diff，計算cnt。