蒟蒻70分求助!贪心+高精度,TLE最后三个点
查看原帖
蒟蒻70分求助!贪心+高精度,TLE最后三个点
549846
dpACerFXing楼主2023/6/23 18:15
# include<iostream>
# include<algorithm>
using namespace std;
const long long maxn=1001, maxai=10001;
struct Node{
	int a[maxai], b[maxai];
	int lena, lenb;
	int b2;
}coin[maxn];
int n;
int S[maxai], lens, mmax[maxai], len_mmax;
int comp(int a[], int b[], int lena, int lenb) {
	if(lena>lenb) return 1;
	else if(lena<lenb) return 2;
	else {
		for(int i=1; i<=lena; i++) {
			if(a[i]==b[i]) continue;
			else return ((a[i]>b[i])?1:2);
		}
		return 0;
	}
}
void copy(int a[], int lena, int *b, int& lenb) {
	for(int i=1; i<=lena; i++)
		b[i]=a[i];
	lenb=lena;
}
int multi(int *res, int a[], int b[], int lena, int lenb) {
	int a2[maxai], b2[maxai], c[maxai]={};
	for(int i=1; i<=lena; i++)
		a2[i]=a[lena-i+1];
	for(int i=1; i<=lenb; i++)
		b2[i]=b[lenb-i+1];
	for(int i=1; i<=lena; i++) {
		for(int j=1; j<=lenb; j++) {
			c[i+j-1]+=a2[i]*b2[j];
			if(c[i+j-1]>=10) {
				c[i+j]+=c[i+j-1]/10;
				c[i+j-1]%=10;
			}
		}
	}
	int lenc;
	if(c[lena+lenb]>0) lenc=lena+lenb;
	else lenc=lena+lenb-1;
	for(int i=1; i<=lenc; i++)
		res[i]=c[lenc-i+1];
	return lenc;
}
bool cmp(Node a, Node b) {
	int left_res[maxai], right_res[maxai];
	int left_len=multi(left_res, a.a, a.b, a.lena, a.lenb);
	int right_len=multi(right_res, b.a, b.b, b.lena, b.lenb);
	int comp_res=comp(left_res, right_res, left_len, right_len);
	if(comp_res==2) return true;
	else return false;
}
int dev(int *res, int a[], int lena, int b) {
	int temp=0, c[1001]={};
	for(int i=1; i<=lena; i++) {
		int target=temp*10+a[i];
		c[i]=target/b;
		temp=target%b;
	}
	int lenc=1;
	while(c[lenc]==0 && lenc<lena) lenc++;
	for(int i=lenc, j=1; i<=lena; i++, j++) {
		res[j]=c[i];
	}
	return lena-lenc+1;
}
int main() {
	cin >> n;
	for(int i=0; i<=n; i++) {
		string x, y; cin >> x >> y;
		for(int j=0; j<x.length(); j++)
			coin[i].a[j+1]=x[j]-'0';
		coin[i].lena=x.length();
		for(int j=0; j<y.length(); j++) {
			coin[i].b[j+1]=y[j]-'0';
			coin[i].b2=coin[i].b2*10+y[j]-'0';
		}
		coin[i].lenb=y.length();
	}
	sort(coin+1, coin+n+1, cmp);
	copy(coin[0].a, coin[0].lena, S, lens);
	lens=coin[0].lena;
	for(int i=1; i<=n-1; i++) {
		lens=multi(S, S, coin[i].a, lens, coin[i].lena);
	}
	int len_mmax=dev(mmax, S, lens, coin[n].b2);
	if(len_mmax==1 && mmax[1]==0) cout << 1 << endl;
	else for(int i=1; i<=len_mmax; i++) cout << mmax[i];
	return 0;
}

可以给两个关注qwq

2023/6/23 18:15
加载中...