1.

P13270 【模板】最小表示法

換模版了，聽說卡了 SA

正解是線性的

看題解里還有 log 的倍增哈希，學(xué)到了

正解暴力比較兩個字符串第一位不同，這樣劣的那個字符串，以其每一個字符起始的字符串都劣，同樣會被優(yōu)的那個的相同位置代替

所以就可以直接跳過

每一步都不是無效的，所以是線性的

AC

2.

P1527 [國家集訓(xùn)隊] 矩陣乘法

用整體二分

內(nèi)部求矩形和用二維樹狀數(shù)組就行了

AC

3.

P2056 [ZJOI2007] 捉迷藏

整體二分板子題算是

因為連回退都不用

有推論

• 點集多加一個點 \(c\) ，設(shè)原來直徑為 \(a , b\)
  那么新的直徑還在他們中間，重新算一下就行

AC

4.

P11598 [NOISG 2018 Finals] Safety

slope trick 經(jīng)典題目

考慮 dp \(f[i][j]\) 為前 \(i\) 個，以 \(j - h \le x \le j + h\) 的數(shù)結(jié)尾最優(yōu)是多少

轉(zhuǎn)移 \(f[i][j] = min(f[i - 1][k] + |k - a[i]|)_{j - h \le k \le j + h}\)

相當(dāng)于是先加一個絕對值函數(shù)，然后再從最低點向兩邊拉 \(h\) ，這個東西優(yōu)先隊列很好維護，平移就打標(biāo)記就行

AC

5.

P5308 [COCI 2018/2019 #4] Akvizna

考慮先套 wqs 二分后，寫出 dp 柿子

\(f[i][j] = min(f[k][j - 1] + \frac{i - k}{n - k} )\)

看著不像斜優(yōu) ？

不好意思，我已經(jīng)開掛了，先看標(biāo)簽再做題

考慮如何化成斜優(yōu)的柿子

\(\frac{i - k}{n - k} = \frac{i}{n - k} - \frac{k}{n - k} = i \times \frac{1}{n - k} - \frac{k}{n - k}\)

e...

沒了 ？

確實沒了

后一項只和 \(k\) 有關(guān)，前一項是 \(i k\) 乘積形式

套斜優(yōu)就行了

不過記得精度開大點 \(eps = 1e-12\) 夠了

AC

6.

P5633 最小度限制生成樹

板紙

先套個 wps 二分

然后就是最小生成樹

但是是兩個 log

可以開始對邊拍一遍序就一個 log 了

然后判無解是個難點，考慮合法的 k 是一段區(qū)間

因此先跑出合法區(qū)間即可，就是先把二分的 \(inf , -inf\) check 一下

AC