P2527[SHOI2001]Panda的烦恼（题解）

· · 题解

P.S.

此题较为毒瘤，需要开long long以及加优化。
普通的构造方法貌似不能过QwQ。

Problem.

给定一堆质因数，求这些质因数构成（乘积）的所有数中的第K小值。

Solution.

首先，我们一看到这道题，笔者第一时间想到要用STL中的set来构造。
于是就写了一个简单的代码（解释在代码注释中）。
因为小的数\times

#include<bits/stdc++.h>//万能头
using namespace std;
int n,k,a[105];set<int>s;//STL set万岁
int main()
{
    scanf("%d%d",&n,&k),s.insert(1);//插入1
    for(int i=1;i<=n;i++) scanf("%d",a+i);//读入n个质因数
    for(int i=1;i<k;i++)//因为要求第k大，所以要删去k-1个比它小的数
    {
        int t=*s.begin();s.erase(s.begin());//把当前最小的拿出来并删去
        for(int i=1;i<=n;i++) s.insert(t*a[i]);//构造出当前最小的能到达的所有数
    }
    return printf("%d\n",*s.begin()),0;//输出删去k-1个最小数后的第k个
}

然后结果我们一运行。。。\color{red}\texttt{WOC}\text{怎么样例都不过啊}
然后我们再来仔细读一读题目

比如说至多只包含质因数2，3的数有2,3,4,6,8,9,……

好罢被坑了，1是无法构造出来的，所以要求第k个质因数是第k+1个。
恭喜笔者绕过了第一个弯QAQ。

然后笔者再打出这样一份代码 

#include<bits/stdc++.h>
using namespace std;
int n,k,a[105];set<long long>s;
int main()
{
    scanf("%d%d",&n,&k),s.insert(1);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=1;i<=k;i++)//修改唯一一处：<k变成<=k
    {
        int t=*s.begin();s.erase(s.begin());
        for(int i=1;i<=n;i++) if(t*a[i]<=2000000000) s.insert(t*a[i]);
    }
    return printf("%lld\n",*s.begin()),0;
}

样例是过了，但是\color{red}\texttt{WOC}\text{为什么}\texttt{WA40}\text{啊}
笔者仔细地看了看错误信息。

Wrong Answer. wrong answer On line 1 column 1, read -, expected 6.

好罢，知道了，没开long long。
恭喜笔者绕过了第二个弯。

然后笔者又打出了第三份代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a[105];set<long long>s;//修改：int变成long long
int main()
{
    scanf("%d%d",&n,&k),s.insert(1);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=1;i<=k;i++)
    {
        long long t=*s.begin();s.erase(s.begin());//修改：int变成long long
        for(int i=1;i<=n;i++) s.insert(t*a[i]);
    }
    return printf("%lld\n",*s.begin()),0;
}

WA是不WA了，但是\color{red}\texttt{WOC}\text{为什么}\texttt{T}\text{了一个点啊}
笔者随便加了点优化。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[105];set<long long>s;
int main()
{
    scanf("%d%d",&n,&k),s.insert(1);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    sort(a+1,a+n+1);//排个序更快
    for(int i=1;i<=k;i++)
    {
        long long t=*s.begin();s.erase(s.begin());
        for(int i=1;i<=n;i++) if(t*a[i]<=2000000000) s.insert(t*a[i]);
        //因为题目中已经说了，保证答案不超过2000000000。
        //那么超过2000000000的肯定不需要加入set，一个优化
    }
    return printf("%lld\n",*s.begin()),0;
}

结果还是\color{red}\texttt{T}

于是笔者从整份代码来考虑，T的原因应该是在set中加入太多超过第K大的数了吧。
那么我们可以记录当前set的最大值。
如果的接下来构造的这个数已经大于最大值且set中有k个数了。
我们就可以break结束了。
然后加了这个优化之后，笔者顺利AC了这道题QAQ。

Coding.

#include<bits/stdc++.h>
using namespace std;
int n,k,f=1,a[105];long long mx,INF=2000000000;set<long long>s;
//f表示当前set中是否有k个数
int main()
{
    scanf("%d%d",&n,&k),s.insert(1);
    for(int i=1;i<=n;i++) scanf("%d",a+i),a[i]==1?(i--,n--):0;
    sort(a+1,a+n+1),mx=1;//最大值变成当前唯一的一个1
    for(int i=1;i<=k;i++)
    {
        long long t=*s.begin();s.erase(s.begin());
        for(int i=1;i<=n&&t*a[i]<=INF;i++) if(f||a[i]*t<=mx) s.insert(t*a[i]),mx=max(mx,t*a[i]);
        //首先，刚刚加的优化仍然有（在循环条件中）
        //然后，这个判断条件就是刚刚说的那个break的反条件QAQ
        f=((int)s.size()+i<=k);
        //更新f，检查加入后是否set中有k个数
    }
    return printf("%lld\n",*s.begin()),0;
}

Ending.

写题解辛苦，管理大大求过，无耻求赞