OI解题基本方法论

· · 个人记录

OI解题基本方法论

引言

oi中的解题可分为三步：
1.分析问题性质
2.转化问题
3.加速求解 本博客将围绕分析问题性质、转化问题、加速求解三个要点总结OI解题的方法论。

目录

第一部分 序列问题

正文

第一部分 序列问题

前缀和

  1. 特性
    • 可以O(1)查询静态区间和；
    • 局限：对前缀和的应用进行拓展时需要注意：拓展运算需要有逆运算，满足结合律。
  2. 应用
    • 可以将区间上问题转化为单点问题，把区间和信息用两个量代替。尤其在斜率优化dp与单调队列优化dp中常见。在这两类dp中用两个值代替区间和可以大大简化状态转移方程。
    • 可以将动态排名问题转化为01序列上的取1问题，用树状数组维护动态前缀和即可

差分

  1. 特性：
    • 原数组的区间加上、减去一个值，在差分数组中只改变两个点；
    • 由增相减损法可得差分数组与原数组中相邻元素gcd相等。
    • 与前缀和互为逆运算
  2. 应用：
    • 可以将对相邻几个元素的操作转化为差分数组上的简单操作（【21NOIP提高组】方差）
    • 也能简化状态转移方程
    • 在需要区间修改的数据结构题中可以简化操作

倍增预处理区间

  1. 特性：
    • 倍增预处理区间后可以用O(log n)时间并凑出答案区间。适用于静态查询。克服前缀和的局限性，在拓展运算中无逆运算时也可使用，只要求满足结合律。min与max满足结合律而无逆运算，所以静态快速查询区间最值时使用倍增预处理st表。
  2. 应用：
    • 加速dp
    • 预处理处理静态序列上特殊运算的值

数据结构优化

离散化

图论问题

拓扑序相关的规划