一、基础算法
快速排序
请你使用快速排序对这个数列按照从小到大进行排序。
数据范围：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个数。
#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 >= rreturn 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 < jswap(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的整数数列。
并将排好序的数列按顺序输出。
#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 >= rreturn;
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 的整数数列，请你计算数列中的逆序对的数量。
#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 >= rreturn 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 <= midtmp[k ++ ] = a[i ++ ];
while(j <= rtmp[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个查询。
如果数组中不存在该元素，则返回 -1 -1。
#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，求它的三次方根。
#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 >= nr = mid;
else l = mid;
}
printf("%.6lf",l;
return 0;
}
高精度
题目：给定两个正整数（不含前导 0），计算它们的和。
#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），计算它们的差，计算结果可能为负数。
#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 的值。
#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( == 0C.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 的商和余数。
#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的整数序列。
对于每个询问，输出原序列中从第 l个数到第 r个数的和。
#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的整数序列。
请你输出进行完所有操作后的序列。
#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表示一个子矩阵的左上角坐标和右下角坐标。
请你将进行完所有操作后的矩阵输出。
数据范围：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;
}