模板大全
一·算法部分
(一)排序部分
1.冒泡排序
#include<iostream> #include<cstdio> using namespace std; int n; int a[3000]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n-1;i++) for(int j=2;j<=n;j++) if(a[j-1]>a[j])swap(a[j-1],a[j]); for(int i=1;i<=n;i++)printf("%d ",a[i]); }
2.选择排序
#include<iostream> #include<cstdio> using namespace std; int n,a[100001]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=2;i<=n;i++) { for(int j=i;j>1;j--) { if(a[j]<a[j-1]) { int temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } else break; } } for(int i=1;i<=n;i++)printf("%d ",a[i]); }
3.插入排序
#include<iostream> #include<cstdio> using namespace std; int n,a[100001]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=2;i<=n;i++) { int l=0,r=i-1; int g=a[i]; while(l<=r) { int mid=(l+r)/2; if(a[mid]>g)r=mid-1; else l=mid+1; } for(int j=i-1;j>=l;j--)a[j+1]=a[j]; a[l]=g; } for(int i=1;i<=n;i++)printf("%d ",a[i]); }
4.归并排序
#include<iostream> #include<cstdio> using namespace std; int n,a[100001]; void up(int l,int mid,int r) { int i=l,num[100001],tot=0,j=mid+1; while(i<=mid&&j<=r) { if(a[i]>a[j])num[++tot]=a[j++]; else num[++tot]=a[i++]; } while(i<=mid)num[++tot]=a[i++]; while(j<=r)num[++tot]=a[j++]; for(int i=1;i<=tot;i++) { a[l++]=num[i]; } } void sep(int l,int r) { if(l==r)return ; int mid=l+(r-l)/2; sep(l,mid); sep(mid+1,r); up(l,mid,r); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); sep(1,n); for(int i=1;i<=n;i++)printf("%d ",a[i]); }
5.快速排序(sort)
(二)快速幂
#include<bits/stdc++.h> using namespace std; long long b,p,k; long long ans,bas; int main() { ans=1; cin>>b>>p>>k; int t=p; bas=b; while(p!=0) { if(p & 1 ==1)ans=((ans%k)*(bas%k))%k; bas=((bas%k)*(bas%k))%k; p >>= 1; } cout<<b<<"^"<<t<<" mod "<<k<<"="<<ans%k; }
(三)三分
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int n; double l,r; double a[14]; double calc(double a,double b) { double sum=1; for(int i=1;i<=b;i++)sum*=a; return sum; } int main() { scanf("%d%lf%lf",&n,&l,&r); for(int i=n;i>=0;i--)scanf("%lf",&a[i]); while(l+0.000001<=r) { double lmid=(l+r)/2; double rmid=(lmid+r)/2; double sum1=0,sum2=0; for(int i=n;i>=1;i--)sum1+=a[i]*calc(lmid,i),sum2+=a[i]*calc(rmid,i); sum1+=a[0];sum2+=a[0]; // printf(" f(%lf)=%lf f(%lf)=%lf ",lmid,sum1,rmid,sum2); sum1>sum2?r=rmid:l=lmid; } printf("%.5lf",l); }
(四)ST表
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int a[100010]; int f[100010][60]; int n,m; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); f[i][0]=a[i]; } int LC=floor(log(n)/log(2.0)); for(int j=1;j<=LC;++j) { for(int i=1;i<=n-(1<<j)+1;++i) { f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } for(int i=1;i<=m;i++) { int l,r; scanf("%d%d",&l,&r); int p=floor(log(r-l+1)/log(2)); printf("%d ",max(f[l][p],f[r-(1<<p)+1][p])); } return 0; }
(五)字符串相关
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char s[11100000]; char new_s[11100000<<1]; int f[11100000<<1]; int ans; int Init() { new_s[0]='$'; int k=1; int p=strlen(s); for(int i=0;i<p;i++) { new_s[k++]=s[i]; new_s[k++]='#'; } new_s[k]='