自动搬运

查看原文

来自洛谷，原作者为

	chuzhitairan |（··）|··）|_·）|·）|）

搬运于2025-08-24 21:32:30，当前版本为作者最后更新于2020-05-28 17:47:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路和前面的大佬们都差不多：就是最开始有$n$个$1$，然后每次操作可以选出两个数相乘（基元对两两配对）再加一（产生一个额外的基元对），得到一个新数放回去······如此重复$n-1$次后只剩下一个数，要我们使得最后这个数尽量大。

怎么做呢？我们大概可以自然而然的想到，操作的次数是一定的，那越小的数留到后面就会越拖累别人，产生浪费，所以应该先让小数变大，即每次选出两个最小的数进行操作（就是贪心没有为什么（〃｀ 3′〃））。

然而在纸上算一下，发现$n$每增加$1$，结果就要扩大$1.5$倍左右，而$10000$次方告诉我们显然要用高精度，那我们就把高精模板打出来：

//写成一个类型方便配合STL
struct BigInt
{
	int num[5000],len;
    //不知道最大有多少位，先设大点无妨
	BigInt() {memset(num,0,sizeof(num));len=0;}
    //初始化一下避免出错
	void print() {for(int i=len;i;i--) printf("%d",num[i]);}
    //这题只需要输出不需要读入
    //然后是重载运算符
	BigInt operator + (const BigInt& b) const
	{
		int len=max(this->len,b.len),carry=0,now;BigInt c;
		for(int i=1;i<=len;i++)
		{
			now=this->num[i]+b.num[i]+carry;
			c.num[i]=now%10;carry=now/10;
		}
		if(carry) c.num[++len]=carry;
		c.len=len;
		return c;
	}
	BigInt operator * (const BigInt& b) const
	{
		BigInt d;
		for(int i=1;i<=this->len;i++)
		{
			int carry=0,now;BigInt c;
			for(int j=1;j<=b.len;j++)
			{
				now=b.num[j]*this->num[i]+carry;
				c.num[j+i-1]=now%10;carry=now/10;
			}
			if(carry) {c.num[b.len+i]=carry;c.len=b.len+i;}
			else c.len=b.len+i-1;
			d=d+c;
		}
		return d;
	}
};

我想说的是，其实这题完全可以高精配$\text{STL}$的$\text{priority\_queue}$的，而且代码并不复杂，只需再给$\text{BigInt}$类型定义一个 $<$ 即可（好像，$\text{STL}$的类型都只需要定义小于）。不过这题我们要用的是小根堆，当然你可以用$\text{greater}$，不过我就直接把 $<$ 定义成了$\geqslant$ ,效果是一样的╰(￣ω￣ｏ)。代码就多了这么一段：

bool operator < (const BigInt& b) const
{
	if(this->len!=b.len) return this->len>b.len;
	for(int i=this->len;i;i--) if(this->num[i]!=b.num[i]) return this->num[i]>b.num[i];
	return true;
}

不过正如前面的大佬所说，可能会有$\text{MLE}$的问题。那怎么办呢？其实可以取点巧，我们输出一下$n$为$10000$时答案的长度，刚好是$1770$，于是我把数位开到$1775$，提交，竟然就过了┗|｀O′|┛ ！ 但如果在多一点，比如$2000$，就会$\text{MLE}$。所以这种写法只是纯粹为了用堆，空间上还是队列的写法好ㄟ( ▔, ▔ )ㄏ

最终代码好像还稍微短那么一点点呢（难道我下意识的压行了？）：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct BigInt
{
	int num[1775],len;
	BigInt() {memset(num,0,sizeof(num));len=0;}
	void print() {for(int i=len;i;i--) printf("%d",num[i]);}
	BigInt operator + (const BigInt& b) const
	{
		int len=max(this->len,b.len),carry=0,now;BigInt c;
		for(int i=1;i<=len;i++)
		{
			now=this->num[i]+b.num[i]+carry;
			c.num[i]=now%10;carry=now/10;
		}
		if(carry) c.num[++len]=carry;
		c.len=len;
		return c;
	}
	BigInt operator * (const BigInt& b) const
	{
		BigInt d;
		for(int i=1;i<=this->len;i++)
		{
			int carry=0,now;BigInt c;
			for(int j=1;j<=b.len;j++)
			{
				now=b.num[j]*this->num[i]+carry;
				c.num[j+i-1]=now%10;carry=now/10;
			}
			if(carry) {c.num[b.len+i]=carry;c.len=b.len+i;}
			else c.len=b.len+i-1;
			d=d+c;
		}
		return d;
	}
	bool operator < (const BigInt& b) const
	{
		if(this->len!=b.len) return this->len>b.len;
		for(int i=this->len;i;i--) if(this->num[i]!=b.num[i]) return this->num[i]>b.num[i];
		return true;
	}
}One,A,B;
int n;
priority_queue<BigInt> q;
int main()
{
	scanf("%d",&n);
	One.num[1]=One.len=1;
	while(n--) q.push(One);
	while(q.size()>1) 
	{
		A=q.top();q.pop();
		B=q.top();q.pop();
		q.push(A*B+One);
	}
	A=q.top();A.print();
	return 0; 
}