快速排序
快速排序
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int s[100000];
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>s[i];
}
sort(s,s+n);
for(int i=0;i<n;i++)
{
cout<<s[i]<<" ";
}
cout<<endl;
return 0;
}
第K个数
#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
nth_element(a+1,a+k,a+1+n);
cout<<a[k]<<endl;
return 0;
}
归并排序
归并排序
#include <iostream>
using namespace std;
const int N = 100010;
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=1,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(int i=l,j=1;i<=r;i++,j++)
{
q[i]=tmp[j];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&q[i]);
}
merge_sort(q,1,n);
for(int i=1;i<=n;i++)
{
printf("%d ",q[i]);
}
return 0;
}
逆序对的数量
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int q[N],tmp[N];
ll merge_sort(int l,int r)
{
if(l>=r)
{
return 0;
}
int mid = (l+r)>>1;
ll res=merge_sort(l,mid)+merge_sort(mid+1,r);
//归并的过程
int k=1,i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j])
{
tmp[k++]=q[i++];
}
else
{
tmp[k++]=q[j++];
res+=(mid-i+1);
}
}
//扫尾
while(i<=mid)
{
tmp[k++]=q[i++];
}
while(j<=r)
{
tmp[k++]=q[j++];
}
//物归原主
for(int i=l,j=1;i<=r;i++,j++)
{
q[i]=tmp[j];
}
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>q[i];
}
cout<<merge_sort(1,n)<<endl;
return 0;
}
二分
数的范围
#include <iostream>
using namespace std;
const int N = 100010;
int q[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>q[i];
}
while(m--)
{
int x;
cin>>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<<" ";
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;
}
数的三次方根
#include <iostream>
using namespace std;
int main()
{
double n;
cin>>n;
double l=-10000,r=10000;
while(r-l>1e-8)
{
double mid = (l+r)/2;
if(mid*mid*mid>=n)
{
r=mid;
}
else l=mid;
}
printf("%.6lf\n",l);
return 0;
}
高精度
高精度加法
Python一行就可以解决
print(int(input())+int(input()))
#include <iostream>
#include <string>
#include <vector>
using namespace std;
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(t);
}
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');
}
auto C = add(A,B);
for(int i=C.size()-1;i>=0;i--)
{
cout<<C[i];
}
return 0;
}
高精度减法
#include <iostream>
#include <string>
#include <vector>
using namespace std;
//判断是否有A>=B
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;
}
//C=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();
}
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');
}
if(cmp(A,B))
{
auto C = sub(A,B);
for(int i=C.size()-1;i>=0;i--)
{
cout<<C[i];
}
}
else
{
auto C = sub(B,A);
cout<<"-";
for(int i=C.size()-1;i>=0;i--)
{
cout<<C[i];
}
}
return 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++)
{
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--)
{
cout << C[i];
}
return 0;
}
高精度除法
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> div(vector<int>& A, int b,int &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());
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);
for (int i = C.size() - 1; i >= 0; i--)
{
cout << C[i];
}
cout<<endl<<r<<endl;
return 0;
}
前缀和与差分
前缀和
#include <iostream>
using namespace std;
const int N = 100005;
int a[N],s[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+a[i];
}
while(m--)
{
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
子矩阵的和
#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++)
for (int j = 1; j <= m; j++)
{
scanf("%d", &a[i][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;
}
差分
#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c)
{
b[l]+=c;
b[r+1]-=c;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
insert(i,i,a[i]);
}
while(m--)
{
int l,r,c;
cin>>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++)
{
cout<<b[i]<<" ";
}
return 0;
}
差分矩阵
#include <iostream>
using namespace std;
const int N = 1010;
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()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>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;
cin>>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++)
{
cout<<b[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
双指针算法
最长连续不重复子序列
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N],s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int res=0;
for(int i=1,j=1;i<=n;i++)
{
s[a[i]]++;
while(s[a[i]]>1)
{
s[a[j]]--;
j++;
}
res=max(res,i-j+1);
}
cout<<res<<endl;
return 0;
}
数组元素的目标和
#include <iostream>
using namespace std;
const int N = 100005;
int n,m,x;
int a[N],b[N];
int main()
{
cin>>n>>m>>x;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
cin>>b[i];
}
for(int i=1,j=m;i<=n;i++)
{
while(j>=1&&a[i]+b[j]>x) j--;
if(a[i]+b[j]==x)
{
cout<<i-1<<" "<<j-1<<endl;
break;
}
}
return 0;
}
判断子序列
#include <iostream>
using namespace std;
const int N = 100005;
int n,m;
int a[N],b[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<m;i++)
{
cin>>b[i];
}
int i=0,j=0;
while(i<n&&j<m)
{
if(a[i]==b[j])i++;
j++;
}
if(i==n)
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
return 0;
}
位运算
二进制中1的个数
#include <iostream>
using namespace std;
int lowbit(int x)
{
return x & -x;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int x;
cin>>x;
int res=0;
while(x)
{
x-=lowbit(x);
res++;
}
cout<<res<<" ";
}
return 0;
}
离散化
区间和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 300010; //n次插入和m次查询相关数据量的上界
int n, m;
int a[N];//存储坐标插入的值
int s[N];//存储数组a的前缀和
vector<int> alls; //存储(所有与插入和查询有关的)坐标
vector<pair<int, int>> 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;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 1; i <= m; i++)
{
int l , r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
//排序,去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//执行前n次插入操作
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];
//处理后m次询问操作
for (auto item : query)
{
int l = find(item.first);
int r = find(item.second);
printf("%d\n", s[r] - s[l-1]);
}
return 0;
}
区间和并文章来源地址https://www.toymoban.com/news/detail-660497.html文章来源:https://www.toymoban.com/news/detail-660497.html
区间和并
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int>pii;
const int N = 100010;
int n;
vector<pii>segs;
void merge(vector<pii>&segs)
{
vector<pii>res;
sort(segs.begin(),segs.end());
int st=-2e9,ed=-2e9;
for(auto seg:segs)
{
if(ed<seg.first)
{
if(ed!=-2e9) res.push_back({st,ed});
st=seg.first;
ed=seg.second;
}
else ed=max(ed,seg.second);
}
if(st!=2e9) res.push_back({st,ed});
cout<<res.size()<<endl;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
cin>>l>>r;
segs.push_back({l,r});
}
merge(segs);
return 0;
}
到了这里,关于算法基础课——基础算法(模板整理)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!