高精TLE求助
查看原帖
高精TLE求助
901195
__Luna__楼主2024/8/26 22:02
#include<iostream>
using namespace std;
struct Int
{
	short t;
	unsigned long long u,d;
	Int()
	{
		t=0;
		u=0;
		d=0; 
	} 
	Int(unsigned long long n)
	{
		t=0;
		u=0;
		d=n; 
	} 
	Int(short tt,unsigned long long uu,unsigned long long dd)
	{
		t=tt;
		u=uu;
		d=dd; 
	} 
	friend Int operator+(Int a,Int b)
	{
		a.t+=b.t;
		if (a.u>(((unsigned long long)(1)<<63)+~((unsigned long long)(1)<<63)-b.u))
		{
			a.t+=1;
		}
		a.u+=b.u;
		if (a.d>(((unsigned long long)(1)<<63)+~((unsigned long long)(1)<<63)-b.d))
		{
			if (a.u>(((unsigned long long)(1)<<63)+~((unsigned long long)(1)<<63)-1))
			{
				a.t+=1;
			}
			a.u+=1;
		}
		a.d+=b.d;
		return a;
	}
	friend void lshift(Int&a)
	{
		a.t<<=1;
		a.t+=(a.u&((unsigned long long)(1)<<63))>>63;
		a.u<<=1;
		a.u+=(a.d&((unsigned long long)(1)<<63))>>63;
		a.d<<=1;
	}
	friend void rshift(Int&a)
	{
		a.d>>=1;
		a.d+=(a.u&1)<<63;
		a.u>>=1;
		a.u+=(a.t&1)<<63;
		a.t>>=1;
	}
	friend Int operator*(Int a,Int b)
	{
		Int c;
		while(a.u>0||a.d>0)
		{
			if(a.d&1)
			{
				c=c+b;
			}
			lshift(b);
			rshift(a);
		}
		return c;
	}
	friend bool operator<=(Int a,Int b)
	{
		if(a.t==b.t)
		{
			if(a.u==b.u)
			{
				return a.d<=b.d;
			}
			return a.u<b.u;
		}
		return a.t<b.t;
	}
}dec_[42]={{0,0,1},
		   {0,0,10},
		   {0,0,100},
		   {0,0,1000},
		   {0,0,10000},
		   {0,0,100000},
		   {0,0,1000000},
		   {0,0,10000000},
		   {0,0,100000000},
		   {0,0,1000000000},
		   {0,0,10000000000},
		   {0,0,100000000000},
		   {0,0,1000000000000},
		   {0,0,10000000000000},
		   {0,0,100000000000000},
		   {0,0,1000000000000000},
		   {0,0,10000000000000000},
		   {0,0,100000000000000000},
		   {0,0,1000000000000000000},
		   {0,0,10000000000000000000},
		   {0,5,7766279631452241920},
		   {0,54,3875820019684212736},
		   {0,542,1864712049423024128},
		   {0,5421,200376420520689664},
		   {0,54210,2003764205206896640},
		   {0,542101,1590897978359414784},
		   {0,5421010,15908979783594147840},
		   {0,54210108,11515845246265065472},
		   {0,542101086,4477988020393345024},
		   {0,5421010862,7886392056514347008},
		   {0,54210108624,5076944270305263616},
		   {0,542101086242,13875954555633532928},
		   {0,5421010862427,9632337040368467968},
		   {0,54210108624275,4089650035136921600},
		   {0,542101086242752,4003012203950112768},
		   {0,5421010862427522,3136633892082024448},
		   {0,54210108624275221,12919594847110692864},
		   {0,542101086242752217,68739955140067328},
		   {0,5421010862427522170,687399551400673280},
		   {2,17316620476856118468,6873995514006732800},
		   {29,7145508105175220139,13399722918938673152},
		   {293,16114848830623546549,4870020673419870208}};
ostream& operator<<(ostream& out, Int a)
{
   	Int j=0;
   	bool zero_=0;
   	for(int i=41;i>=0;i--)
   	{
   		int t=0;
   		for(Int k=j;k<=a;j=k,k=k+dec_[i],t++);
   		t--;
   		if(t)
   		{
   			out<<t;
   			zero_=1;
		}
		else if(i==0||zero_)
		{
			out<<0;
		}
	}
}
Int dp[41][6];
int num[41];
int n,k;
Int getn(int l,int r)
{
	Int rt=0;
	for(int i=l;i<=r;i++)
	{
		rt=rt*10;
		rt=rt+num[i];
	}
	return rt;
} 
int main()
{
    cin>>n>>k;
    Int l=0;
    for(int i=1;i<=n;i++)
    {
    	char j;
		cin>>j;
		num[i]=j-'0'; 
		l=l*10;
		l=l+num[i];
		dp[i][0]=l;
	}
	for(int i=1;i<=k;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int l=1;l<j;l++)
			{
				dp[j][i]=dp[j][i]<=dp[l][i-1]*getn(l+1,j)?dp[l][i-1]*getn(l+1,j):dp[j][i];
			}
		}
	} 
	cout<<dp[n][k]<<endl;
    return 0;
}

这不是一个常规的高精。从理论上和测试样例上,它都是可行的,但是很不幸所有点都T了。
我知道正常的高精怎么写,不需要教我。我只是想知道,这种高精TLE的原因。

2024/8/26 22:02
加载中...