华师一附中OI组

标题: P2723 丑数 Humble Numbers [打印本页]

作者: admin 时间: 2018-5-17 13:33
标题: P2723 丑数 Humble Numbers
https://www.luogu.org/problemnew/show/P2723

题目背景
对于一给定的素数集合 S = {p1, p2, ..., pK},考虑一个正整数集合，该集合中任一元素的质因数全部属于S。这个正整数集合包括，p1、p1*p2、p1*p1、p1*p2*p3...(还有其它)。该集合被称为S集合的“丑数集合”。注意：我们认为1不是一个丑数。

题目描述
你的工作是对于输入的集合S去寻找“丑数集合”中的第N个“丑数”。所有答案可以用longint(32位整数)存储。

补充：丑数集合中每个数从小到大排列，每个丑数都是素数集合中的数的乘积，第N个“丑数”就是在能由素数集合中的数相乘得来的（包括它本身）第n小的数。

输入输出格式
输入格式：
第 1 行: 二个被空格分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000.

第 2 行: K 个被空格分开的整数:集合S的元素

输出格式：
单独的一行，输出对于输入的S的第N个丑数。

输入输出样例
输入样例#1：
4 19
2 3 5 7
输出样例#1：
27
说明
题目翻译来自NOCOW。

USACO Training Section 3.1

作者: admin 时间: 2018-9-8 17:17
思维过程：
首先，最容易想到，不用动脑都可以想到的就是分解i的质因数是否是丑数，然后再inc(ans)，判断ans=n的时候输出i。这样显然对于大规模数据是会超时的。

我们可以进一步优化，当我们把19个丑数列出来时：
num=2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27
tot =1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
你会发现，其实
4是由两个2组成的
6是由2,3组成的
8是由2,4组成的
9是由3,3组成的
10是由2,5组成的...
这些所组成的数，都是由前面的丑数*a[k]得来的，所以可以得到如下的一个算法：
判断当前是由前面哪个丑数乘以a[k]得来的最小值且大于第i-1个丑数的丑数。
但是这样还是不能过全部的解。要如何优化呢？

作者: admin 时间: 2018-9-8 17:18
还是刚刚模拟的数：
num=2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27
tot=1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
我们先来看一下为什么上面的算法会慢，例如当判断第19个丑数的时候，你还要从第1个丑数开始判断，这样肯定慢了，因为第一个丑数2乘以任何a[i]都不可能大于第18个丑数，第二个、第三个、第四个也一样——27肯定是由第8个丑数与3构成的。
还可以这样理解：当前a[2]=3,3与第4个丑数构成了第12个丑数，那么，请问，接下来的丑数构成，3与第4个丑数还有可能构成吗？3只有可能与第5个丑数构成，当然这不一定能构成，但至少可以判断3不可能与前4个丑数构成了。
所以可以得出如下结论：
判断当前第i个丑数是什么值之后，再判断是由哪个丑数乘以哪个a[i]构成的，然后再把i所可能构成的丑数的位数+1.以此类推，可以得到最优解，效率O(nk)：

所以题目要一步步的做，大家也要认真揣摩。

作者: 子衿 时间: 2018-9-14 18:04
#include<bits/stdc++.h>
using namespace std;
int k,n;
int a[100000000];
bool b[10000000000];
int w=0;

bool pai(int j,int xx)
{
int nn=j;
int t=1;
while(nn>=a[1])
{
for(int i=xx;i>=1;i--)
         if(nn%i==0)
   nn/=a[i];
}
if(nn==0)
return true;
else
return false;
}

void dfs(int x)
{
if(w==1)
      return;
if(x==n)
{
   sort(a,a+x+1);
   cout<<a[n];
   w=1;
   return;
}
else

for(int i=a[x-1]+1;i<=2*a[x-1];i++)
if(!b[i]&&pai(i,x-1))
{
a[x]=i;
b[i]=1;
dfs(x+1);
if(w==1)
      return;
}
}

int main()
{
cin>>k>>n;
for(int i=1;i<=k;i++)
   {
      cin>>a[i];
      b[a[i]]=1;
   }
sort(a,a+k+1);
dfs(k+1);
return 0;
}

水一点积分

作者: admin 时间: 2018-9-15 23:11
其实可以用优先队列的BFS，加上一个set判重，虽然有可能超时，但是训练一下BFS+SET也不错

#include <iostream>
#include <queue>
#include <set>
using namespace std;
priority_queue<int, vector<int>, greater<int> > a; ///定义小的在前的优先队列
set<int> b; ///定义一个集合判重
int i,k,n,s[110];
int x,y;
int main()
{
cin>>k>>n;
for (i=1; i<=k; i++) cin>>s[i];
a.push(1); ///首元素进队
b.insert(1);
while (n--)
{
x=a.top();///取队首元素
a.pop();///弹出
for (i=1; i<=k; i++)
{
y=x*s[i]; ///生成儿子
if (b.count(y)==0) /// 判重
{
a.push(y); ///进队
b.insert(y);
}
}
}
cout<<a.top();
return 0;
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)