根据数据范围判断算法

蓝桥杯的评测机子和蓝桥云课的机子基本上一样的，速度大概在一秒 \(5\times 10^8\)

\(10^{18}\)

对单个数字的操作时间复杂度就只能在 \(O(1)\) 或者 \(O(\log)\)

如果是 \(O(1)\) 就说明这个题一定是一个数学题或者找规律题。

如果是 \(O(\log)\) 最大公约数是 \(\log\) 级别的算法，二分答案是 \(\log\times \text{check}\) 的算法。

算出一个数字的阶乘多少个因子（阶乘尾 0）

LL res=0;
while(x){
    res=res+x/5;
    x/=5;
}

如果有规律：则需要多分析很多数字来确认答案（暴力打表，看看哪些数字符合）

\(10^{12}\)

对单个数字的操作时间复杂度在之前的基础上，我们多了 \(\sqrt{N}\)

判断单个素数，枚举约数、分解质因数，数论分块（比较难）

\(10^{7}\)

\(O(n)\) 级别的算法。

枚举、前缀和（快速求出区间和）、差分（快速做区间修改）、双指针（快速求解区间问题）、栈（有特殊性质）、队列（有特殊性质）、并查集（不相交集合的并问题）、桶数组（值域要小）、unordered_map（无序哈希表，蓝桥杯很难被卡）、线性动态规划、字符串哈希（将字符串转换成数值快速判两个字符串是否相等）、BFS（ \(O(n+m)，点数+边数\)（解决最小操作次数问题，且每个操作代价相同）），随机数据下的 spfa

有一些特殊的链表题（将编号为 \(x\) 的移动到编号为 \(y\) 的节点前面或者后面）

\(10^{6}\)

\(O(n\log n)\)

排序（一个序列变得有序）、序列二分（有序序列中找到第一个 >= 或 > 的第一个数字）、素数筛法（求解 \(1\sim n\) 中的素数、线段树（区间修改、区间查询）、最小生成树 \((\text{n 个点 n-1 条边的最小路径})\)、Dijkstra（求 \(1\sim n\) 的最短路）、优先队列（取出序列中的最值）

\(2\times 10^{5}\)

\(O(n\sqrt{n})\)

分块（被线段树平替了）

\(10^4\)

\(O(n^2)\)

二维前缀和（求出以 \(x_1,y_1\) 为左上角，\(x_2,y_2\) 为右下角子矩阵的和）、二维差分（对 \(x_1,y_1\) 为左上角，\(x_2,y_2\) 为右下角子矩阵进行快速修改）

背包问题

\(500\)

\(O(n^3)\)

Floyd（求出任意两点之间的最短路）

矩阵乘法（优化动态规划）

DFS

20

搜索

子集枚举 \(O(n\times 2^n)\)：列出一个序列的全部子序列、选或不选、删或不删

组合型枚举 \(O(\dfrac{2^n}{\sqrt{n}})\)：列出一个序列中选出 \(k\) 个数字的全部方案

12

全排列 \(n\times n!\)：将一个序列的全部排列输出

还有一些其他的搜索方式，具体要看实现。