排序
1. 快速排序
void quick_sort(int a[], int l, int r){
if (l >= r) return ;
int i = l, j = r, x = a[l + r >> 1];
while(i <= j){
while(a[i] < x) i ++;
while(a[j] > x) j --;
if(i < j){
swap(a[i], a[j]);
i ++;
j --;
}
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}
2. 归并排序
void merge_sort(int a[], int l, int r){
if (l >= r) return ;
int m = l + r >> 1;
merge_sort(a, l, m);
merge_sort(a, m + 1, r);
int k = 0; // 记下标
int i = l, j = m + 1; // 归并范围
while(i <= m && j <= r){
if(a[i] <= a[j])
tmp[k ++] = a[i ++];
else
tmp[k ++] = a[j ++];
}
while(i <= m) tmp[k ++] = a[i ++];
while(j <= r) tmp[k ++] = a[j ++];
for(i = l, j = 0; i <= r; i++, j++) // l-r
a[i] = tmp[j];
}
_3. 冒泡排序 _
void normSort(int a[], int l, int r){
for(int i = l; i <= r; i ++)
for(int j = i +1; j <= r; j ++)
if(a[i] > a[j])
swap(a[i], a[j]);
}
二分搜索
1. 整数二分
bool check(int x){
return true;
}
int blsearch(int l, int r){
while(l < r){
int m = l + r >> 1;
if(check(m))
r = m;
else
l = m + 1;
}
return l;
}
int brsearch(int l, int r){
while(l < r){
int m = l + r + 1 >> 1;
if(check(m))
l = m;
else
r = m - 1;
}
return l;
}
2. 浮点数二分
bool check(double x){
return true;
}
double fsearch(double l, double r){
while(r - l > 1e-6){ // 保证精度
double m = (l + r) / 2
if(check(m))
r = m;
else
l = m;
}
return l;
}
高精度运算
1. 加法
vector<int> add(vector<int> &A, vector<int> &B){
// 让A长度大于B长度便于统一操作
if(A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for(int i = A.size() - 1; i >= 0; i --){
t += A[i];
if(i < B.size()) t += B[i];
// 大于10之后 进行取余运算
C.push_back(t % 10);
t /= 10; // 进位
}
// 两个数相加之后越界之前的长度情况
if(t)
C.push_back(t);
reverse(C.begin(), C.end());
return C;
}
2. 减法
vector<int> sub(vector<int> &A, vector<int> &B){
vector<int> C;
int t = 0;
for(int i = A.size() - 1; i >= 0; i --){
t = A[i] - t; // 存储被减数的值,同时被减数可能会被之前的数借位
if(i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if(t < 0) // 要借位
t = 1;
else // 不借位
t = 0;
}
while(C.size() > 0 && C.back() == 0) // 消除开始为0位置
C.pop_back();
reverse(C.begin(), C.end());
return C;
}
3. 乘法
vector<int> mul(vector<int> &A, int b){
vector<int> C;
int t = 0;
for(int i = A.size() - 1; i >= 0; i --){
t += A[i] * b;
// 大于10之后 进行取余运算
C.push_back(t % 10);
t /= 10; // 进位
}
if(t)
C.push_back(t);
reverse(C.begin(), C.end());
return C;
}
4. 除法
vector<int> div(vector<int> &A, int b, int &r){
// A-被除数 b-除数 r-余数
vector<int> C;
r = 0;
for(int i = 0; i < A.size(); i ++){
// 放大并且加上后一位便于相除
r = r * 10 + A[i];
// 存放除数
C.push_back(r / b);
// 存放余数用于后续计算
r %= b;
}
reverse(C.begin(), C.end());
while(C.size() > 0 && C.back() == 0)
C.pop_back();
reverse(C.begin(), C.end());
return C;
}
前缀和
1. 一维前缀和
int preSumOne(int l, int r){
for(int i = 1; i <= n; i++){
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
// L~R的前缀和为
return s[r] - s[l - 1];
}
2. 二维前缀和
int preSumTwo(int x1, int y1, int x2, int y2){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> a[i][j];
// 根据1的个数来判断符号
// 前缀奇正偶负
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
}
// 答案反着来, 减一常二,xy取同维
int ans = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1]
// 二维同三维
return ans;
}
3. 三维前缀和
pre_sum[i][j][k] =
arr[i][j][k]
+ pre_sum[i-1][j][k]
+ pre_sum[i][j-1][k]
+ pre_sum[i][j][k-1]
- pre_sum[i-1][j-1][k]
- pre_sum[i-1][j][k-1]
- pre_sum[i][j-1][k-1]
+ pre_sum[i-1][j-1][k-1];
差分数组
1. 一维差分
void difference(){
scanf("%d%d", n, m);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
// 差分数组
for(int i = 1; i <= n; i++)
df[i] = a[i] - a[i - 1];
// 修改差分数组
while(m --){
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
df[l] += c;
df[r + 1] -= c;
}
// 通过差分数组恢复
for(int i = 1; i <= n; i++)
a[i] = df[i] + a[i - 1];
}
2. 二维差分
/**
二维差分
给以(x1, y1)为左上角,
(x2, y2)为右下角的子矩阵中的所有元素加上c
*/
df[x1][y1] += c;
df[x2 + 1][y1] -= c;
df[x1][y2 + 1] -= c;
df[x2 + 1][y2 + 1] += c;
区间操作
1. 离散
vector<int> alls;
// 去重时候需要先排序
sort(alls.begin(), alls.end());
// 去除重复元素
alls.erase(unique(alls.begin()), alls.end(), alls.end());
int find(int x){
int l = 0, r = alls.size() - 1;
while(l < r){
int m = l + r >> 1;
if(alls[m] >= x)
r = m;
else
l = m + 1;
}
return l + 1;
}
2. 合并
void merge(vector<PII> &segs){
vector<PII> tmp; // 临时数组存放合并的结果
// 排序原数组
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9
// 遍历每个数组
for(auto seg : segs){
if(ed < seg.first){ // 区间无重合
if(st != -2e9){ // 非默认区间 就添加之前的区间
tmp.push_back({st, ed});
}
st = seg.first, ed = seg.second; // 存放当前正在访问的区间
}
else if(ed < seg.second){ // 区间有重合
ed = seg.second; // 更新ed用于下次存放
}
}
// 遍历完之后直接添加最后的区间即可
tmp.push_back({st, ed});
segs = tmp;
}
链表
1. 单链表
void sLinkNode(){
// 单链表
int head, idx;
int e[N], ne[N];
// 初始化
void init(){
head = -1;
idx = 0;
}
// 插入元素a,使用头插法
void insert(int a){
e[idx] = a;
ne[idx] = head;
head = idx;
idx ++;
}
// 移除头结点
void remove(){
head = ne[head];
}
}
2. 双链表
void dLinkNode(){
// e[]表示节点的值,l[]表示节点的左指针,r[]表示节点的右指针,idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
void init(){
r[0] = 1, l[1] = 0;
idx = 2;
}
void insert(int a, int x){
// 存放元素
e[idx] = x;
/**
before: a -> o
a <- o
after: a <- x -> o
a -> x <- o
*/
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++;
}
void remove(int a){
l[r[a]] = l[a];
r[l[a]] = r[a];
}
}
树和图
1. 构建
void create(){
int idx;
int h[N], e[N], ne[N];
void init(){
idx = 0;
memset(h, -1, sizeof h);
}
void add(int a, int b){
e[idx] = b; // 存放节点
ne[idx] = h[a]; // 节点下一个位置 初始是-1
h[a] = idx; // 存放下标用于访问ne和e
idx ++;
}
}
2. 深度优先
void dfs(int u){
// 表示当前节点被访问过
st[u] = true;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(!st[j])
dfs(j);
}
}
3. 广度优先
void bfs(){
queue<int> q;
st[1] = true;
q.push(1);
while(q.size()){
// 取队列首
int t = q.front();
// 出队
q.pop();
for(int i = h[t]; i != -1; i = ne[i]){
j = e[i]; // 取出当前元素
if(!st[j]){
// 标记为访问
st[j] = true;
// 入队
q.push(j);
}
}
}
}
4. dijkstra
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(){
// 初始化dist数组
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i < n; i ++){
// 在还未确定的点 寻找与他相连的最短距离的点
int t = -1;
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
// 用t更新其他距离
for(int j = 1; j <= n; j ++){
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
// 给当前标记为访问过
st[t] = true;
}
if(dist[n] == 0x3f3f3f)
return -1;
return dist[n];
}
5. Prim
int g[N][N];
int dist[N];
bool st[N];
int prim(){
memset(dist, 0x3f, sizeof dist);
int res = 0;
for(int i = 1; i < n; i++){
int t = -1;
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || dist[t] > dist[i]))
t = j;
}
if(i && dist[t] == INF)
return INF;
if(i)
res += dist[t];
st[t] = true;
for(int j = 1; j <= n; j ++)
dist[j] = min(dist[j], g[t][j]);
}
return res;
}
树状数组
int lowbit(int x)//-x=(~x+1) 也就是x的每一位二进制数先取反,然后再加上 1
{
return x&-x;
}
void add(int x,int v)//这个函数用于更新 c 数组
{
for(int i=x;i<=32001;i+=lowbit(i))c[i]+=v;//更新一下树状数组
}
int query(int x)//这个函数用于计算前缀和
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))res+=c[i];//计算一下前缀和
return res;
}
线段树
int w[N];//记录一下权重
struct node
{
int l,r;//左右区间
int sum;//总和
}tr[N*4];//记得开 4 倍空间
void push_up(int u)//利用它的两个儿子来算一下它的当前节点信息
{
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;//左儿子 u<<1 ,右儿子 u<<1|1
}
void build(int u,int l,int r)/*第一个参数,当前节点编号,第二个参数,左边界,第三个参数,右边界*/
{
if(l==r)tr[u]={l,r,w[r]};//如果当前已经是叶节点了,那我们就直接赋值就可以了
else//否则的话,说明当前区间长度至少是 2 对吧,那么我们需要把当前区间分为左右两个区间,那先要找边界点
{
tr[u]={l,r};//这里记得赋值一下左右边界的初值
int mid=l+r>>1;//边界的话直接去计算一下 l + r 的下取整
build(u<<1,l,mid);//先递归一下左儿子
build(u<<1|1,mid+1,r);//然后递归一下右儿子
push_up(u);//做完两个儿子之后的话呢 push_up 一遍u 啊,更新一下当前节点信息
}
}
int query(int u,int l,int r)//查询的过程是从根结点开始往下找对应的一个区间
{
if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;//如果当前区间已经完全被包含了,那么我们直接返回它的值就可以了
//否则的话我们需要去递归来算
int mid=tr[u].l+tr[u].r>>1;//计算一下我们 当前 区间的中点是多少
//先判断一下和左边有没有交集
int sum=0;//用 sum 来表示一下我们的总和
if(mid>=l)sum+=query(u<<1,l,r);//看一下我们当前区间的中点和左边有没有交集
if(r>=mid+1)//看一下我们当前区间的中点和右边有没有交集
sum+=query(u<<1|1,l,r);
return sum;
}
void modify(int u,int x,int v)//第一个参数也就是当前节点的编号,第二个参数是要修改的位置,第三个参数是要修改的值
{
if(tr[u].l==tr[u].r)tr[u].sum+=v; //如果当前已经是叶节点了,那我们就直接让他的总和加上 v 就可以了
//否则
else
{
int mid=tr[u].l+tr[u].r>>1;
//看一下 x 是在左半边还是在右半边
if(x<=mid)modify(u<<1,x,v);//如果是在左半边,那就找左儿子
else modify(u<<1|1,x,v);//如果在右半边,那就找右儿子
//更新完之后当前节点的信息就要发生变化对吧,那么我们就需要 pushup 一遍
push_up(u);
}
}
素数
1. 判断素数
bool is_prime(int x){
if(x < 2) return false;
for(int i = 2; i <= x / i; i ++)
if(x % i == 0)
return false;
return true;
}
2. 朴素筛素数
int primes[N];
int cnt;
bool st[N];
void getPrimes(int n){
for(int i = 2; i <= n; i++){
if(st[i])
continue;
primes[cnt ++] = i;
for(int j = i + i; j <= n; j += i){
st[j] = true;
}
}
}
3. 线性筛素数
int primes[N];
int cnt;
bool st[N];
void getPrimes(int n){
for(int i = 2; i <= n ; i ++){
if(!st[i]) primes[cnt ++] = i;
for(int j = 0; i * primes[j] <= n; j ++){
st[primes[j] * i] = true;
if(i % primes[j] == 0)
break;
}
}
}
4. 分解质因数
void divide(int x){
for (int i = 2; i <= x / i; i ++ ){
if (x % i == 0){
int s = 0;
while (x % i == 0)
x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
}
if (x > 1)
cout << x << ' ' << 1 << endl;
cout << endl;
}
约数
1. 约数
vector<int> getDivisors(int x){
vector<int> tmp;
for(int i = 1; i <= x / i; i ++){
if(x % i == 0){
tmp.push_back(i);
if(i != x / i)
tmp.push_back(x / i);
}
}
sort(tmp.begin(), tmp.end());
return tmp;
}
int mian(){
cin >> n;
vector<int> ans;
ans = getDivisors(n);
for(auto ai : ans)
cout << ai << " ";
}
2. 质约数个数
const int mod = 1e9 + 7;
unordered_map<int, int> h;
void getDiv(int x){
for(int i = 2; i <= x / i; i ++){
while(x % i == 0){
x /= i;
h[i] ++;
}
}
if(x > 1)
h[x] ++;
}
int main(){
int n;
cin >> n;
while(n --){
int x;
cin >> x;
getDiv(x);
}
LL ans = 1;
for(auto hi : h)
ans = ans * (hi.second + 1) % mod;
cout << "约数个数:" << ans << endl;
return 0;
}
3. 质约数之和
const int mod = 1e9 + 7;
unordered_map<int, int> h;
void getDiv(int x){
for(int i = 2; i <= x / i; i ++){
while(x % i == 0){
x /= i;
h[i] ++;
}
}
if(x > 1)
h[x] ++;
}
int main(){
int n;
cin >> n;
while(n --){
int x;
cin >> x;
getDiv(x);
}
LL res = 1;
for(auto hi : h){
int pi = hi.first, ci = hi.second;
// 每个数的括号内容 (pi^0 + pi^1 + .. + pi^ci)
LL t = 1;
while(ci --)
t = (1 + t * pi) % mod;
// 多个数之间运算
res = res * t % mod;
}
cout << "约数之和:" << res << endl;
return 0;
}
快速幂
int qmi(int q, int k, int p){
// ans = m ^ k mod p
int ans = 1 % p;
int t = m;
while(k){
if(k & 1)
ans = ans * t % p;
t = t * t % p;
k >>= 1;
}
}
欧几里得
1. 欧几里得
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
2. 扩展欧几里得
// ax + by = exgcd(a, b)
int exgcd(int a, int b, int &x, int &y){
if(!b){
x = 1, y = 0;
return a;
}
int gcd, x1, y1;
gcd = exgcd(b, a % b, x1, y1);
x = y1,
y = x1 - (a / b) * y1;
return gcd;
}
组合
1. 简单组合
int c[N][N];
void getC(){
// 时间复杂度 n ^ 2 c[a][b] 表示从a个苹果中选b个的方案数
for(int i = 0; i < N; i ++){
for(int j = 0; j <= i; j ++)
if(!j)
c[i][j] = 1;
else
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
2. 逆元组合
int fact[M], infact[M];
int qmi(int a, int k, int p){
int ans = 1 % p;
while(k){
if(k & 1)
ans = (LL)ans * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return ans;
}
void getCPlus(){
// O(a * log(mod))
//乘法逆元定义,a/b≡a×xa/b≡a×x (mod(mod m)m),其中x称为b的模m的乘法逆元,x=b?1x=b?1;b,m互质。
fact[0] = 1;
infact[0] = 1;
for(int i = 1; i < N; i ++){
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
}
日期操作
int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check(int date){
int y = date / 10000;
int m = date % 10000 / 100;
int d = date % 100;
if(m > 12 || m == 0 || d == 0)
return false;
if(m != 2 && d > months[m])
return false;
if(m == 2){
int flag = y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
if(d > 28 + flag)
return false;
}
return true;
}
n≤30, 指数级别, dfs+剪枝,状态压缩dp
n≤100 => O(n^3),floyd,dp,高斯消元
n≤1000 => O(n^2),O(n2logn)O(n2logn),dp,二分,朴素版Dijkstra、朴素版Prim、Bellman-Ford
n≤10^4 => O(n√n),块状链表、分块、莫队
n≤10^5 => O(nlogn) => 各种sort,线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
n≤10^6 => O(n), 以及常数较小的 O(nlogn)O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集,kmp、AC自动机,常数比较小的 O(nlogn)O(nlogn) 的做法:sort、树状数组、heap、dijkstra、spfa
n≤10^7 => O(n),双指针扫描、kmp、AC自动机、线性筛素数
n≤10^9 => O(√n),判断质数
n≤10^18 => O(logn),最大公约数,快速幂,数位DP
n≤10^1000 => O((logn)2),高精度加减乘除
n≤10^100000 => O(logk×loglogk),k表示位数O(logk×loglogk),k表示位数,高精度加减、FFT/NTT
递归
1. 指数型
int st[N]; // 0-未遍历 1-选 2-不选
void dfs(int u){
if(u == n){
for(int i = 0; i < n; i++){
if(st[i] == 1){
printf("%d ", i + 1);
}
}
printf("\n");
return ; // 不要一遗忘!!!
}
// 选取分支
st[u] = 1;
dfs(u + 1);
st[u] = 0;
// 不选取分支
st[u] = 2;
dfs(u + 1);
st[u] = 0;
}
2. 排列型
int st[N]; // 0-未遍历 1~n-表示对应的访问
int used[N]; // true-访问 false-未被访问
void dfs(int u){
if(u == n){
for(int i = 0; i < n; i++)
printf("%d ", st[i]);
puts("");
return ;
}
for(int i = 0; i < n; i++){
if(!used[i]){
used[i] = true;
st[u] = i + 1;
dfs(u + 1);
st[u] = 0;
used[i] = false;
}
}
}
3. 组合型
int st[N]; // 0-未遍历 1~n-表示对应的访问
void dfs(int u, int start){
if(u == m){
for(int i = 0; i < m; i++)
printf("%d ", st[i]);
puts("");
return ;
}
for(int i = start; i <= n; i++){
st[u] = i;
dfs(u + 1, i + 1);
st[u] = 0;
}
}
动态规划DP
_1. _
int n, m;
int v[N], w[N];
int dp[N][N]; // dp表示(重量)价值,i表示拿取个数,j表示拿取体积
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
scanf("%d%d", &v[i], &w[i]);
for(int i = 1; i <= n; i++){
for(int j = 0; j <= m; j++){
if(j < v[i]) // 装不下
dp[i][j] = dp[i - 1][j];
else // 装下的话需要比较拿还是不拿
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - v[i]] + w[i]);
}
}
printf("%d\n", dp[n][m]);
return 0;
}
_2. _
int T;
int r, c;
int v[N][N];
int dp[N][N]; // dp表示(重量)价值,i表示拿取个数,j表示拿取体积
int main(){
scanf("%d", &T);
while(T --){
scanf("%d%d", &r, &c);
memset(v, 0, sizeof v);
for(int i = 1; i <= r; i++)
for(int j = 1; j <= c; j++)
scanf("%d", &v[i][j]);
for(int i = 1; i <= r; i++){
for(int j = 1; j <= c; j++){
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + v[i][j];
}
}
printf("%d\n", dp[r][c]);
}
return 0;
}