一、基础算法
快速排序
题目：给定你一个长度为 n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
数据范围：1≤n≤100000，所有整数均在 1∼10^9 范围内
#include <cstdio> //数据比较大时，尽量用scanf,printf进行输入输出
#include <iostream>
using namespace std; //swap函数需要std
const int N = 100010;
int n;
int a[N];
void quick_sort(int a[],int l,int r)
{
if(l >= r) return; //数组里只有1个或者没有数时返回
int x = a[(l + r) / 2],i = l - 1,j = r + 1; //数据加强，x只能取中间值，不能取两边值，否则超时
while(i < j)
{
do i ++;while(a[i] < x); //小于x即可，不需要小于等于
do j --;while(a[j] > x);
if(i < j) swap(a[i],a[j]);
}
quick_sort(a,l,j); //如果取i的话，x取值需为(l + r + 1) / 2
quick_sort(a,j + 1,r);
}
int main()
{
scanf("%d",&n);
for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
quick_sort(a,0,n - 1);
for(int i = 0;i < n;i ++)printf("%d ",a[i]);
return 0;
}
题目：给定一个长度为 n的整数数列，以及一个整数 k，请用快速选择算法求出数列从小到大排序后的第 k个数。
数据范围：1≤n≤100000，所有整数均在 1∼10^9 范围内
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int n,k;
int quick_sort(int l,int r,int k) //k为第k个小的数
{
if(l >= r)return a[l];
int x = a[l + r >> 1];
int i = l - 1;
int j = r + 1;
while(i < j)
{
while(a[ ++ i] < x);
while(a[ -- j] > x);
if(i < j)swap(a[i],a[j]);
}
int sl = j - l + 1; //sl为左半边有多少个数
if(sl >= k) return quick_sort(l,j,k); //递归左半边
else return quick_sort(j + 1,r,k - sl); //递归右半边，k-sl为右半边第k-sl个小的数
}
int main()
{
cin >> n >> k;
for(int i = 0;i < n;i ++ )scanf("%d",&a[i]);
cout << quick_sort(0,n -1,k);
return 0;
}
归并排序
题目：给定你一个长度为 n的整数数列。
请你使用归并排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
数据范围：1≤n≤100000，所有整数均在 1∼10^9 范围内
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int tmp[N];
int n;
void merge_sort(int a[],int l,int r)
{
if(l >= r)return;
int mid = l + r >> 1; //取中间值
merge_sort(a,l,mid);
merge_sort(a,mid + 1,r); //递归处理左右两边
int i = l,j = mid + 1; //指针指向左右两边起始处
int k = 0 ; //k为结果数组中已排好序的数量
while(i <= mid && j <= r)
{
if(a[i] < a[j]) tmp[k ++] = a[i ++];
else tmp[k ++] = a[j ++];
}
while(i <= mid) tmp[k ++] = a[i ++];
while(j <= r) tmp[k ++] = a[j ++]; //如果有数组还剩余数，直接补到结果数组后
for(int i = l,j = 0;i <= r;i ++ ,j ++) //l到r为闭区间，将结果数组复制回去
{
a[i] = tmp[j];
}
}
int main()
{
cin >> n;
for(int i = 0;i < n;i ++ )scanf("%d",&a[i]);
merge_sort(a,0,n - 1);
for(int i = 0;i < n;i ++ )printf("%d ",a[i]);
return 0;
}
题目：给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。
数据范围：1≤n≤100000，所有整数均在 1∼10^9 范围内
#include <iostream>
using namespace std;
const int N = 100010;
int n,k;
int a[N],tmp[N];
typedef long long LL; //数据超过int存储范围，需用long long
LL merge_sort(int l,int r)
{
if(l >= r)return 0;
int mid = l + r >> 1;
int i = l,j = mid + 1;
LL res = merge_sort(l,mid) + merge_sort(mid + 1,r); //递归处理左右两边
k = 0; //每次递归前k需要清零
while(i <= mid && j <= r)
{
if(a[i] <= a[j])tmp[k ++ ] = a[i ++ ];
else
{
tmp[k ++ ] = a[ j ++ ];
res += mid - i + 1; //如果左边的数比右边大，那么左边这个数到中间的数都能形成逆序
}
}
while(i <= mid)tmp[k ++ ] = a[i ++ ];
while(j <= r)tmp[k ++ ] = a[ j ++ ];
for(int i = l,j = 0;i <= r;i ++ ,j ++ )
a[i] = tmp[j];
return res;
}
int main()
{
cin >> n ;
for(int i = 0;i < n;i ++)
scanf("%d",&a[i]);
cout << merge_sort(0 ,n - 1);
return 0;
}
二分
题目：给定一个按照升序排列的长度为 n的整数数组，以及 q个查询。
对于每个查询，返回一个元素 k的起始位置和终止位置（位置从 0开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
数据范围：1≤n≤100000，1≤q≤10000，1≤k≤10000
#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int n,q;
int main()
{
cin >> n >> q;
for(int i = 0;i < n;i ++ )
scanf("%d",&a[i]);
while(q --)
{
int k;
scanf("%d",&k);
int l = 0,r = n - 1; //有边界不包括n
while(l < r)
{
int mid = l + r >> 1; //每次改变区间后mid需要重新计算，所以mid放入循环中
if(a[mid] >= k) r = mid; //取等号是因为答案有可能取到边界
else l = mid + 1;
}
if(a[l] != k) cout << "-1 -1" << endl;
else
{
cout << l << " ";
int l = 0,r = n - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(a[mid] <= k) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}
return 0;
}
题目：给定一个浮点数 n，求它的三次方根。
数据范围：-10000≤n≤10000，结果保留6位小数。
#include <iostream>
using namespace std;
int main()
{
double n;//注意浮点数
cin >> n;
double l = -10000,r = 10000;//注意浮点数
while(r - l > 1e-8) //注意10的-8次方，注意是大于
{
double mid = (l + r) / 2;//注意浮点数
if(mid * mid * mid >= n)r = mid;
else l = mid;
}
printf("%.6lf",l);
return 0;
}
高精度
题目：给定两个正整数（不含前导 0），计算它们的和。
数据范围：1≤整数长度≤100000
#include <iostream>
#include <vector>
using namespace std;
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]; //如果B还有数才加，因为有可能B比A更短
C.push_back(t % 10); //存储个位
t /= 10; //存储进位
}
if(t) C.push_back(t); //如果最后有进位，就补到最后一位
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'); //数据长，用vector存，倒着存
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 --)cout << C[i]; //由于是倒着存的，所以结果要倒着打
cout << endl;
return 0;
}
题目：给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。
数据范围：1≤整数长度≤10^5
#include <iostream>
#include <vector>
using namespace std;
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; //两个数如果相等，返回真
}
vector<int> sub(vector<int> &A,vector<int> &B)//引用的作用是少一遍数组拷贝，效率更高
{
vector<int> C;
int t = 0; //初始借位为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; //如果减出来为负数，则肯定有借位，所以把借位置为1，否则置为0
else t = 0;
}
while(C.size() > 1 && C.back() == 0) C.pop_back(); //去掉前导0，如果刚好得0则不去掉这个0
return C;
}
int main()
{
string a,b;
cin >> a >> b;
vector<int> 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');
vector<int> C;
if(cmp(A,B)) C = sub(A,B); //比较哪个数更大，如果被减数更小，需要加负号，并计算B-A
else
{
C = sub(B,A);
cout << "-";
}
for(int i = C.size() - 1;i >= 0;i --)
{
cout << C[i];
}
return 0;
}
题目：给定两个非负整数（不含前导 0） A和 B，请你计算 A×B 的值。
数据范围：1≤A的长度≤100000,0≤B≤10000
#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为进位，需要等进位全部补入到最后才能结束循环
{
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;
}
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;
}
题目：给定两个非负整数（不含前导 0） A，B，请你计算 A/B 的商和余数。
数据范围：1≤A的长度≤100000,0≤B≤10000,B 一定不为 0
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> dev(vector<int> &A,int b,int &r) //第一个引用的作用是少一遍数组拷贝，效率更高，第二个引用是将r的值带回去
{
vector<int> C;
r = 0;
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()); //翻转回来后便于去掉前导0
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 = dev(A,b,r);
for(int i = C.size() - 1;i >= 0;i --)printf("%d",C[i]);
cout << endl;
cout << r;
return 0;
}
前缀和
输入一个长度为 n的整数序列。
接下来再输入 m个询问，每个询问输入一对 l,r。
对于每个询问，输出原序列中从第 l个数到第 r个数的和。
数据范围：1≤l≤r≤n,1≤n,m≤100000,−1000≤数列中元素的值≤1000
#include <iostream>
using namespace std;
const int N = 100010;
int a[N],s[N];
int main()
{
int n,m;
cin >> 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]; //前缀和
while(m --)
{
int l,r;
cin >> l >> r;
printf("%d",s[r] - s[l-1]);
cout << endl;
}
return 0;
}
题目：输入一个 n行 m列的整数矩阵，再输入 q个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
数据范围：1≤n,m≤1000,1≤q≤200000,1≤x1≤x2≤n,1≤y1≤y2≤m,−1000≤矩阵内元素的值≤1000
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N],s[N][N];
int main()
{
int n,m,q;
cin >> n >> m >> q;
for(int i = 1;i <= n;i ++) //下标是从1开始的
{
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][j - 1] + s[i - 1][j] -s[i - 1][j - 1] + a[i][j];
}
while(q --)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 -1][y1 -1]);
}
return 0;
}
差分
题目：输入一个长度为 n的整数序列。
接下来输入 m个操作，每个操作包含三个整数 l,r,c，表示将序列中l,r之间的每个数加上 c。
请你输出进行完所有操作后的序列。
数据范围：1≤n,m≤100000,1≤l≤r≤n,−1000≤c≤1000,−1000≤整数序列中元素的值≤1000
#include <iostream>
using namespace std;
const int N = 100010;
int a[N],b[N];
void insert(int l,int r,int c)
{
b[l] += c;
b[r + 1] -= c;
}
int main()
{
int n,m;
cin >> 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] ;
}
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。
请你将进行完所有操作后的矩阵输出。
数据范围：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];
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()
{
int n,m,q;
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][j - 1] + b[i - 1][j] -b[i - 1][j - 1] ;
}
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= m;j ++)
printf("%d ",b[i][j]);
cout << endl;
}
return 0;
}