本文主要是介绍USACO Section 3.1 Humble Numbers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
已知一个集合S 由S的任意子集作为因子 可构造出一个数字 求 这些构造出的数字中第k大的数字是多少
思路：
拿到这题就被“数字不是很多而且比较连续暴力枚举就好”这个思路迷惑了 果断TLE…
跪了一次后想到通过bfs构造可取 这时用了queue维护bfs 用priority_queue维护答案（大顶堆 内部最多k个数字） 用set判重复（5*2=2*5） 写法不优秀还是TLE…
之后想到了2个剪枝 1.利用S单调性减少判重 2.利用新搜出结果的暂时单调性减少搜索数量
第三次提交终于AC了… （我知道这题让我做水了…）
代码：
/*
ID: housera1
PROG: humble
LANG: C++
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;struct node
{ll val;int pos;
}now;
int n,m;
ll p[110];
queue<node> bf;
priority_queue<ll> qu;void bfs()
{int i,amt;ll tmp,val;now.val=1,now.pos=1;bf.push(now);while(!bf.empty()){now=bf.front();val=now.val;bf.pop();for(i=now.pos;i<=n;i++) //剪枝1 {tmp=val*p[i];if(tmp!=1LL){amt=qu.size();if(amt<m){qu.push(tmp);now.val=tmp;now.pos=i;bf.push(now);}else if(amt==m&&qu.top()>tmp){qu.pop();qu.push(tmp);now.val=tmp;now.pos=i;bf.push(now);}else break; //剪枝2 }}}
}int main(){int Debug=0;if(!Debug){freopen("humble.in","r",stdin);freopen("humble.out","w",stdout);}int i,j;//clock_t bg=clock();while(!qu.empty()) qu.pop();while(!bf.empty()) bf.pop();scanf("%d%d",&n,&m);for(i=1;i<=n;i++) scanf("%lld",&p[i]);sort(p+1,p+1+n);bfs();printf("%lld\n",qu.top());//clock_t fi=clock();//printf("time is %d\n",fi-bg);return 0;
}
这篇关于USACO Section 3.1 Humble Numbers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
