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

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

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

$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，二分。
$n \leq 10^4$ , $O(n \times \sqrt n)$ ，块状链表
$n \leq 10^5$ , $O(n \log n)$ ，各种sort，线段树、树状数组、set/map、heap、Dijkstra+heap、SPFA、求凸包、求半平面交、二分
$n \leq 10 ^ 6$ , $O(n)$ , 以及常数较小的 $O(n \log n)$ ，hash、双指针扫描、kmp、AC自动机，常数比较小的 $O(n \log n)$ ：sort、树状数组、heap、Dijkstra、SPFA
$n \leq 10^7$ , $O(n)$ ，双指针扫描、kmp、AC自动机、线性筛素数
$n \leq 10^ 9$ , $O(\sqrt n)$ ，判断质数
$n \leq 10^ {18}$ ， $O(\log n)$ ，最大公约数。

在写题的之前一定要先判断时间复杂度，写写伪代码。

还有一种常见的形式是交互式类型的题目，通常会限定查询次数:

需要熟悉一般数据范围对应对数： $$ \log _2 10 \approx 3.32 \ \log _2 10^4 \approx 13.29 \ \log _2 10^5 \approx 16.61 \ \log _2 10^6 \approx 19.93 $$