基础优化技巧1
三分
求单峰函数极值点
丢弃极值点一定不在的点，注意不能用于非严格单调的函数。
由于区间长度可以随便取，可以把分段点取得很近，这个时候就相当于二分斜率
前面比0大，极值点处等于0，后面小于0
01分数规划
略。模型特征：
-
答案是比率形式（取对数可以把根式和次方转换为乘法，有时有用）
-
比率上下项数相同或者可以拆成项数相同的
整体二分
例子：MET-Meteors
若对一个国家来说，直接二分（虽然只有一个国家的时候不需要二分），在每一次检验的时候其实不止能求出一个国家是否满足，而是可以求出所有国家是否满足，则考虑把所有国家一起二分，节省时间。
分治
复杂度分析：按层分析
-
CDQ 多维限制，偏序问题
-
矩形问题：按长边分裂，即添加限制以简化问题，分裂成两半就能确定跨越的点对必须经过中间
-
启发式分裂：涉及到点对中间的极值，考虑用极值进行一个划分，然后处理小的那一段对大的那一段的贡献。复杂度只会跟小的那边相关。
例子:CF1156E，维护一个 map 每次递归传参数，然后在总共的 map 里去掉小的那一段得到大的那一段，这样就可以计算了。（当然此题维护uset是OK的）
-
分治的位置，是可以自己选的，你可以自己选择特殊点进行限制的施加。
倍增
-
通过预处理 \(2^k\) 长度的信息然后合并
-
可重复贡献：对于满足可重复贡献的信息，即重复部分合并对信息没有影响，如 gcd/线性基，此时可以使用倍增。
哈希
-
将对象映射成为一个数，作为判重、判相等、判存在、用于 dp 下标
-
字符串哈希：保留需要的特征，不要保留不要的特征，不要用自然溢出，可以随机base加双模数
-
随机赋权然后异或哈希：
ABC250E
Trie
-
支持查询字符串是否出现
-
支持反映两个字符串的前后缀关系
-
LCA on Trie == LCP
-
例子:
First!G：发现可以一一确定每个串是不是最小串，建立偏序关系为图，判断是否全部偏序关系都可成立，即是否有topo序，即是否有环。
-
求异或最小生成树：在Trie上的每一个点，假如我们已经合并了左边、右边子树里面的所有数，现在要把左边右边合并起来，我们肯定要找两个 lcp 尽可能长的合并，那显然就是从左边右边各找一个数进行合并，我们只要遍历较小那一边的数，在右边查找smallest xor pair 即可。这本身就是 MST 的 Boruvka 算法。
KMP
-
性质：一个 i ，其 border 是由 next[next[i]],next[next[next[i]]] 等推到来的
-
失配树：若链接 \(i\to next[i]\) 则构成树。此时从 \(i\) 到根的链给出 \(i\) 的所有 border，则 lca 是最长公共 border
-
KMP 自动机：在一个单字符串上的 AC 自动机。转移指针定义为
\[\text{trans}_{i,c} = \begin{cases} i + 1, & \text{if }b_{i} = c \\[2ex] \text{trans}_{\text{next}_{i},c}, & \text{otherwise} \end{cases} \]这也给出了构建方案。
-
TD HNOI 2019 JoJo
-
例子：GT考试：容易想到 dp，考虑到不吉利数字很短，转移也只有到下一层的，层数很大，可以尝试矩阵优化，然后就比较简单。