没有合适的资源？快使用搜索试试~ 我知道了~

文库首页后端C++AcWing算法基础课模板大全

AcWing算法基础课模板大全

数据结构

需积分: 5 17 下载量 24 浏览量 2023-07-14 22:31:47 上传评论 7 收藏 1.51MB PDF 举报

温馨提示

试读

57页

基础算法 —— 代码模板链接常用代码模板1——基础算法排序二分高精度前缀和与差分双指针算法位运算离散化区间合并数据结构 —— 代码模板链接常用代码模板2——数据结构链表与邻接表：树与图的存储栈与队列：单调队列、单调栈 kmp Trie 并查集堆 Hash表搜索与图论 —— 代码模板链接常用代码模板3——搜索与图论 DFS与BFS 树与图的遍历：拓扑排序最短路最小生成树二分图：染色法、匈牙利算法数学知识 —— 代码模板链接常用代码模板4——数学知识质数约数欧拉函数快速幂扩展欧几里得算法中国剩余定理高斯消元组合计数容斥原理简单博弈论动态规划背包问题线性DP 区间DP 计数类DP 数位统计DP 状态压缩DP 树形DP 记忆化搜索贪心

资源推荐

资源详情

资源评论

Acwing 算法基础课超详细笔记

C/C++中文参考手册(C++23标准) 离线chm最新版是一份详尽的C++23标准参考手册，适用于C++程序员和开发人员。该手册提供了全面的C++23标准库和语言特性的介绍，包括语法、关键字、数据类型、控制结构、函数、指针、类和对象、继承、多态性、模板和异常处理等内容。该手册以离线chm格式提供，方便用户在没有互联网连接的情况下查阅和使用。用户只需下载并安装该文件，即可在本地计算机上随时随地

一、基础算法

快速排序算法模板

边界问题

因为边界问题只有这两种组合，不能随意搭配

归并排序算法模板

void quick_sort(int q[], int l, int r)

{

 //递归的终止情况

 if (l >= r) return;

 

  //选取分界线。这里选数组中间那个数

 int i = l - 1, j = r + 1, x = q[l + r >> 1];

 //划分成左右两个部分

 while (i < j)

 {

   do i ++ ; while (q[i] < x);

   do j -- ; while (q[j] > x);

   if (i < j) swap(q[i], q[j]);

 }

 //对左右部分排序

 quick_sort(q, l, j), quick_sort(q, j + 1, r);

}

x不能取q[l]和q[l+r>>1];

quick_sort(q,l,i-1),quick_sort(q,i,r);

x不能取q[r]和q[(l+r+1)>>1];

quick_sort(q,l,j),quick_sort(q,j+1,r);

void merge_sort(int q[], int l, int r)

{

 //递归的终止情况

 if (l >= r) return;

 //第一步：分成子问题

 int mid = l + r >> 1;

 //第二步：递归处理子问题

 merge_sort(q, l, mid);

 merge_sort(q, mid + 1, r);

 

 //第三步：合并子问题

 int k = 0, i = l, j = mid + 1;

 while (i <= mid && j <= r)

   if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];

整数二分算法模板

对lower_bound来说，它寻找的就是第一个满足条件“值大于等于x”的元素的位置；对upper_bound函

数来说，它寻找的是第一个满足“值大于 x”的元素的位置。

浮点数二分算法模板

   else tmp[k ++ ] = q[j ++ ];

 while (i <= mid) tmp[k ++ ] = q[i ++ ];

 while (j <= r) tmp[k ++ ] = q[j ++ ];

 //第四步：复制回原数组

 for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

}

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：

int bsearch_1(int l, int r)

{

 while (l < r)

 {

   int mid = l + r >> 1;

   if (check(mid)) r = mid;  // check()判断mid是否满足性质

   else l = mid + 1;//左加右减

 }

 return l;

}

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：

int bsearch_2(int l, int r)

{

 while (l < r)

 {

   int mid = l + r + 1 >> 1;//如果下方else后面是l则这里加1

   if (check(mid)) l = mid;

   else r = mid - 1;//左加右减

 }

 return l;

}

高精度加法

高精度减法

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)

{

 const double eps = 1e-6;  // eps 表示精度，取决于题目对精度的要求

 while (r - l > eps)

 {

   double mid = (l + r) / 2;

   if (check(mid)) r = mid;

   else l = mid;

 }

 return l;

}

// C = A + B, A >= 0, B >= 0

vector<int> add(vector<int> &a,vector<int> &b){

 //c为答案

 vector<int> c;

 //t为进位

 int t=0;

 for(int i=0;i<a.size()||i<b.size();i++){

   //不超过a的范围添加a[i]

   if(i<a.size())t+=a[i];

   //不超过b的范围添加b[i]

   if(i<b.size())t+=b[i];

   //取当前位的答案

   c.push_back(t%10);

   //是否进位

   t/=10;

 }

 //如果t!=0的话向后添加1

 if(t)c.push_back(1);

 return c;

}

// C = A - B, 满足A >= B, A >= 0, B >= 0

vector<int> sub(vector<int> &A, vector<int> &B)

{

 //答案

 vector<int> C;

 //遍历最大的数

 for (int i = 0, t = 0; i < A.size(); i ++ )

 {

   //t为进位

   t = A[i] - t;

   //不超过B的范围t=A[i]-B[i]-t;

高精度比大小（cmp函数）

高精度乘低精度

   if (i < B.size()) t -= B[i];

   //合二为一，取当前位的答案

   C.push_back((t + 10) % 10);

   //t<0则t=1

   if (t < 0) t = 1;

   //t>=0则t=0

   else t = 0;

 }

 //去除前导零

 while (C.size() > 1 && C.back() == 0) C.pop_back();

 return C;

}

//高精度比大小

bool cmp(vector<int> &A, vector<int> &B) {

if (A.size() != B.size())

return A.size() > B.size();

for (int i = A.size() - 1; i >= 0; i -- )

if (A[i] != B[i])

return A[i] > B[i];

return true;

}

// C = A * b, A >= 0, b >= 0

vector<int> mul(vector<int> &A, int b)

{

 //类似于高精度加法

 vector<int> C;

 //t为进位

 int t = 0;

 for (int i = 0; i < A.size() || t; i ++ )

 {

   //不超过A的范围t=t+A[i]*b

   if (i < A.size()) t += A[i] * b;

   //取当前位的答案

   C.push_back(t % 10);

   //进位

   t /= 10;

 }

 //去除前导零

 while (C.size() > 1 && C.back() == 0) C.pop_back();

 return C;

}

高精度乘高精度

高精度除低精度

高精度除高精度

vector<int> mul(vector<int> &A, vector<int> &B) {

 vector<int> C(A.size() + B.size() + 7, 0); // 初始化为 0，C的size可以大一点

 for (int i = 0; i < A.size(); i++)

   for (int j = 0; j < B.size(); j++)

     C[i + j] += A[i] * B[j];

 int t = 0;

 for (int i = 0; i < C.size(); i++) { // i = C.size() - 1时 t 一定小于 10

   t += C[i];

   C[i] = t % 10;

   t /= 10;

 }

 while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高

位很可能是 0

 return C;

}

// A / b = C ... r, A >= 0, b > 0

vector<int> div(vector<int> &A, int b, int &r)//高精度A，低精度b，余数r

{

 vector<int> C;//答案

 r = 0;

 for (int i = A.size() - 1; i >= 0; i -- )

 {

   r = r * 10 + A[i];//补全r>=b

   C.push_back(r / b);//取当前位的答案

   r %= b;//r%b为下一次计算

 }

 reverse(C.begin(), C.end());//倒序为答案

 while (C.size() > 1 && C.back() == 0) C.pop_back();//去除前导零

 return C;

}

vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r) {

vector<int> C;

if (!cmp(A, B)) {

C.push_back(0);

r.assign(A.begin(), A.end());

return C;

}

int j = B.size();

剩余56页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

Zh0uKal1

粉丝: 117
资源: 4

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

AcWing算法基础课模板大全

acwing基础算法模板整理

AcWing 基础算法课.md

建议收藏算法基础课模板大全

templates.rar（AcWing）

acwing算法基础课讲义

算法基础课模板，常用模板代码实现

算法基础课模板小全.pdf

算法基础课模板小全算法基础课模板小全

Acwing 算法基础课超详细笔记

acwing算法第三讲

loadrunner课堂笔记

Acwing-基础算法-第一章-基础算法

AcWing算法基础课项目,所有题目均以c++实现.zip

老毛子百度云转存【2019-1-22】.txt

acwing和leetcode-algo:某物

vue基础视频15课

acwing和leetcode-Algorithm-All-Know:从零开始刷算法题

第十五届蓝桥杯大赛软件赛省赛C++B组题目

C/C++中文参考手册离线最新版

代码随想录-八股文 pdf

编译器（gcc、g++）

第十五届蓝桥杯大赛软件赛省赛-C++A组题目

Qt5.9 C++开发指南.pdf 及示例源码

Qt （高仿Visio）流程图组件开发，源码分享

mingw-w64-install.exe

Qt、QCustomPlot、实时波形绘制、实时曲线绘制

C/C++中文帮助文档

最新资源