Chapter 1 基础算法
1：快速排序
【1】确定分界点。x = q[l], q[r], q[(r+l)/2]都可以
【2】调整区间，使得左段<=x ，右段>x
【3】递归处理左右两段
暴力：
【1】开辟
a[N], b[N]【2】把小于等于x的数放在
a[N]，大于x的数放在b[N]【3】遍历
a[N], b[N]，按大小顺序拷贝到q[N]
双指针：
# include <iostream>
using namespace std;
const int N = 1e6+10;
int n;
int q[N];
// basic quick sort
void quick_sort(int q[], int l, int r){
if(l >= r) return;
// judge the boundary
int i=l-1,j=r+1;
int x=q[r+l >> 1];
// initiate x, i, j
while(i < j){
do i++;
while(q[i]<x);
do j--;
while(q[j]>x);
if(i < j) swap(q[i],q[j]);
}
// 如果x=q[l],则必须写成j和j+1
quick_sort(q, l, j);
quick_sort(q, j+1, r);
}
int main(){
scanf("%d",&n);
for(int i=0; i<n; i++){
scanf("%d", &q[i]);
}
quick_sort(q, 0, n-1);
for(int i=0; i<n; i++){
printf("%d", q[i]);
}
return 0;
}
/*
5 3
2 4 1 5 3
3
*/
2：归并排序
分治法
【1】确定分界点mid = (l+r)/2
【2】递归排序left和right
【3】归并，然后合二为一
双指针：
#include <iostream>
using namespace std;
const int N=1e6+10;
int n;
int q[N], tmp[N];
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; // i是左侧数组的起点，j是右侧数组的起点
while(i <= mid && j <= r){ // i和j都在数组范围内
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i <= mid) tmp[k++] = q[i++]; // 左侧还有数
while(j <= r) tmp[k++] = q[j++]; //右侧还有数
// 拷贝tmp到q（额外空间tmp开销）
for(i = l, j = 0; i <= r; i++, j++){
// i从左侧数组起点l开始，j从tmp数组起点0开始
q[i] = tmp[j];
}
}
int main(){
scanf("%d, &n");
for(int i=0; i<n; i++){
scanf("%d", &q[i]);
}
merge_sort(q, 0, n-1);
for(int i=0; i<n; i++){
printf("%d", q[i]);
}
return 0;
}
3：整数二分
—0—0—0—0—0—x(0)—y(1)—1—1—1—1—1—1—1—
1：右侧都满足check
0：左侧都不满足check
y为1的边界
x为0的边界
方法1（得到x）
【1】确定分界点：mid = (l+r+1)/2
【2】检查mid是否符合条件（即取0），若true（取0了），则答案在[mid, r]内，更新l = mid；若false（取1了），则答案在[l, mid-1]内，更新r = mid-1
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; // 一定要加1，否则会出现边界问题！
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
方法2（得到y）
【1】确定分界点：mid = (l+r)/2
【2】检查mid是否符合条件（即取1），若true（取1了），则答案在[l, mid]内，更新r = mid；若false（取0了），则答案在[mid+1, r]内，更新l = mid+1
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
题目：数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回
-1 -1。输入格式：
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
#include <iostream>
using namespace std;
const int N=1e6+10;
int n,m;
int q[N];
int main(){
scanf("%d%d", &n, &m);
for (int i=0; i<n; i++) scanf("%d", &q[i]);
while(m--){
int x;
scanf("%d", &x);
int l = 0, r = n-1;
// 起始位置判定
while(l < r){
int mid = l+r >> 1;
if(q[mid] >= x) r = mid; // 如果mid位置的数，不小于询问元素k
else l = mid+1;
}
if(q[l] != x) cout<<"-1 -1"<<endl;
else{
cout<<l<<" ";
int l=0, r=n-1;
// 终止位置判定
while(l < r){
int mid = l+r+1 >> 1;
if(q[mid] <= x) l = mid;
else r = mid-1;
}
cout<<l<<endl;
}
}
return 0;
}
4：浮点二分
题目：大于1的数字的平方根
# include <iostream>
using namespace std;
int main(){
double x;
cin>>x;
double l=0, r=x;
while(r - l > 1e-8){
double mid = (l+r)/2;
if(mid * mid > x) r = mid;
else l = mid;
}
printf("%lf\n", l);
return 0;
}
5：高精度加法
【1】大整数存储（正整数），从个位开始（string to vector）
【2】Ai + Bi + 进位
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6+10;
// 加法
vector<int> add(vector<int> &A, vector<int> &B){
vector<int> C;
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];
C.push_back(t%10);
t /= 10;
}
if(t) C.push_back(1); //最高位有进位，例如9+2=11，1需要进位
return C;
}
int main(){
string a,b;
vector<int> A, B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
auto C = add(A, B);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
}
6：高精度减法
【1】大整数存储（正整数），从个位开始（string to vector）
【2】Ai - Bi + 结位
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6+10;
// 判断A>=B
bool cmp(vector<int> &A, vector<int> &B){
// 判断bit-size
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 1; // A == B
}
// 减法
vector<int> sub(vector<int> &A, vector<int> &B){
vector<int> C;
int t=0;
for(int i=0; i<A.size(); 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()>1 && C.back()==0) C.pop_back() // 去除前导0，例如01
return C;
}
int main(){
string a,b;
vector<int> A, B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
// A >= B
if(cmp(A, B)){
auto C = sub(A, B);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
}
else{
auto C = sub(A, B);
cout<<"-";
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
}
return 0;
}
7：高精度乘法
【1】大整数存储（正整数），从个位开始（string to vector）
【2】b看成一个整体，和A相乘（A是大整数，B是小整数）
#include <iostream>
#include <vector>
using namespace std;
// multiply
vector<int> mul(vector<int> &A, int b){
vector<int> C;
int t=0;
for(int i=0;i<A.size()|| t;i++){
if(i<A.size()) t += A[i]*b;
C.push_back(t%10);
t /= 10;
}
return C;
}
int main(){
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
auto C = mul(A, b);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
}
8：高精度除法
【1】大整数存储（正整数），从个位开始（string to vector）
【2】b看成一个整体，和A相除（A是大整数，B是小整数），从最高位开始算（一般会有前导0）
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// divide
vector<int> div(vector<int> &A, int b, int &r){
vector<int> C;
r=0;
for(int i=A.size()