题解 P1974 【基因聚合】

· · 题解

题目传送门

算法标签：贪心 （水） ，高精，队列（不是很多）

PART 1 ：题目解析

如果你认真读题，其实会发现 （废话一堆） 就一句话：

从n个1中，取出任意两个数相乘再加一，在序列删除两数并加入新的结果，问最后剩下的数的最大值。

PART 2 ：贪心

为什么这题要用贪心呢？（前提是你认真读题）

如果要求结果最大，那么我们期望每一步得到的结果都最大，则必须两个因数最大

既然要因数最大，那么我们就拿尽可能小的数进行操作，使得在底层获得的1更多，得到的结果不断叠加，则能够使结果最大

PART 3 ：高精

如果你仔细想想 （别问我怎么想的），答案会十分巨大

你不用高精，怎么办？？？

在处理高精部分时，我习惯用重载运算符的方法，具体实现见底部代码哦

（吐槽一下烦人的高精）

blog：重载运算符

大佬讲解：重载运算符

PART 4 ：队列

在贪心的基础上，我们很容易想到使用小根堆来实现

但是，堆/优先队列+高精 太 TM 恶心了，而且如果你非要用的话，不仅加大了码量，而且会MLE

怎么办呢?

我们发现，答案具有单调性，简单来说，就是每次操作都会得到第一大的数（你也可以认为这是贪心的理由）

所以，我们只需要用队列不就得了，保证了队列的前两个元素一定是最小的

但是，我们还会MLE

因为我们把高精的数组，一起存在了队列中，而且同时会占用O（n*(n+1)/2）的高精数组空间，那不就MLE了

既然如此，我们为什么不可以利用已经不要的数组空间呢

在此，我们就用队列，存储数组下标，毕竟我们不需要关心每个数的大小了

PART 5 ：代码 

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
struct pp{
    int l,g[3000];//l存长度，g存数字
    pp()//这里一定要初始化
    {
        l=0;
        memset(g,0,sizeof(g));
    }
    void print()
    {
        for(int i=l-1;i>=0;i--)//输出
                printf("%d",g[i]);
            printf("\n");
    }
}f[10010];
int n;
queue<int>q;//这里就存数组下标了
pp operator +(const pp &a,const pp &b)//重载运算符
{
    pp c;
    c.l=max(a.l,b.l);
    int x=0;
    for(int i=0;i<c.l;i++)//普通高精打法（贴板子）
    {
        c.g[i]=a.g[i]+b.g[i]+x;
        x=c.g[i]/10;
        c.g[i]%=10;
    }
    if(x>0) c.g[++c.l]=x;//进位
    return c;
}
pp operator *(const pp &a,const pp &b)//还是重载运算符
{
    pp c;
    for(int i=0;i<a.l;i++)
        for(int j=0;j<b.l;j++)
            c.g[i+j]+=a.g[i]*b.g[j];
    c.l=a.l+b.l-1;
    for(int i=0;i<c.l;i++)
    {        
        c.g[i+1]+=c.g[i]/10;
        c.g[i]=c.g[i]%10;
    }
    while(c.g[c.l++]);//注意这里的高精计算
    while(!c.g[c.l-1]) c.l--;//同上
    return c;
}
int main()
{
    scanf("%d",&n);
    pp k;
        int ans,anss;
    k.g[0]=1;
    k.l++;
    for(int i=1;i<=n;i++) q.push(i),f[i]=k;
    while(q.size()!=1)//留下最后的答案
    {
        ans=q.front();
        q.pop();
        anss=q.front();
        q.pop();
        f[ans]=f[ans]*f[anss];
        f[ans]=f[ans]+k;
        q.push(ans);
    }
    ans=q.front();
    f[ans].print();
    return 0;
}