01快速排序
给定你一个长度为n的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。
输入格式
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在1~109109范围内），表示整个数列。
输出格式
输出共一行，包含 n 个整数，表示排好序的数列。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
5
3 1 2 4 5输出样例：
1 2 3 4 5分析：
这道题目显然是要我们将一个无序数列排序,成为具有升序性质的升序序列
STL解法中sort(xx,xx) / sort(xx,xx,xx) 可以写两个参数或三个参数 两个默认升序，三个可以升序或者降序修改大于小于即可。
快排的思想
基础解法：
#include //万能头文件仅使用于竞赛
using namespace std;
const int N=1e8+10;
int a[N];
void quick_sort(int l,int r)
{
if(l>=r) return;
int x=a[(l+r)/2],i=l-1,j=r+1;
while(ix);
if(i STL解法：
#include
using namespace std;
const int N=1e8+10;
int a[N];
int cmp(int a,int b)
{
return a 二分
02整数二分算法
数的范围
给定一个按照升序排列的长度为n的整数数组，以及 q 个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从0开始计数）。
如果数组中不存在该元素，则返回“-1 -1”。
输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数（均在1~10000范围内），表示完整数组。
接下来q行，每行包含一个整数k，表示一个询问元素。
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回“-1 -1”。
数据范围
1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5输出样例：
3 4
5 5
-1 -1分析：
在一个范围内,查找一个数字,要求找到这个元素的起始位置和结束位置,请注意这个范围内的数字都是单调递增的,即具有单调性质.
算法理解
一个题目,如果一个区间具有单调性质,那么一定可以二分,但是如果说这道题目没有单调性质,而是具有某种区间性质的话,我们同样可以使用二分.
二分的题目,往往会出现最大值最小值,或者单调性质,这道题目显然不例外,要我们离线查找,所以我们完全可以使用二分算法来处理这道题目.
所谓的二分算法,就是我们知道当前的候选区间中,一定存在我们要找到的答案,而且我们发现这个区间拥有单调性质此类的性质,那么我们可以不停地缩减候选区间的范围,达到排除无用答案的效果.
题解：
#include
using namespace std;
const int N = 1e5+10;
int q[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i =0;i=x) r=mid;
else l =mid+1;
}
if(q[l] != x) printf("-1 -1\n");
else
{
printf("%d ",l);
int l=0,r=n-1;
while(l 03小数二分算法
给定一个浮点数n，求它的三次方根。
输入格式
共一行，包含一个浮点数n。
输出格式
共一行，包含一个浮点数，表示问题的解。
注意，结果保留6位小数。
数据范围
−10000≤n≤10000−10000≤n≤10000
输入样例：
1000.00输出样例：
10.000000题解：
#include
using namespace std;
int main()
{
double x;
scanf("%lf",&x);
double l = -1e4,r = 1e4;//数值的取值范围
//根据题目要求保留浮点数后面多少位进行增加2
//如本题保留6位 1e-8 ;4位 1e-6 ;2位1e-4
while (r - l > 1e-8)
{
double mid = (l+r)/2;
if(mid * mid * mid >= x) r = mid;//修改此处更改开方大小
else l = mid;
}
printf("%lf\n",l);
return 0;
} 高精度
04高精度加法
给定两个正整数，计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤1000001≤整数长度≤100000
输入样例：
12
23输出样例：
35题解：
#include
using namespace std;
vector add(vector&A,vector&B)
{
vectorc;
if(A.size() < B.size()) return add(B,A);//根据加法式位数长的在上面
int t=0;
for(int i=0;i 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');//vector中push_back()在vector末尾插入值
auto C = add(A,B);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
return 0;
} 05高精度减法
给定两个正整数，计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤1051≤整数长度≤105
输入样例：
32
11输出样例：
21题解：
#include
using namespace std;
//判断A>=B，根据减法如果A &A, vector &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 sub(vector &A,vector &B)
{
vector C;
for(int i=0,t=0;i 1 && C.back() == 0) C.pop_back();//C.back()返回最后一个元素，C.pop_back()删除最后一个元素
return C;
}
int main()
{
string a,b;
vector 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]);
}
} 06高精度乘法
给定两个正整数A和B，请你计算A * B的值。
输入格式
共两行，第一行包含整数A，第二行包含整数B。
输出格式
共一行，包含A * B的值。
数据范围
1≤A的长度≤1000001≤A的长度≤100000,
1≤B≤100001≤B≤10000
输入样例：
2
3输出样例：
6题解：
#include
#include
using namespace std;
vector mul(vector &A, int b)
{
vector C;
int t=0;
for(int i=0; i < A.size() || t ; i++)
{
if(i> a >> b;
vector 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;
} 07高精度除法
给定两个正整数A，B，请你计算 A / B的商和余数。
输入格式
共两行，第一行包含整数A，第二行包含整数B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤1000001≤A的长度≤100000,
1≤B≤100001≤B≤10000
输入样例：
7
2输出样例：
3
1题解：
#include
using namespace std;
vector div(vector &A,int b,int &r)
{
vector 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());//reverse逆序(C.头，C尾)
while(C.size()>1&&C.back() ==0)C.pop_back();
return C;
}
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');
int r;
auto C=div(A,b,r);
for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
printf("\n%d",r);
return 0;
}
前缀和于差分
08前缀和
输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对l, r。
对于每个询问，输出原序列中从第l个数到第r个数的和。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数，表示整数数列。
接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。
输出格式
共m行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n1≤l≤r≤n,
1≤n,m≤1000001≤n,m≤100000,
−1000≤数列中元素的值≤1000−1000≤数列中元素的值≤1000
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4输出样例：
3
6
10题解：
#include
#include
using namespace std;
const int N=1e5+10;
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];
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",s[r]-s[l-1]);
}
return 0;
} *09子矩阵的和
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数n，m，q。
接下来n行，每行包含m个整数，表示整数矩阵。
接下来q行，每行包含四个整数x1, y1, x2, y2，表示一组询问。
输出格式
共q行，每行输出一个询问的结果。
数据范围
1≤n,m≤10001≤n,m≤1000,
1≤q≤2000001≤q≤200000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000−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
#include
using namespace std;
const int N=10000+10;
int n,m,q;
int 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",&s[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];
while(q--)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
}
return 0;
} 10差分
输入一个长度为n的整数序列。
接下来输入m个操作，每个操作包含三个整数l, r, c，表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数，表示整数序列。
接下来m行，每行包含三个整数l，r，c，表示一个操作。
输出格式
共一行，包含n个整数，表示最终序列。
数据范围
1≤n,m≤1000001≤n,m≤100000,
1≤l≤r≤n1≤l≤r≤n,
−1000≤c≤1000−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000−1000≤整数序列中元素的值≤1000
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1输出样例：
3 4 5 3 4 2题解：
#include
#include
const int N=1e5+10;
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];
for(int i=1;i<=n;i++) printf("%d ",b[i]);
return 0;
} *11差分矩阵
输入一个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≤10001≤n,m≤1000,
1≤q≤1000001≤q≤100000,
1≤x1≤x2≤n1≤x1≤x2≤n,
1≤y1≤y2≤m1≤y1≤y2≤m,
−1000≤c≤1000−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1输出样例：
2 3 4 1
4 3 4 1
2 2 2 2题解：
#include
using namespace std;
const int N=1010;//不能超出10010会超出内存限制
int n,m,q;
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()
{
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++)
printf("%d ",b[i][j]);
printf("\n");
}
return 0;
} 双指针算法
12最长连续不重复子序列
给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续区间，输出它的长度。
输入格式
第一行包含整数n。
第二行包含n个整数（均在0~100000范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复数字的连续子序列的长度。
数据范围
1≤n≤1000001≤n≤100000
输入样例：
5
1 2 2 3 5输出样例：
3分析：
本题的核心思想是双指针算法，i指针是快指针，j是慢指针，每当i指针i指针右移一位的时候，
其对应的元素的个数就需要++，可以看出此处需要一个计数的数组或者unordered_map<int, int>，
如果是字符串或者字符等元素的话，建议用后者。
接下来介绍check函数，check函数的实现功能就是，当s[a[i]]>1的话，我们就持续j++，
并且将s[a[j]]–，这一步绝对不能省。
第三步就是最后的操作了res = max(res, i - j + 1);
题解：
#include
#include
using namespace std;
const int N=1e5+10;
int q[N],s[N];
int n;
int main()
{
scanf("%d",&n);
for(int i=0;i < n;i++) scanf("%d",&q[i]);
int res=0;
for(int i=0,j=0;i 1) s[q[j++]] --;
res = max(res,i-j+1);
}
printf("%d\n",res);
return 0;
} 位运算
13二进制中1的个数
给定一个长度为n的数列，请你求出数列中每个数的二进制表示中1的个数。
输入格式
第一行包含整数n。
第二行包含n个整数，表示整个数列。
输出格式
共一行，包含n个整数，其中的第 i 个数表示数列中的第 i 个数的二进制表示中1的个数。
数据范围
1≤n≤1000001≤n≤100000,
0≤数列中元素的值≤1090≤数列中元素的值≤109
输入样例：
5
1 2 3 4 5输出样例：
1 1 2 1 2题解：
#include
using namespace std;
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int x,s=0;
scanf("%d",&x);
for(int i=x; i;i-=i & -i) s++;
printf("%d ",s);
}
return 0;
} 离散化
14区间和
假定有一个无限长的数轴，数轴上每个坐标上的数都是0。
现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。
近下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行，每行包含两个整数x和c。
再接下里 m 行，每行包含两个整数l和r。
输出格式
共m行，每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109−109≤x≤109,
1≤n,m≤1051≤n,m≤105,
−109≤l≤r≤109−109≤l≤r≤109,
−10000≤c≤10000−10000≤c≤10000
输入样例：
3 3
1 2
3 6
7 5
1 3
4 6
7 8输出样例：
8
0
5题解：
#include
#include
#include
using namespace std;
typedef pair PII;
const int N = 300010;
int n, m;
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 + 1;
}
vector::iterator unique(vector &a)
{
int j = 0;
for (int i = 0; i < a.size(); i ++ )
if (!i || a[i] != a[i - 1])
a[j ++ ] = a[i];
// a[0] ~ a[j - 1] 所有a中不重复的数
return a.begin() + j;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int x, c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i ++ )
{
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), alls.end());
// 处理插入
for (auto item : add)
{
int x = find(item.first);
a[x] += item.second;
}
// 预处理前缀和
for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];
// 处理询问
for (auto item : query)
{
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
} 区间合并
15区间合并
给定 nn 个区间 [li,ri][li,ri]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n。
接下来n行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9输出样例：
3题解：
#include
#include
#include
using namespace std;
typedef pair PII;
void merge(vector &segs)
{
vector res;
sort(segs.begin(),segs.end());
int st = -2e9,ed = -2e9;
for(auto seg : segs)
if(ed segs;
for(int i=0;i 
