1.
P13270 【模板】最小表示法
换模版了，听说卡了 SA
正解是线性的
看题解里还有 log 的倍增哈希，学到了
正解暴力比较两个字符串第一位不同，这样劣的那个字符串，以其每一个字符起始的字符串都劣，同样会被优的那个的相同位置代替
所以就可以直接跳过
每一步都不是无效的，所以是线性的
AC
2.
P1527 [国家集训队] 矩阵乘法
用整体二分
内部求矩形和用二维树状数组就行了
AC
3.
P2056 [ZJOI2007] 捉迷藏
整体二分板子题算是
因为连回退都不用
有推论
- 点集多加一个点 \(c\) ，设原来直径为 \(a , b\)
那么新的直径还在他们中间，重新算一下就行
AC
4.
P11598 [NOISG 2018 Finals] Safety
slope trick 经典题目
考虑 dp \(f[i][j]\) 为前 \(i\) 个，以 \(j - h \le x \le j + h\) 的数结尾最优是多少
转移 \(f[i][j] = min(f[i - 1][k] + |k - a[i]|)_{j - h \le k \le j + h}\)
相当于是先加一个绝对值函数，然后再从最低点向两边拉 \(h\) ，这个东西优先队列很好维护，平移就打标记就行
AC
5.
P5308 [COCI 2018/2019 #4] Akvizna
考虑先套 wqs 二分后，写出 dp 柿子
\(f[i][j] = min(f[k][j - 1] + \frac{i - k}{n - k} )\)
看着不像斜优 ？
不好意思，我已经开挂了，先看标签再做题
考虑如何化成斜优的柿子
\(\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\) 有关，前一项是 \(i k\) 乘积形式
套斜优就行了
不过记得精度开大点 \(eps = 1e-12\) 够了
AC
6.
P5633 最小度限制生成树
板纸
先套个 wps 二分
然后就是最小生成树
但是是两个 log
可以开始对边拍一遍序就一个 log 了
然后判无解是个难点，考虑合法的 k 是一段区间
因此先跑出合法区间即可，就是先把二分的 \(inf , -inf\) check 一下
AC