重庆永川网站建设报价,台州网站建设咨询薇,企业网站建设及推广研究,.tel域名能存放网站吗文章目录
基本算法 位运算递推与递归前缀和与差分二分排序倍增贪心总结与练习基本数据结构 栈队列链表与邻接表Hash字符串Tire二叉堆总结与练习搜索 树与图的遍历深度优先搜索剪枝迭代加深广度优先搜索广度变形A*IDA*总结与练习数学知识 质数约数同余矩阵乘法高斯消元与线性空… 文章目录
基本算法 位运算递推与递归前缀和与差分二分排序倍增贪心总结与练习基本数据结构 栈队列链表与邻接表Hash字符串Tire二叉堆总结与练习搜索 树与图的遍历深度优先搜索剪枝迭代加深广度优先搜索广度变形A*IDA*总结与练习数学知识 质数约数同余矩阵乘法高斯消元与线性空间组合计数容斥原理与Mobius函数概率与数学期望0/1分数规划博弈论之SG函数总结与练习数据结构进阶 并查集树状数组线段树分块点分治二叉查找树与平衡树初步离线分治算法可持久化数据结构总结与练习动态规划 线性DP背包区间DP树形DP环形与后效性处理状态压缩DP倍增优化DP数据结构优化DP单调队列优化DP斜率优化四边形不等式计数类DP数位统计DP总结与练习图论 最短路最小生成树树的直径与最近公共祖先基环树负环与差分约束Tarjan算法与无向图连通性Tarjan算法与有向图连通性二分图的匹配二分图的覆盖与独立集网络流初步总结与练习一、基本算法
1.位运算
1.a^b
#includeiostream
#includecstring
#includealgorithmusing namespace std;typedef long long LL;int main()
{LL a,b,p;cinabp;//本题利用快速幂即可解决问题LL res1%p;while(b){if(b1)resres*a%p;aa*a%p;b1;}coutresendl;return 0;
}
2.64位整数乘法
#includeiostream
#includecstring
#includealgorithmusing namespace std;typedef unsigned long long LL;int main()
{LL a,b,p;cinabp;LL res0;while(b){if(b1) res(resa)%p;aa*2%p;b1;}coutresendl;return 0;
}
3.最短Hamilton路径
#includeiostream
#includecstring
#includealgorithmusing namespace std;const int N20,M1N;int n;
int w[N][N],f[M][N];int main()
{cinn;for(int i0;in;i)for(int j0;jn;j)cinw[i][j];memset(f,0x3f,sizeof(f));//因为要求最小值所以初始化为无穷大f[1][0]0;//因为零是起点,所以f[1][0]0;for(int i0;i1n;i)//i表示所有的情况for(int j0;jn;j)//j表示走到哪一个点if(ij1)for(int k0;kn;k)//k表示走到j这个点之前,以k为终点的最短距离if(ik1)f[i][j]min(f[i][j],f[i-(1j)][k]w[k][j]);//更新最短距离coutf[(1n)-1][n-1]endl;//表示所有点都走过了,且终点是n-1的最短距离//位运算的优先级低于-所以有必要的情况下要打括号return 0;
}
4.起床困难综合症
#include iostream
#include cstring
#include algorithmusing namespace std;#define x first
#define y secondtypedef pairstring,int PII;
const int N1e510;int n,m;
PII a[N];int calc(int bit,int num)
{for(int i0;in;i){int X(a[i].ybit)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 i0;in;i)cina[i].xa[i].y;int x00,res0;for(int i30;~i;i--)//由题意可知可以知道最大不超过有30个比特位所以可以从第30位开始枚举{int ans1calc(i,0);//最高位填0int ans2calc(i,1);//最高位填1if(x0(1i)mans1ans2)x0(1i),resans2i;else resans1i;}coutresendl;return 0;
}2.递推与递归
1.递归实现指数型枚举
//利用二进制来进行状态的描述#includeiostream
#includecstring
#includealgorithmusing namespace std;int n;void dfs(int u,int status)
{if(un){for(int i1;in;i){if(statusi1)couti ;}coutendl;return;}else{dfs(u1,status);dfs(u1,status(1u));}
}int main()
{cinn;dfs(1,0);
}
2.递归实现组合型枚举
#include cstring
#include iostream
#include algorithmusing 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 (un) 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.递归实现排列型枚举
#includeiostream
#includecstring
#includealgorithmusing namespace std;const int N10;int n;
int path[N];
bool st[N];void dfs(int u)
{if(un)//说明此时将一种情况的全排列找到{for(int i1;in;i)coutpath[i] ;coutendl;}else {for(int i1;in;i){if(!st[i]){st[i]true;path[u]i;//经典的回溯dfs(u1);st[i]false;path[u]0;}}}}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cinn;dfs(1);return 0;
}
4.费解的开关
#include iostream
#include cstring
#include algorithm
#include limits.husing namespace std;const int N10;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 i0;i5;i)//如果当前位置x,y需要改变灯则上下左右也会发生变换。{int newXxdx[i],newYydy[i];if(newX5newY5newX0newY0)//如果满足边界条件g[newX][newY]^1;//通过异或方式来改变灯的变换}
}void solve()
{int resINT_MAX;//枚举第一行的灯的所有情况for(int k0;k15;k){int curRes0;char tmp[N][N];//保存当前的结果memcpy(tmp,g,sizeof g);for(int i0;i5;i){if(ki1) {curRes;turn(0,i);}}//第一行的状态已确定如果存在0的情况下那么只能从第二行开始for(int i0;i4;i)for(int j0;j5;j)if(g[i][j]0){curRes;turn(i1,j);}bool darkfalse;//通过判断最后一行的灯情况如果没有出现0则说明变换成功for(int i0;i5;i)if(g[4][i]0){darktrue;break;}if(!dark) resmin(res,curRes);memcpy(g,tmp,sizeof g);}if(res6) cout-1endl;else coutresendl;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T;cinT;while(T--){for(int i0;i5;i) cing[i];solve();}return 0;
}
5.奇怪的汉诺塔
#include iostream
#include cstring
#include algorithmusing namespace std;const int N15;int d[N],f[N];int main()
{d[1]1;for(int i2;i12;i)d[i]1d[i-1]*2;//首先考虑三个汉诺塔问题可以推出该递推公式memset(f,0x3f,sizeof f);f[0]0;for(int i1;i12;i){for(int j0;ji;j)f[i]min(f[i],f[j]*2d[i-j]);//f[i]min(f[i],f[j]*2d[i-j]);//i表示当前一共有几个塔也就是所说的n}for(int i1;i12;i)coutf[i]endl;return 0;
}
6.约数之和
#include iostream
#include cstring
#include algorithmusing namespace std;const int mod9901;int qmi(int a,int b)
{a%mod;int res1%mod;while(b){if(b1) resres*a%mod;aa*a%mod;b1;}return res;
}
//(1pk2)∗sum(p,k2)
int sum(int p,int k)
{if(k0) 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;cinAB;int res1;for(int i2;iA;i){int s0;while(A%i0){s;A/i;}if(s) resres*sum(i,s*B)%mod;}if(!A) puts(0);else coutresendl;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.初步总结与练习
