1、基础算法 —— 代码模板
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]);
else break;
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
例题：找第k小数
给定一个长度为 n 的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k 个数。
输入格式
第一行包含两个整数 n 和 k。
第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整数数列。
输出格式
输出一个整数，表示数列的第 k 小数。
数据范围
1≤n≤100000,
1≤k≤n
1）个人写的代码，不够巧妙，hhhh
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n,k;
int q[N];
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(l<r){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
else break;
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&q[i]);
quick_sort(q,1,n);
printf("%d ",q[k]);
return 0;
}
#include<iostream>
using namespace std;
const int N=100010;
int n,k;
int q[N];
void quick_set(int l,int r,int k){
if(l>=r) return;//可写==但是快排里必须是>=
int x=q[l+r >>1],i=l-1,j=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]);
else break;
}
int sl=j-l+1;
if(k<sl) return quick_set(l,j,k);
return quick_set(j+1,r,k-sl);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++) scanf("%d",&q[i]);
quick_set(0,n,k);
printf("%d",q[k]);
return 0;
}
void merge_sort(int q[],int l,int r)
{
if(l>=r) return;
int mid=l+r >> 2;
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++];
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];
//将排好序的tmp数组复制到原来的数组q里面，用于在main函数输出
}
例题：788. 逆序对的数量
给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。
输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。
输出格式
输出一个整数，表示逆序对的个数。
数据范围
1≤n≤100000
输入样例：
6
2 3 4 5 6 1
输出样例：
5
思路：
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int q[N],tmp[N];
LL merge_sort(int q[],int l,int r){
if(l>=r) return 0;
int mid = l + r >> 1;//不用加(),因为+的优先级大于>>
LL res = 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++];
else{
res += mid - i + 1;
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];//i从l开始
return res;
}
int main(){
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
cout << merge_sort(q, 0, n - 1) << endl;
return 0;
}
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1,比如当l=r-1时，区间为[r-1,r],如果mid=(l+r)/2,则更新后mid=l,check(mid)为true之后，l=mid=l,则区间还是为[l,r]，造成死循环.若mid=(l+r)/2+1的话，mid=r,check(mid)为true之后，l=mid=r,区间更新为[r,r].
注！若更新为l=mid,r=mid+1,则mid=(l+r+1)/2;
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;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
例题：789数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。
接下来 q 行，每行包含一个整数 k，表示一个询问元素。
输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1
#include<iostream>
using namespace std;
const int N=1e6+10;
int n,m,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;
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位小数，写1e-6;
保留6位小数，1e-8;
#include<iostream>
using namespace std;
int main(){
double x;
cin>>x;
double l=0,r=x;
while(r-l>1e-6){
double mid=(l + r)/2;
if(mid * mid >=x) r=mid;
else l=mid+1;
}
printf("%f\n",l);
return 0;
}
#include<vector>// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
例题：给定两个正整数，计算它们的和。
#include<iostream>
using namespace std;
#include<vector>
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);//最高位如果需要进1
return C;
}
int main(){
string a,b;
vector<int> A,B;
cin >> a >> b;//a="123456"
//存储大数数组
for(int i=a.size()-1; i>=0; i--) A.push_back(a[i]-'0');//减0的目的是为了将字符串a[i]转化为数组,A=[6,5,4,3,2,1]，！！i>=0
for(int i=b.size()-1; i>=0; i--) B.push_back(b[i]-'0');
auto C=add(A,B);//auto--编译器自己推断C是什么类型的，等价于vector<int> C
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
}
二、高精度减法
大整数A-大整数B
#include<iostream>
using namespace std;
#include<vector>
//判断是否有A>=B
bool cmp(vector<int> &A,vector<int> &B){
if(A.size() != B.size()) return A.size()>B.size();//判断A的位数是否大于B的位数
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])
return A[i]>B[i];
return true;//否则的话相等
}
vector<int> sub(vector<int> &A,vector<int> &B){
vector<int> C;
for(int i=0,t=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，则干掉
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');
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(B,A);
printf("-");
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
}
return 0;
}
三、高精度乘法–大整数乘小整数string a;int b;
注意判断b是否为0
#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &A,int b){
vector<int> C;
int t=0;
for(int i=0;i<A.size()|| t;i++){
t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
if(t) C.push_back(t);
while(C.size()>1&&C.back()==0)//当b为0时
C.pop_back();
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;
}
四、高精度乘法
给定两个非负整数 A，B，请你计算 A/B 的商和余数。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000,
B 一定不为 0
例题：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//A / b,商是c[i],余是r
vector<int> div(vector<int> &A,int b,int &r){
vector<int> C;
r=0;//定义余数初始为0；
// 特殊之处在于与前面的大整数乘法和加减法不同的是，除法从高位开始进行运算即从A[i-1]开始
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());//reverse需要加上头文件algorithm
while(C.size()>1 && C.back()==0) C.pop_back();
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');
int r;
auto C=div(A,b,r);//不仅返回商还要返回余数r
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
cout << endl << r << endl;
return 0;
}
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],s[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
int l,r;
while(m--){
scanf("%d%d",&l,&r);
printf("%d\n",s[r]-s[l-1]);
}
return 0;
}
// 一维前缀和
// S[i] = a[1] + a[2] + … a[i]
// a[l] + … + a[r] = S[r] - S[l - 1]
// 二维前缀和
// S[i, j] = 第i行j列格子左上部分所有元素的和
// 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为 S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
例子：子矩阵的和
输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 q 行，每行输出一个询问的结果。
数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21
#include<iostream>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N],s[N][N];
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;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;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);//x1后面必须紧跟y1,不然出错
printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);//算子矩阵的和
}
return 0;
}
#include<iostream>
using namespace std;
const int N=100010;
int a[N],b[N];
int n,m;
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) insert(i,i,a[i]);
while(m--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
for(int i=1;i<=n;i++) b[i]+=b[i-1];//an=b1+...+bn
for(int i=1;i<=n;i++) printf("%d ",b[i]);
return 0;
}
二阶差分矩阵
例题：
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含 5 个整数 x1,y1,x2,y2,c，表示一个操作。
输出格式
共 n 行，每行 m 个整数，表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000
#include<iostream>
using namespace std;
const int N=1010;
int a[N][N],b[N][N];
int n,m,q;
void insert(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
insert(i,j,i,j,a[i][j]);
while(q--){
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&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];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(j == m) printf("%d\n", b[i][j]);
else printf("%d ",b[i][j]);
return 0;
}