P2723 丑数 Humble Numbers

admin

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

思维过程：
首先，最容易想到，不用动脑都可以想到的就是分解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

还是刚刚模拟的数：
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)：

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

子衿

#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

其实可以用优先队列的BFS，加上一个set判重，虽然有可能超时，但是训练一下BFS+SET也不错

1. #include <iostream>
   
2. #include <queue>
   
3. #include <set>
   
4. using namespace std;
   
5. priority_queue<int, vector<int>, greater<int> > a; ///定义小的在前的优先队列
   
6. set<int> b; ///定义一个集合判重
   
7. int i,k,n,s[110];
   
8. int x,y;
   
9. int main()
   
10. {
    
11.     cin>>k>>n;
    
12.     for (i=1; i<=k; i++) cin>>s[i];
    
13.     a.push(1); ///首元素进队
    
14.     b.insert(1);
    
15.     while (n--)
    
16.     {
    
17.         x=a.top();///取队首元素
    
18.         a.pop();///弹出
    
19.         for (i=1; i<=k; i++)
    
20.         {
    
21.             y=x*s[i];  ///生成儿子
    
22.             if (b.count(y)==0) /// 判重
    
23.             {
    
24.                 a.push(y); ///进队
    
25.                 b.insert(y);
    
26.             }
    
27.         }
    
28.     }
    
29.     cout<<a.top();
    
30.     return 0;
    
31. }
    

复制代码