发门网
基础算法（排序，二分，高精度，前缀和，差分，双指针，位运算，离散化，区间合并）
创始人
2024-05-24 08:31:31
0次

基础算法

目录

    • 基础算法
      • 排序
        • 快速排序
          • 步骤（分治）
        • 归并排序
          • **步骤（分治）**：
      • 二分
          • 代码
      • 高精度
        • A + B
        • A - B
        • A * b
        • A /b
      • 前缀和
        • 一维数组
        • 二维数组
      • 差分（前缀和逆运算）
        • 一维构造
        • 二维差分
      • 双指针
      • 位运算
        • lowbit(x)
      • 离散化（整数）
        • 核心代码
      • 区间合并(贪心)

排序

快速排序

步骤（分治）
  • 确定分界点x（左右边界点或中间的点）
  • 调整区间：使得第一个区间所有元素小于等于x，第二区间所有元素大于x

方法：双指针

左指针右移直到元素大于x， 右指针相反，然后交换左右指针的值

  • 递归处理左右两端

代码这样写(第一个元素为分界点)：

#include
using namespace std;void print(int a[], int n)
{  for(int j= 0; j= x) j--;  if(i

一般我们更常用下面的代码(左边小于等于x, 右边大于等于x)

#include
using namespace std;
const int N = 1e6 + 10;int n;
int q[N];void quick_sort(int q[], int l, int r) {if (l >= r)	return;int x = q[l], i = l - 1, j = r + 1;while (i < j) {while (q[++i] < x);while (q[--j] > x);cout << q[i] << " " << q[j]<> n;for (int i = 0; i < n; ++i) {cin >> q[i];}quick_sort(q, 0, n - 1);for (int i = 0; i < n; ++i) {cout << q[i] << " ";}return 0;
}

归并排序

O(nlogn)

稳定：两个相同值排序后的相对位置不发生变化（快速排序不稳定）

步骤（分治）：
  • 确定分界点， 中间的点
  • 递归排序left，right
  • 归并，合二为一

代码

#include 
using namespace std;const int N = 1e6 + 10;
int n;
int q[N], tmp[N];void merge_sort(int arr[], int l, int r) {if (l >= r)     return;int mid = (l + r) / 2;merge_sort(arr, l, mid), merge_sort(arr, mid + 1, r);int i = l, j = mid + 1, k = 0;while (i <= mid && j <= r) {if (q[i] <= q[j])       tmp[k++] = q[i++];else    tmp[k++] = q[j++];    // cout << tmp[k-1] <<" "<> n;for (int i = 0; i < n; ++i) {cin >> q[i];}merge_sort(q, 0, n - 1);for (int i = 0; i < n; ++i) {cout << q[i] << " ";}
}

二分

(很容易死循环 TuT)

在一个区间：右半边满足某性质，左半边不满足，可以用二分来找到边界点

代码
class Solution {
public:int search(vector& nums, int target) {int l = 0, r = nums.size() - 1;while (l <= r) {int mid = l + r >> 1;if (nums[mid] < target) l = mid + 1;else if (nums[mid] > target)   r = mid - 1;else    return mid; }return -1;}
};

样例

给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。

对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式

第一行包含整数 nn 和 qq，表示数组长度和询问个数。

第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。

接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。

输出格式

共 qq 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

代码

#include 
using namespace std;
const int N = 1e5 + 10;
int ar[N];
int main() {int n, m;cin >> n >> m;for (int i = 0; i < n; ++i)     cin >> ar[i];while (m--) {int x;cin >> x;int l = 0, r = n - 1;while (l < r) {int mid = (l + r) >> 1;if (ar[mid] >= x)   r = mid;else    l = mid + 1;}// cout << l;if (ar[l] != x) {cout << "-1 -1" << endl;continue;}int ans1 = l;l = 0, r = n - 1;while (l < r){int mid = (l + r + 1) >> 1; // 防止死循环if (ar[mid] <= x)   l = mid;else    r = mid - 1; }int ans2 = l;cout << ans1 << " " << ans2 << endl; }return 0;
}

高精度

  • 大整数存储：存在一个数组中，下标为零存个位

A + B

#include 
#include 
using namespace std;
vector a, b;
vector add(vector &a, vector &b) {vector ans;int t = 0;for (int i = 0; i < a.size() || i < b.size(); ++i) {if (i < a.size())   t += a[i];  if (i < b.size())   t += b[i];ans.push_back(t % 10);t /= 10;}if (t)  ans.push_back(t);//cout << ans.size() << endl;return ans;
}
int main() {string x, y;cin >> x >> y;for (int i = x.size() - 1; i  >= 0; --i)      a.push_back(x[i] - '0');for (int i = y.size() - 1; i  >= 0; --i)      b.push_back(y[i] - '0');vector ans = add(a, b);for (int i = ans.size() - 1; i >= 0; --i)    cout <

A - B

#include 
#include 
using namespace std;
bool cmp (vector &a, vector &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;
}
vector minuss(vector a, vector b) {vector ans;int t = 0;for (int i = 0; i < a.size(); ++i) {t += a[i];if (i < b.size())   t -= b[i];//if (t >= 0) {ans.push_back(t);t = 0;}     else {ans.push_back(10 + t);t = -1;}//cout << ans.size() << endl;}
//    for (int i = ans.size() - 1; i >= 0; --i) {
//        cout << ans[i];
//    }for (int i = ans.size() - 1; i >= 1; --i) {if (ans[i] == 0)    ans.pop_back();else    break;}return ans;
}
int main() {string a, b;cin >> a >> b;vector aa, bb;for (int i = a.size() - 1; i >= 0; --i) {aa.push_back(a[i] - '0');}for (int i = b.size() - 1; i >= 0; --i) {bb.push_back(b[i] - '0');}vector ans;if (!cmp(aa, bb)) {cout << "-";ans = minuss(bb, aa); }  else	 ans = minuss(aa, bb);//cout<= 0; --i) {cout << ans[i];}return 0;
}

A * b

  • 高精度整数A乘低精度整数b
#include 
#include 
using namespace std;
vector  mul(vector a, int b) {vector ans;int t = 0;for (int i = 0; i < a.size(); ++i) {t += a[i] * b;ans.push_back(t % 10);t /= 10; }if (t)  ans.push_back(t);while (ans.size() > 1 && ans.back() == 0) ans.pop_back();//cout << t << endl; return ans;
}
int main() {string a;int b;vector A;cin >> a >> b;for (int i = a.size() - 1; i >= 0; --i)     A.push_back(a[i] - '0');auto ans = mul(A, b);for (int i = ans.size() - 1; i >= 0; --i) {cout << ans[i];}return 0;
}

A /b

  • 高精度整数A除低精度整数b
#include 
#include 
#include 
using namespace std;
vector div(vector &a, int b, int &r) {r = 0;vector c;for (int i = a.size() - 1; i >= 0; --i) {r = r * 10 + a[i];c.push_back(r / b);r %= b;}reverse(c.begin(), c.end());while (c.size() > 1 && !c.back())   c.pop_back();return c;
}int main() {string a;int b, r;cin >> a >> b;vector  A;for (int i = a.size() - 1; i >= 0; --i) {A.push_back(a[i] - '0');}auto ans = div(A, b, r);for (int i = ans.size() - 1; i >= 0; --i) {cout << ans[i];}cout << endl;cout << r;return 0;
}

前缀和

一维数组

Si=a1+a2+...+aiS_i = a_1 + a_2 +...+ a_i Si​=a1​+a2​+...+ai​

ai=si−si−1a_i = s_i -s_{i-1} ai​=si​−si−1​

  • 定义s0s_0s0​为0
  • 作用：一次运算求出一段区间的和([l, r] : srs_rsr​ - si−1s_{i-1}si−1​)

代码

#include 
#include 
using namespace std;
int main() {int m, n;cin >> n >> m;vector a(n + 1);vector s(n + 1);for (int i = 1; i <=n; ++i) {cin >> a[i];s[i] = s[i-1] + a[i];}while (m--) {int l, r;cin >> l >> r;cout << s[r] - s[l - 1] << endl;}return 0;
}

二维数组

Si,j=Si−1,j+Si,j−1−Si−1,j−1+ai,jS_{i,j} = S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+a_{i,j} Si,j​=Si−1,j​+Si,j−1​−Si−1,j−1​+ai,j​

aij到sija_{ij}到s_{ij}aij​到sij​
Sx2y2−Sx2y1−Sx1y2+Sx1y1S_{x_2y_2}-S_{x_2y_1}-S_{x_1y_2} + S{x_1y_1} Sx2​y2​​−Sx2​y1​​−Sx1​y2​​+Sx1​y1​
代码

#include 
using namespace std;
const int N = 1010;
int m, n, q;
int a[N][N], s[N][N];
int main() {ios::sync_with_stdio(false);cin >> n >> m >> q;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][j];s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i-1][j-1] + a[i][j];}}while (q--) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;cout << s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1] << endl;}return 0;
}

差分（前缀和逆运算）

一维构造

已知a1,a2,...,ana_1,a_2,...,a_na1​,a2​,...,an​

构造b1,b2,...,bnb_1,b_2,...,b_nb1​,b2​,...,bn​

使得ai=b1+b2+...+bia_i=b_1+b_2+...+b_iai​=b1​+b2​+...+bi​

我们可以通过b 数组得到a 数组

  • a数组[l, r] + c ：bl+cb_l+cbl​+c，br+1−cb_{r+1}-cbr+1​−c

代码

#include 
using namespace std;
const int N = 1e5 + 10;
int s[N], d[N];
int main() {ios::sync_with_stdio(false);int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i)  {cin >> s[i];d[i] = s[i] - s[i - 1];}while (m--) {int l, r, c;cin >> l >> r >> c;d[l] += c;d[r + 1] -= c;}for (int i = 1; i <= n; ++i) {s[i] = s[i - 1] + d[i];cout << s[i] << " ";}return 0;
}

#include 
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
void insert(int l, int r, int c) {b[l] += c;b[r + 1] -= c;
}
int main() {ios::sync_with_stdio(false);int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> a[i];insert(i, i, a[i]);}while (m--) {int l, r, c;cin >> l >> r >> c;insert(l, r, c);}for (int i = 1; i <= n; ++i) {a[i] = a[i-1] + b[i];cout << a[i] << " ";}return 0;
}

二维差分

代码

注意insert函数

#include 
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {b[x1][y1] += c;b[x1][y2+1] -= c;b[x2+1][y1] -= c;b[x2+1][y2+1] += c;
}
int main() {ios::sync_with_stdio(false);int m, n, q;cin >> n >> m >> q;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][j];insert(i, j, i, j, a[i][j]);}}while (q--) {int x1, x2, y1, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c);}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];cout << a[i][j] << " ";}cout << endl;}return 0;
}

#include 
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {b[x1][y1] += c;b[x1][y2+1] -= c;b[x2+1][y1] -= c;b[x2+1][y2+1] += c;
}
int main() {ios::sync_with_stdio(false);int m, n, q;cin >> n >> m >> q;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][j];insert(i, j, i, j, a[i][j]);}}while (q--) {int x1, x2, y1, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c);}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];cout << b[i][j] << " ";}cout << endl;}return 0;
}

双指针

快慢指针

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

#include 
using namespace std;
const int N = 1e5 + 10;
int a[N], s[N];
int main() {ios::sync_with_stdio(false);int n;cin >> n;for (int i = 0; i < n; ++i) {cin >> a[i];}int res = 0;for (int i = 0, j = 0; i < n; ++i) {++s[a[i]];while (j < i && s[a[i]] > 1)    --s[a[j++]];res = max(res, i - j + 1);} cout << res;return 0;
}

位运算

n的二进制第k位是几： n >> k & 1

lowbit(x)

返回x最后一个1以及后面部分

int lowbit(int x) {return x & -x;
}

代码

#include 
using namespace std;int lowbit(int x) {return x & -x;
}int main() {int n;cin >> n;while (n--) {int x;cin >> x;int ans = 0;while (x) {x -= lowbit(x);++ans;}cout << ans << " ";}return 0;
}

x = 1010

原码 0…01010

反码 1…11010

补码（取反加一)11…11011

计算机负数用补码表示

离散化（整数）

  • 10510^5105个数，值域0−1090-10^90−109(个数比较少。数值比较大）
  • 我们需要把值作为下标

我们把他们映射到1,2,3,4,5…自然数

核心代码

int find(int x) {int l = 0, r = alls.size() - 1;while (l < r) {int mid = l + r >> 1;if (alls[mid] >= x)     r = mid;else    l = mid + 1;}return r;
}

    sort(alls.begin(), alls.end());// 去重alls.erase(unique(alls.begin(), alls.end()), alls.end());

代码

#include 
#include 
#include 
using namespace std;
const int N = 3e5 + 10;
int a[N], s[N];
vector alls;
vector> add, query;
int find(int x) {int l = 0, r = alls.size() - 1;while (l < r) {int mid = l + r >> 1;if (alls[mid] >= x)     r = mid;else    l = mid + 1;}return r;
}
int main() {int n, m;cin >> n >> m;while (n--) {int x, c;cin >> x >> c;add.push_back({x, c});alls.push_back(x);}while (m--) {int l, r;cin >> l >> r;query.push_back({l,  r});alls.push_back(l);alls.push_back(r);}sort(alls.begin(), alls.end());// 去重alls.erase(unique(alls.begin(), alls.end()), alls.end());for (auto i: add) {// a数组从1开始计int x = find(i.first) + 1;a[x] += i.second; }//  前缀和数组for (int i = 1; i <= alls.size(); ++i) {s[i] = s[i-1] + a[i];}for (auto i: query) {int  l = find(i.first) + 1, r = find(i.second) + 1;cout << s[r] - s[l-1] << endl;}return 0;
}

区间合并(贪心)

  • 按区间左端点排序
  • 右端点合并

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;vector> merge(vector> &p) {vector> ans;sort(p.begin(), p.end());int st = -2e9, ed = -2e9;for (auto i: p) {if (i.first > ed) {if (st != -2e9)  ans.push_back({st, ed});st = i.first, ed = i.second;}else {ed = max(ed, i.second);}}if (st != -2e9)  ans.push_back({st, ed});return ans;
}
int main()
{vector> segs;int n;cin >> n;while (n--) {int l, r;cin >> l >> r;segs.push_back({l, r});} auto ans = merge(segs);cout << ans.size();return 0;
}

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：智能工厂自动化设备如何将数据采集到物联网云平台上

下一篇：MacBookPro M2芯片下如何搭建React-Native环境

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播，要解决的几个问题是：1&...
Windows10添加群晖磁盘... 在使用群晖NAS时，我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章，在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF，目录中的页码并非PDF中直接索引的页码...
Fluent中创建监测点 1 概述某些仿真问题，需要创建监测点，用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装（Wind... 前言：刚换了一台电脑，里面所有东西都需要重新配置，习惯了所...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
MFC文件操作  MFC提供了一个文件操作的基类CFile，这个类提供了一个没有缓存的二进制格式的磁盘...