排序

（只收录部分常用排序。）

冒泡排序

void maopaosort()
{
	for(int i=1;i<n;i++)
	{
		bool flag=0;
		for(int j=1;j<=n-i;j++)
		{
			if(a[j]>a[j+1])
			{
				swap(a[j],a[j+1]);
				flag=1;
			}
		}
		if(flag==0) break;
	}
}

快速排序

void quicksort(int a[],int l,int r)
{
	if(l>=r) return;
	int i=l,j=r;
	int mid=(l+r)/2;
	swap(a[l],a[mid]);
	int temp=a[l];
	while(i!=j)
	{
		while(a[j]>=temp&&i<j) j--;
		while(a[i]<=temp&&i<j) i++;
		if(i<j) swap(a[i],a[j]);
	}
	swap(a[i],a[l]);
	quicksort(a,l,i-1);
	quicksort(a,i+1,r);
}

归并排序

void mergesort(int a[],int l,int r)
{
	if(l>=r) return;
	int mid=(l+r)/2;
	mergesort(a,l,mid);
	mergesort(a,mid+1,r);
	int i=l,j=mid+1,cnt=l;
	while(i<=mid&&j<=r)
	{
		if(a[i]<a[j]) t[cnt++]=a[i++];
		else t[cnt++]=a[j++];
	}
	while(i<=mid) t[cnt++]=a[i++];
	while(j<=r) t[cnt++]=a[j++];
	for(int k=l;k<=r;k++) a[k]=t[k];
}

高精度

高精加

string add(string a,string b)
{
	int la=a.size(),lb=b.size();
	string ans;
	if(la>lb)
	for(int i=1;i<=la-lb;i++) b="0"+b;
	else
	for(int i=1;i<=lb-la;i++) a="0"+a;
	int l=a.size();
	int jw=0,temp,temp1,temp2;
	for(int i=l-1;i>=0;i--)
	{
		temp1=a[i]-'0';
		temp2=b[i]-'0';
		temp=temp1+temp2+jw;
		if(temp>=10){jw=1;temp%=10;}
		ans=char(temp+'0')+ans;
	}
	if(jw) ans="1"+ans;
	return ans;
}

高精乘

string mul(string a,string b)
{
	string s;
	int la=a.size(),lb=b.size();
	int aa[100005],bb[100005],cc[100005];
	memset(aa,0,sizeof(aa));
	memset(bb,0,sizeof(bb));
	memset(cc,0,sizeof(cc));
	for(int i=la-1;i>=0;i--)
		aa[la-i]=a[i]-'0';
	for(int i=lb-1;i>=0;i--)
		bb[lb-i]=b[i]-'0';
	for(int i=1;i<=la;i++)
		for(int j=1;j<=lb;j++)
			cc[i+j-1]=aa[i]*bb[j];
	for(int i=1;i<=la+lb;i++)
	{
		cc[i+1]=c[i]/=10;
		c[i]%=10;
	}
	if(c[la+lb]) ans+=char(c[la+lb]+'0');
	for(int i=la+lb-1;i>=1;i--)
		ans+=char(c[i]+'0');
	return ans;
}

快速幂+高精

string mul(string a,string b)
{
	string s;
	int la=a.size(),lb=b.size();
	int aa[100005],bb[100005],cc[100005];
	memset(aa,0,sizeof(aa));
	memset(bb,0,sizeof(bb));
	memset(cc,0,sizeof(cc));
	for(int i=la-1;i>=0;i--)
		aa[la-i]=a[i]-'0';
	for(int i=lb-1;i>=0;i--)
		bb[lb-i]=b[i]-'0';
	for(int i=1;i<=la;i++)
		for(int j=1;j<=lb;j++)
			cc[i+j-1]=aa[i]*bb[j];
	for(int i=1;i<=la+lb;i++)
	{
		cc[i+1]=c[i]/=10;
		c[i]%=10;
	}
	if(c[la+lb]) ans+=char(c[la+lb]+'0');
	for(int i=la+lb-1;i>=1;i--)
		ans+=char(c[i]+'0');
	return ans;
}
string ksm(string a,ll p)
{
	string ans="1";
	while(p)
	{
		if(p%2==1) ans=mul(ans,a);
		a=mul(a,a);
		p/=2;
	}
	return ans;
}

优化

cin cout 加速

  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

快读

int read() 
{
	int x=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') 
	{
		if(ch=='-')
			w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') 
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*w;
}

快写

void write(int x) 
{
	if(x<0) 
	{
		putchar('-');
		x=-x;
	}
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}