求助95pt,第八个点TLE
  • 板块P2005 A/B Problem II
  • 楼主_TLP
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/6/22 12:35
  • 上次更新2023/11/3 13:22:34
查看原帖
求助95pt,第八个点TLE
456546
_TLP楼主2023/6/22 12:35

这是TLE的代码

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int N = 3e4;
string a, b;
int n[N], m[N], tmp[N], ans[N];
void init(int x[], string k)
{
	x[0] = k.size();
	int t = x[0];
	for(int i = 1; i <= x[0]; i ++) x[i] = k[t - i] - '0';
}
void enlarge(int x[], int y[], int c)
{
	y[0] = x[0] + c;
	for(int i = x[0]; i > 0; i --) y[i + c] = x[i];
}
int cmp(int x[], int y[])
{
	if(x[0] > y[0]) return 1;
	else if(x[0] < y[0]) return -1;
	else
	{
		for(int i = x[0]; i > 0; i --)
		{
			if(x[i] > y[i]) return 1;
			else if(x[i] < y[i]) return -1;
		}
		return 0;
	}
}
void print(int x[])
{
    while(x[0] > 1 && x[x[0]] == 0) x[0] --;
    for(int i = x[0]; i > 0; i --) printf("%d", x[i]);
    if(x[0] == 0) printf("0");
}
void sub(int x[], int y[])
{
    ans[0] = x[0] - y [0] + 1;
	for(int i = x[0] - y[0]; i >= 0; i --)
	{
	   
		enlarge(y, tmp, i);
		for(int c = cmp(x, tmp); c >= 0; c = cmp(x, tmp))
		{   
			for(int j = 1; j <= tmp[0]; j ++)
			{
				x[j] -= tmp[j];
				if(x[j] < 0)
				{
					x[j] += 10;
					x[j + 1] -= 1; 
				}
			}
			ans[i + 1] += 1;
			if(x[0] > 1 && x[x[0]] == 0) x[0] --;
		}
		memset(tmp, 0, sizeof(tmp));
	}
}
int main()
{
	cin >> a >> b;
	init(m, a); init(n, b);
    sub(m, n);
    print(ans);
	return 0;
}

这是之前写的AC代码,和后来写的形式差不多,但是不知道后来写的代码哪里慢了,希望大佬们指正

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=1e5+10;
int a[N],b[N],c[N],tmp[N],x=0;
string s1,s2;
void init(int q[],string s){
    q[0]=s.size();
    for(int i=1;i<=q[0];i++)q[i]=s[q[0]-i]-'0';
}
int cmp(int m[],int n[]){
    if(m[0]>n[0])return 1;
    if(m[0]<n[0])return -1;
    for(int i=m[0];i>=1;i--){
        if(m[i]>n[i])return 1;
        if(m[i]<n[i])return -1;
    }
    return 0;
}
void enlarge(int t[],int k[],int c){
    for(int i=1;i<=k[0];i++)t[i+c]=k[i];
    t[0]=k[0]+c;
}
void sub(int m[],int n[]){
    for(int i=1;i<=n[0];i++){
        m[i]-=n[i];
        if(m[i]<0){
            m[i+1]-=1;
            m[i]+=10;
        }
    }
    while(m[0]>1&&!m[m[0]])m[0]--;
}
void div(int m[],int n[]){
    c[0]=m[0]-n[0]+1;
    for(int i=c[0];i>=0;i--){
        enlarge(tmp,n,i);
        while(cmp(m,tmp)>=0){
            sub(m,tmp);
            c[i+1]+=1;
        }
        memset(tmp,0,sizeof(tmp));
    }
    while(c[0]>1&&!c[c[0]])c[0]--;
}
int main(){
    cin>>s1>>s2;
    init(a,s1);init(b,s2);
    div(a,b);
    for(int i=c[0];i>=1;i--)printf("%d",c[i]);
}
2023/6/22 12:35
加载中...