##帮帮本蒟蒻,怎么优化时间复杂度##
查看原帖
##帮帮本蒟蒻,怎么优化时间复杂度##
514936
EllinY楼主2022/8/10 11:15

大佬们,康康我的TLE代码,我正在想怎么优化 可是真的想不出来啊 HELP!

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000010],b[1000010],c[1000010];
string ans1,ans2,ans3;
string mult(string s1,int s2){
//高精度乘法,字符串*整数,无误 
	reverse(s1.begin(),s1.end());
	int lena=s1.size()-1;
	int lenb=-1;
	memset(c,0,sizeof(c));
	for(int i=0;i<=lena;i++){
		a[i]=s1[i]-'0';
	}
	while(s2){
		b[++lenb]=s2%10;
		s2/=10;
	}
	int lenc=lena+lenb+1;
	for(int i=0;i<=lena;i++){
		for(int j=0;j<=lenb;j++){
			c[i+j]+=a[i]*b[j];
			c[i+j+1]+=c[i+j]/10;
			c[i+j]%=10;
		}
	}
	while(c[lenc]==0&&lenc>0){
		lenc--;
	}
	string r="";
	for(int i=lenc;i>=0;i--){
		char ch='0'+c[i];
		r=r+ch; 
	}
	return r; 
}
string minu(string s1,string s2){
//高精度减法,字符串-字符串,无误 
	reverse(s1.begin(),s1.end());
	reverse(s2.begin(),s2.end());
	int lena=s1.size()-1;
	int lenb=s2.size()-1;
	memset(c,0,sizeof(c));
	for(int i=0;i<=lena;i++){
		a[i]=s1[i]-'0';
	}
	for(int i=0;i<=lenb;i++){
		b[i]=s2[i]-'0';
	}
	for(int i=0;i<=lena;i++){
		if(a[i]<b[i]){
			a[i]+=10;
			a[i+1]--;
		}
		c[i]=a[i]-b[i];
	}
	int lenc=lena;
	while(c[lenc]==0&&lenc>0){
		lenc--;
	}
	string r="";
	for(int i=lenc;i>=0;i--){
		char ch='0'+c[i];
		r=r+ch; 
	}
	return r; 
}
int main(){
	cin>>n>>m;
	ans1="1";
	for(int i=1;i<=n+2;i++){
		ans1=mult(ans1,i);
		if(i==n+1) ans2=ans1;
		//后面会用到
      //把老师捆绑起来,
      //加上男生的排列情况,后面会乘二 
	}//先把老师当男的 
	for(int i=n+3;i>n+3-m;i--){
		ans1=mult(ans1,i);
	}//把女生插入男生和老师中 
	
	ans2=mult(ans2,2);//老师的排列情况 
	for(int i=n+2;i>n+2-m;i--){
		ans2=mult(ans2,i);
	}
   //把女生插入男生和老师中,不能插在老师中间 
	ans3=minu(ans1,ans2);
   //排除老师相邻的情况 
	cout<<ans3<<endl;
	return 0;
}
2022/8/10 11:15
加载中...