P2527 [SHOI2001]Panda的烦恼

题目描述

panda是个数学怪人,他非常喜欢研究跟别人相反的事情。最近他正在研究筛法,众所周知,对一个范围内的整数,经过筛法处理以后,剩下的全部都是质数,不过panda对这些不感兴趣,他只对被筛掉的数感兴趣,他觉得在这些被筛掉的数中一定隐藏着重要的宇宙秘密,只是人们还没有发现罢了。

panda还觉得如果只是单纯地从小到大筛的话,还不足够发现其中的奥秘,于是他决定对至多只包含某些质因数的数进行研究(比如说至多只包含质因数2,3的数有2,3,4,6,8,9,……),他需要得到这些数中第k小的数(k是panda认为的宇宙系数),请你编个程序,帮助他找到这个数。

输入输出格式

输入格式:

第1行有2个数n,k,n代表质因数的个数,k代表那个宇宙系数(1<=n<=100,1<=k<=100000)

第2行有n个数,代表这n个质因数。(每个均小于1000,且不相同)

输出格式:

仅1行,即至多只包含这n个质因数的数中第k小的数。(这个数不会超过2000000000)


一上来非常自信的打了优先队列BFS,出到第k的点时就输出答案。yy了一下复杂度感觉有点危险。

果然

洛谷 P2527 [SHOI2001]Panda的烦恼 解题报告-LMLPHP

开始我的卡常技巧,换上set(优先队列要加个map判重),玄学剪枝,register,读优等等

洛谷 P2527 [SHOI2001]Panda的烦恼 解题报告-LMLPHP

有点尴尬


瞅了一下题解,发现很巧妙。

为什么可以用优先队列set等等?因为要保证前面所有的数字都出来了

那么,这样做的缺点是什么?多加了很多没意义的数字

每个数字是怎么来的?给出的素数乘上优先队列里面的数字

每个素数当然要从小的开始乘,每个素数维护一个位置,表示这个素数现在应该乘上优先队列的第几位了。

当要加入一个新的数字的时候,找到素数与优先队列中最小的乘积,并更新位置与答案,注意去重


code:

#include <cstdio>
const int inf=0x7fffffff;
const int N=104;
int pri[N],cnt[N],f[100010],k,n,tot;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",pri+i);
f[0]=1;
while(tot<k)
{
int mi=inf,id;
for(int i=1;i<=n;i++)
if(pri[i]*f[cnt[i]]<mi)
{
mi=pri[i]*f[cnt[i]];
id=i;
}
cnt[id]++;
if(mi>f[tot]) f[++tot]=mi;
}
printf("%d\n",f[k]);
return 0;
}

2018.6.26

05-08 15:34