由数据范围反推算法复杂度以及算法内容

一般ACM或笔试题的时间限制是 1秒/2秒。
在这种情况下，C++代码的操作次数控制在 10^7 ~ 10^8 最佳。

在不同的数据范围下，代码的时间复杂度与算法的选择：

  1. n ≤ 30 ⇒ 指数级别
    dfs + 剪枝
    状态压缩dp
  2. n ≤ 100 ⇒ O(n³)
    Floyd
    DP
    高斯消元
  3. n ≤ 1000 ⇒ O(n²) / O(n²logn)
    DP
    二分
    朴素版Dijkstra
    朴素版Prim
    Bellman-Ford
  4. n ≤ 10000 ⇒ O(n * √n)
    块状链表
    分块
    莫队
  5. n ≤ 100000 ⇒ O(nlogn)
    各种sort
    线段树
    树状数组
    set/map
    heap
    拓扑排序
    Dijkstra + heap
    Prim + heap
    Kruskal
    spfa
    求凸包
    求半平面交
    二分
    CDQ分治
    整体二分
    后缀数组
    树链剖分
    动态树
  6. n ≤ 10⁶ ⇒ O(n) / 常数较小的O(nlogn)算法
    单调队列
    hash
    双指针扫描
    并查集
    KMP
    AC自动机
    常数较小的O(nlogn)算法有：sort，树状数组，heap，Dijkstra，spfa
  7. n ≤ 10⁷ ⇒ O(n)
    双指针扫描
    KMP
    AC自动机
    线性筛素数
  8. n ≤ 10⁹ ⇒ O(√n)
    判断质数
  9. n ≤ 10¹⁸ ⇒ O(logn)
    最大公约数
    快速幂
    数位DP
  10. n ≤ 10¹⁰⁰⁰，O((logn)²)
    高精度加减乘除
  11. n ≤ 10¹⁰⁰⁰⁰⁰，O(logk * loglogk)
    k表示数位，高精度加减
    FFT/NTT