算法"/>
常用代码模板2——基础算法
构思算法：可以先想暴力解法，然后观察时间复杂度，如果超时，再考虑优化，优化的方向就是时间复杂度要下降，下表可以给出一些算法选择的参考：
暴力枚举 -> 枚举+优化 -> 正解
| 数据范围 | 时间复杂度 | 考察的算法 |
|---|---|---|
| n \leq 30n≤30 | 指数级别 | dfs+剪枝，状态压缩dp |
| n\leq10^2n≤102 | O(n^3)O(n3) | floyd，dp |
| n\leq10^3n≤103 | O(n^2),O(n^2\log n)O(n2),O(n2logn) | dp，二分，朴素版Dijkstra，朴素版Prim，Bellman-Ford |
| n\leq10^4n≤104 | O(n*\sqrt{n})O(n∗n) | 块状链表，分块，莫队 |
| n\leq10^5n≤105 | O(n\log n)O(nlogn) | 各种sort，线段树，树状数组，set/map，heap，拓扑排序，dijkstra+heap，prim+heap，spfa，二分 |
| n\leq10^6n≤106 | O(n)O(n),常数较小的 O(n\log n)O(nlogn)算法 | hash，双指针扫描，并查集，常数较小的 O(n\log n)O(nlogn)算法：sort，树状数组，ST表，heap，dijkstra，spfa |
| n\leq10^7n≤107 | O(n)O(n) | 双指针扫描，线性筛素数 |
| n\leq10^9n≤109 | O(\sqrt{n})O(n) | 判断质数 |
| n\leq10^{18}n≤1018 | O(\log n)O(logn) | 最大公约数，快速幂 |
| n\leq10^{1000}n≤101000 | O((\log n)^2)O((logn)2) | 高精度加减乘除 |
备注：\log nlogn 主要出现在二分、分治和树、图中。
素数判定
试除法
// 试除法：判断一个整数 i 是不是素数，是则返回 true，否则返回 false
bool isprime(int i){if(i < 2)return false;for(int j = 2; j <= sqrt(i); j++)if(i % j == 0)return false;return true;
}
Copy
埃氏筛法
const int N = 100000; // N 的大小取决于问题中 n 的范围
bool a[N]; // 标记数组 a[i] = 0(false):素数，a[i]=1(true): 非素数
// 埃氏筛法 函数执行完后 a[] 数组即为筛出的素数结果 a[i]=false 表示 i 是素数
void prime()
{a[0]=a[1]=true; // 0 和 1 不是素数for(int i = 2; i <= n; i++){if(a[i] == false) // i 是素数{for(int j = i+i; j <= n; j += i)a[j] = true;}}
}
Copy
例题：素数距离 - TopsCoding
质因数分解
int t = 2;
while(k!=1){while(k%t == 0) {k /= t;cout << t << ' ';}t++;
}
Copy
递推
数学中的斐波那契数列、错排问题的递推公式、等差数列、等比数列问题，都可以用递推去解决。
在编程中，计算问题的解时，如果可以找到前后过程之间的数量关系（即递推式），那么就可以用递推去解决。
f[i] = g(f[i-1],f[i-2],...,f[1])f[i]=g(f[i−1],f[i−2],...,f[1])
int f[N] = {部分初始值};
for(int i = 2; i <= n; i++)
{f[i] = ...f[i-1]...f[i-2]...;
}
cout << f[n];
Copy
例题：小 C 的数
更多推荐
常用代码模板2——基础算法
发布评论