1.
換模版了,聽說卡了 SA
正解是線性的
看題解里還有 log 的倍增哈希,學(xué)到了
正解暴力比較兩個字符串第一位不同,這樣劣的那個字符串,以其每一個字符起始的字符串都劣,同樣會被優(yōu)的那個的相同位置代替
所以就可以直接跳過
每一步都不是無效的,所以是線性的
2.
用整體二分
內(nèi)部求矩形和用二維樹狀數(shù)組就行了
3.
整體二分板子題算是
因為連回退都不用
有推論
- 點集多加一個點 \(c\) ,設(shè)原來直徑為 \(a , b\)
那么新的直徑還在他們中間,重新算一下就行
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)記就行
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\) 夠了
6.
板紙
先套個 wps 二分
然后就是最小生成樹
但是是兩個 log
可以開始對邊拍一遍序就一個 log 了
然后判無解是個難點,考慮合法的 k 是一段區(qū)間
因此先跑出合法區(qū)間即可,就是先把二分的 \(inf , -inf\) check 一下
浙公網(wǎng)安備 33010602011771號