算法进阶指南打卡

---

文章目录

• 基本算法
  • 位运算
  • 递推与递归
  • 前缀和与差分
  • 二分
  • 排序
  • 倍增
  • 贪心
  • 总结与练习
• 基本数据结构
  • 栈
  • 队列
  • 链表与邻接表
  • Hash
  • 字符串
  • Tire
  • 二叉堆
  • 总结与练习
• 搜索
  • 树与图的遍历
  • 深度优先搜索
  • 剪枝
  • 迭代加深
  • 广度优先搜索
  • 广度变形
  • A*
  • IDA*
  • 总结与练习
• 数学知识
  • 质数
  • 约数
  • 同余
  • 矩阵乘法
  • 高斯消元与线性空间
  • 组合计数
  • 容斥原理与Mobius函数
  • 概率与数学期望
  • 0/1分数规划
  • 博弈论之SG函数
  • 总结与练习
• 数据结构进阶
  • 并查集
  • 树状数组
  • 线段树
  • 分块
  • 点分治
  • 二叉查找树与平衡树初步
  • 离线分治算法
  • 可持久化数据结构
  • 总结与练习
• 动态规划
  • 线性DP
  • 背包
  • 区间DP
  • 树形DP
  • 环形与后效性处理
  • 状态压缩DP
  • 倍增优化DP
  • 数据结构优化DP
  • 单调队列优化DP
  • 斜率优化
  • 四边形不等式
  • 计数类DP
  • 数位统计DP
  • 总结与练习
• 图论
  • 最短路
  • 最小生成树
  • 树的直径与最近公共祖先
  • 基环树
  • 负环与差分约束
  • Tarjan算法与无向图连通性
  • Tarjan算法与有向图连通性
  • 二分图的匹配
  • 二分图的覆盖与独立集
  • 网络流初步
  • 总结与练习

---

一、基本算法

1.位运算

1.a^b

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;typedef long long LL;int main()
{LL a,b,p;cin>>a>>b>>p;//本题利用快速幂即可解决问题LL res=1%p;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}cout<<res<<endl;return 0;
}

2.64位整数乘法

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;typedef  unsigned long long LL;int main()
{LL a,b,p;cin>>a>>b>>p;LL res=0;while(b){if(b&1) res=(res+a)%p;a=a*2%p;b>>=1;}cout<<res<<endl;return 0;
}

3.最短Hamilton路径

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=20,M=1<<N;int n;
int w[N][N],f[M][N];int main()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>w[i][j];memset(f,0x3f,sizeof(f));//因为要求最小值，所以初始化为无穷大f[1][0]=0;//因为零是起点,所以f[1][0]=0;for(int i=0;i<1<<n;i++)//i表示所有的情况for(int j=0;j<n;j++)//j表示走到哪一个点if(i>>j&1)for(int k=0;k<n;k++)//k表示走到j这个点之前,以k为终点的最短距离if(i>>k&1)f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);//更新最短距离cout<<f[(1<<n)-1][n-1]<<endl;//表示所有点都走过了,且终点是n-1的最短距离//位运算的优先级低于'+'-'所以有必要的情况下要打括号return 0;
}

4.起床困难综合症

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;#define x first
#define y secondtypedef pair<string,int> PII;
const int N=1e5+10;int n,m;
PII a[N];int calc(int bit,int num)
{for(int i=0;i<n;i++){int X=(a[i].y>>bit)&1;if (a[i].first == "OR") {num |= X;} else if (a[i].first == "XOR") {num ^= X;} else {num &= X;}}return num;
}int main()
{scanf("%d%d", &n, &m);for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y;int x0=0,res=0;for(int i=30;~i;i--)//由题意可知，可以知道最大不超过有30个比特位：所以可以从第30位开始枚举{int ans1=calc(i,0);//最高位填0int ans2=calc(i,1);//最高位填1if(x0+(1<<i)<=m&&ans1<ans2)x0+=(1<<i),res+=ans2<<i;else res+=ans1<<i;}cout<<res<<endl;return 0;
}

2.递推与递归

1.递归实现指数型枚举

//利用二进制来进行状态的描述#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;int n;void dfs(int u,int status)
{if(u>n){for(int i=1;i<=n;i++){if(status>>i&1)cout<<i<<" ";}cout<<endl;return;}else{dfs(u+1,status);dfs(u+1,status+(1<<u));}
}int main()
{cin>>n;dfs(1,0);
}

2.递归实现组合型枚举

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int n, m;void dfs(int u, int s, int state)
{if (s > m){for (int i = 1; i <= n; i ++ )if (state >> i & 1)cout << i  << ' ';cout << endl;return;}if (u>n) return;for (int i = u; i <=n; i ++ ){dfs(i + 1, s + 1, state + (1 << i));}
}int main()
{cin >> n >> m;dfs(1, 1, 0);return 0;
}

3.递归实现排列型枚举

#include<iostream>
#include<cstring>
#include<algorithm>using namespace std;const int N=10;int n;
int path[N];
bool st[N];void dfs(int u)
{if(u>n)//说明此时将一种情况的全排列找到{for(int i=1;i<=n;i++)cout<<path[i]<<" ";cout<<endl;}else {for(int i=1;i<=n;i++){if(!st[i]){st[i]=true;path[u]=i;//经典的回溯dfs(u+1);st[i]=false;path[u]=0;}}}}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n;dfs(1);return 0;
}

4.费解的开关

#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits.h>using namespace std;const int N=10;char g[N][N];
int dx[] = {-1, 0, 1, 0, 0}, dy[] = {0, 1, 0, -1, 0};void turn(int x,int y)
{for(int i=0;i<5;i++)//如果当前位置x,y需要改变灯，则，上下左右也会发生变换。{int newX=x+dx[i],newY=y+dy[i];if(newX<5&&newY<5&&newX>=0&&newY>=0)//如果满足边界条件g[newX][newY]^=1;//通过异或方式来改变灯的变换}
}void solve()
{int res=INT_MAX;//枚举第一行的灯的所有情况for(int k=0;k<1<<5;k++){int curRes=0;char tmp[N][N];//保存当前的结果memcpy(tmp,g,sizeof g);for(int i=0;i<5;i++){if(k>>i&1) {curRes++;turn(0,i);}}//第一行的状态已确定如果存在0的情况下，那么只能从第二行开始for(int i=0;i<4;i++)for(int j=0;j<5;j++)if(g[i][j]=='0'){curRes++;turn(i+1,j);}bool dark=false;//通过判断最后一行的灯情况如果没有出现0则说明变换成功for(int i=0;i<5;i++)if(g[4][i]=='0'){dark=true;break;}if(!dark) res=min(res,curRes);memcpy(g,tmp,sizeof g);}if(res>6) cout<<"-1"<<endl;else cout<<res<<endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T;cin>>T;while(T--){for(int i=0;i<5;i++) cin>>g[i];solve();}return 0;
}

5.奇怪的汉诺塔

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N=15;int d[N],f[N];int main()
{d[1]=1;for(int i=2;i<=12;i++)d[i]=1+d[i-1]*2;//首先考虑三个汉诺塔问题，可以推出该递推公式memset(f,0x3f,sizeof f);f[0]=0;for(int i=1;i<=12;i++){for(int j=0;j<i;j++)f[i]=min(f[i],f[j]*2+d[i-j]);//f[i]=min(f[i],f[j]*2+d[i-j]);//i表示当前一共有几个塔，也就是所说的n}for(int i=1;i<=12;i++)cout<<f[i]<<endl;return 0;
}

6.约数之和

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int mod=9901;int qmi(int a,int b)
{a%=mod;int res=1%mod;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
//(1+pk2)∗sum(p,k2)
int sum(int p,int k)
{if(k==0) return 1;if (k % 2 == 0) return (p % mod * sum(p, k - 1) % mod + 1) % mod;return sum(p, k / 2) % mod * (1 + qmi(p, k / 2 + 1)) % mod;
}int main()
{int A,B;cin>>A>>B;int res=1;for(int i=2;i<=A;i++){int s=0;while(A%i==0){s++;A/=i;}if(s) res=res*sum(i,s*B)%mod;}if(!A) puts("0");else cout<<res<<endl;return 0;
}

3.前缀和与差分

4.二分

5.排序

6.倍增

7.贪心

8.总结与练习

二、基本数据结构

1.栈

2.队列

3.链表与邻接表

4.Hash

5.字符串

6.Tire

7.二叉堆

8.总结与练习

三、搜索

1.树与图的遍历

2.深度优先搜索

3.剪枝

4.迭代加深

5.广度优先搜索

6.广度变形

7.A*

8.IDA*

9.总结与练习

四、数学知识

1.质数

2.约数

3.同余

4.矩阵乘法

5.高斯消元与线性空间

6.组合计数

7.容斥原理与Mobius函数

8.概率与数学期望

9.0/1分数规划

10.博弈论之SG函数

11总结与练习

五、数据结构进阶

1.并查集

2.树状数组

3.线段树

4.分块

5.点分治

6.二叉查找树与平衡树初步

7.离线分治算法

8.可持久化数据结构

9.总结与练习

六、动态规划

1.线性DP

2.背包

3.区间DP

4.树形DP

5.环形与后效性处理

6.状态压缩DP

7.倍增优化DP

8.数据结构优化DP

9.单调队列优化DP

10.斜率优化

11.四边形不等式

12.计数类DP

13.数位统计DP

14.总结与练习

七、图论

1.最短路

2.最小生成树

3.树的直径与最近公共祖先

4.基环树

5.负环与差分约束

6.Tarjan算法与无向图连通性

7.Tarjan算法与有向图连通性

8.二分图的匹配

9.二分图的覆盖与独立集

10.网络流

11.初步总结与练习