大佬求助!#10超时
查看原帖
大佬求助!#10超时
1160843
wuyu6688楼主2024/6/19 21:54
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int A[N],B[N],C[N],la,lb,lc;
void init(string a,string b) {
	la = a.size(), lb = b.size();
	memset(A, 0, sizeof(A));
	memset(B, 0, sizeof(B));
	memset(C, 0, sizeof(C));
	for(int i=0; i<la; i++) A[i]=a[i]-'0';
	for(int i=0; i<lb; i++) B[i]=b[i]-'0';
	reverse(A, A+la), reverse(B, B+lb);
}
bool cmp(string a , string b) 
{
	if(a.size() != b.size()) return a.size() > b.size();
	for(int i=0; i<a.size(); i++) 
	{
		if(a[i]!=b[i]) return a[i] > b[i];
	}
	return 1;
}
void xuebao1(string a,string b)
{
	int  h[N]={0} , p[N]={0} , k[N]={0};
	int t = max(a.size() , b.size());
	for(int i = 0; i < a.size(); i++)
	{
		h[a.size() - i - 1] = a[i] - '0';
	}
	for(int i = 0; i < b.size(); i++)
	{
		p[b.size() - i - 1] = b[i] - '0';
	}for(int i = 0; i < t; i++)
	{
			k[i] = p[i] + h[i];
	}
	for(int i = 0; i < t; i++)
	{
		if(k[i] >= 10)
		{
			k[i + 1] = k[i + 1] + k[i] / 10;
			k[i] = k[i] % 10;
			
		}
	}
	if(k[t] != 0)
	{
		t++;
	}
	for(int i = t - 1; i >= 0; i--)
	{
		cout << k[i];
	}
}
string xuebaoe(string a,string b) {
init(a, b);
lc = max(la, lb);
for(int i=0; i<lc; i++) 
{
C[i] = A[i]-B[i];
if(C[i]<0) 
{
	A[i+1]--, C[i]+=10;
}
}
while(lc>1 && C[lc-1]==0) 
{
	lc--;	
}
string c;
for(int i=lc-1; i>=0; i--) 
{
	c.append(1, C[i]+'0');
}
return c;
}
string xuebao3(string a,string b) 
{
	init(a,b);
	lc = la+lb-1;
	for(int i=0; i<la; i++) 
	{
	for(int j=0; j<lb; j++) 
	{
	C[i+j] += A[i]*B[j];
	}
	}
	for(int i=0; i<lc; i++) 
	{
		C[i+1] += C[i]/10, C[i] %= 10;
	}
	while(C[lc]) 
	{
		lc++;	
	}
	string c;
	for(int i=lc-1; i>=0; i--) 
	{
		c.append(1, C[i]+'0');	
	}
	return c;
}
void xuebao4(string a,string b) {
	string c, d;
	for(int i=0; i<a.size(); i++) 
	{
	d = d.append(1, a[i]);
	while(d.find('0')==0 && d.size()>1) d.erase(0, 1);
	if(cmp(d , b)) 
	{
		for(int k=9; k>=1; k--) 
		{
			string x;
			x.append(1, k+'0');
			x = xuebao3(x, b);
			if(cmp(d, x)) 
			{
				d = xuebaoe(d, x);
				c.append(1, k+'0');
				break;
			}
		}
	} 
	else c.append(1, '0');
	}
	while(c.find('0')==0 && c.size()>1) 
	{
		c.erase(0,1);	
	}
	cout << c << endl;
}
void xuebao5(string a,string b) {
	string c, d;
	for(int i=0; i<a.size(); i++) 
	{
	d = d.append(1, a[i]);
	while(d.find('0')==0 && d.size()>1) d.erase(0, 1);
	if(cmp(d , b)) 
	{
		for(int k=9; k>=1; k--) 
		{
			string x;
			x.append(1, k+'0');
			x = xuebao3(x, b);
			if(cmp(d, x)) 
			{
				d = xuebaoe(d, x);
				c.append(1, k+'0');
				break;
			}
		}
	} 
	else c.append(1, '0');
	}
	while(c.find('0')==0 && c.size()>1) 
	{
		c.erase(0,1);	
	}
	cout << d << endl;
}
void xuebao2(string a1,string b1)
{
int a[N] = {0}, b[N] = {0}, k[N] = {0};
	bool flag = 0;
	int sum = max(a1.size() , b1.size());
	if(a1.size() < b1.size() || a1 < b1 && a1.size() == b1.size())
	{
		flag = 1;
		swap(a1 , b1);
	}
	for(int i = a1.size(); i > 0; i--)
	{
		a[i] = a1[a1.size() - i] - '0';
	}
	for(int i = b1.size(); i > 0; i--)
	{
		b[i] = b1[b1.size() - i] - '0';
	}
	for(int i = 1; i <= sum; i++)
	{
		if(a[i] < b[i])
		{
			a[i + 1] --;
			a[i] += 10;
		}
		k[i] = a[i] - b[i];
	}
	while(k[sum] == 0 && sum > 1)
	{
		sum--;
	}
	if(flag)
	{
		cout << '-';
	}
	for(int i = sum; i > 0; i--)
	{
		cout << k[i];
	}
}
int main(){
	string a,b;
	cin >> a >> b;
	xuebao1(a , b);
	cout << endl;
	xuebao2(a , b);
	cout << endl;
	cout << xuebao3(a , b);
	cout << endl;
	xuebao4(a , b);
	xuebao5(a , b);
	return 0;
}
2024/6/19 21:54
加载中...