P1974 基因聚合

· · 题解

思路和前面的大佬们都差不多：就是最开始有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; 
}