一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 $10^7 \sim 10^8$ 为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：
- $n \leq 30$：指数级别，适合使用
dfs+剪枝、状态压缩dp - $n \leq 100$：$O(n^3)$，适合
floyd、dp、高斯消元 - $n \leq 1000$：$O(n^2)$ 或 $O(n^2 \log n)$，适合
dp、二分、朴素版Dijkstra、朴素版Prim、Bellman-Ford - $n \leq 10000$：$O(n \sqrt{n})$，适合
块状链表、分块、莫队 - $n \leq 100000$：$O(n \log n)$，适合各种
sort、线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树 - $n \leq 1000000$：$O(n)$，以及常数较小的 $O(n \log n)$ 算法，适合
单调队列、hash、双指针扫描、BFS、并查集、kmp、AC自动机；常数较小的 $O(n \log n)$ 做法包括：sort、树状数组、heap、dijkstra、spfa - $n \leq 10000000$：$O(n)$，适合
双指针扫描、kmp、AC自动机、线性筛素数 - $n \leq 10^9$：$O(\sqrt{n})$，适合
判断质数 - $n \leq 10^{18}$：$O(\log n)$，适合
最大公约数、快速幂、数位DP - $n \leq 10^{1000}$：$O((\log n)^2)$，适合
高精度加减乘除 - $n \leq 10^{100000}$：$O(\log k \times \log \log k)$，其中 $k$ 表示位数，适合
高精度加减、FFT/NTT
补充 1：更细致的时间常数考量（C++ 实际运行效率）
虽然理论上 $10^8$ 操作/秒是常见估计，但实际运行速度受常数影响极大：
| 操作类型 | 近似耗时（纳秒） | 说明 |
|---|---|---|
| 加减乘除（int） | ~1–4 ns | 快 |
取模 %、除法 / |
~10–30 ns | 慢！尽量避免频繁使用 |
| 函数调用（非内联） | ~5–10 ns | 小心递归深 |
STL 容器访问（vector, array） |
~1–2 ns | 连续内存快 |
map 查找 |
~20–50 ns | 哈希冲突或树结构开销 |
unordered_map |
~10–30 ns | 平均快，但最坏 $O(n)$ |
动态内存分配（new / vector::push_back 扩容） |
~50–100+ ns | 避免频繁分配 |
建议：
- 能用数组不用 vector（如果大小固定）
- 能用 unordered_set/map 时注意自定义哈希防卡（防哈希攻击）
- 多重循环中避免 STL 的深层嵌套调用
补充 2：常见时间复杂度的实际可接受操作数（1秒时限，C++）
| 时间复杂度 | 最大约束 $n$ | 典型算法举例 |
|---|---|---|
| $O(n)$ | $10^7 \sim 10^8$ | 扫描、BFS、线性筛 |
| $O(n \log n)$ | $n \leq 10^6$ | 排序、堆、线段树遍历 |
| $O(n \sqrt{n})$ | $n \leq 10^5$ | 分块、莫队（带块大小优化） |
| $O(n \log^2 n)$ | $n \leq 10^5$ | CDQ 分治、整体二分、树套树（卡常） |
| $O(n \sqrt{n} \log n)$ | $n \leq 3 \times 10^4$ | 莫队 + 树状数组 |
| $O(n^2)$ | $n \leq 5000$（紧）~ $10^4$（松） | 朴素 DP、flood fill |
| $O(n^3)$ | $n \leq 300$ ~ $500$ | Floyd、矩阵乘法（未优化） |
| $O(2^n \cdot n^2)$ | $n \leq 20$ | TSP、状态压缩 DP |
| $O(3^n)$ | $n \leq 15$ | 子集枚举类 DP |
注意：
n=1000的 $O(n^3)$ 是 $10^9$，很可能超时，除非常数极小或题目明确允许。
补充 3：空间复杂度限制也要注意！
- 一般内存限制为 256MB 或 512MB
- 一个
int占 4 字节，long long占 8 字节 vector<int>大小为 $10^7$ → 约 40MB- $10^3 \times 10^3$ 的二维数组 → $10^6$ 个元素 →
int为 4MB，double为 8MB - $10^6 \times 10^6$ 数组 不可能（需要 4TB 内存）
建议：
- 避免开过大数组（如 int dp[1000000][100] 是 $10^8$ 个 int → 400MB，超限）
- 使用滚动数组优化空间（如背包问题）
- 能用 int 不用 long long（节省空间 & 缓存友好）
补充 4：特殊场景下的算法选择
| 场景 | 推荐算法 / 技巧 |
|---|---|
| 多次区间查询 + 单点修改 | 树状数组（BIT）比线段树快 |
| 区间修改 + 区间查询 | 线段树（懒标记） |
| 静态区间最值查询 | RMQ（Sparse Table）$O(1)$ 查询，$O(n \log n)$ 预处理 |
| 静态区间第 K 小 | 主席树（可持久化线段树） |
| 图中多源最短路 | Floyd（$n \leq 300$），否则用 $n$ 次 Dijkstra |
| 负权边 | SPFA（已不推荐）、Bellman-Ford、或 Johnson（稀疏图） |
| 大数阶乘 / 组合数取模 | 预处理阶乘 + 逆元（$O(1)$ 查询） |
| 字符串匹配（多模式串） | AC 自动机、后缀数组、SAM（后缀自动机） |
| 动态连通性 | LCT（Link-Cut Tree）、ETT（Euler Tour Tree） |
补充 5：卡常技巧（优化常数）
在 $n=10^6$ 且 $O(n \log n)$ 接近极限时，以下技巧可救命：
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
