Home > Old Blog Posts > USACO 3.1.3 Humble Numbers

USACO 3.1.3 Humble Numbers


这道题我脑袋一时短路看了题解..

下面是nocow上的官方题解译文

我们在数组hum中计算出前n个丑数。为了实现起来更简单,我们把1也作为一个丑数,算法也要因此略微调整一下。

当我们已知前k个丑数,想得到第k+1个,我们可以这样做:

对于每个质数p
	寻找最小的丑数h
	  使得 h * p 比上一个丑数大

取我们找到的 h * p 中最小的一个:它就是下一个丑数

为了使搜索更快,我们可以为每个质数维护一个索引“pindex”表示每个质数已经乘到了哪个丑数,每次都从那里开始,而不是再从头再来。

代码:

/*
ID: dementr1
PROG: humble
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“humble.in”);
ofstream fout(“humble.out”);
int humble[100001]={},p[101]={},pnow[101]={};
int K,N;
void init()
{
int i;
fin>>K>>N;
for(i=1;i<=K;i++) fin>>p[i];
fin.close();
}
void work()
{
int i,j,min,minj[100],tmp,counter=0;
humble[0]=1;
for(i=1;i<=N;i++)
{
min=2000000000;
for(j=1;j<=K;j++)
{
tmp=p[j]*humble[pnow[j]];
while(tmp<=humble[i-1])
{
tmp*=p[j];
}
if(tmp<min)
{
min=tmp;
counter=0;
minj[counter++]=j;
}
else if(tmp==min)
{
minj[counter++]=j;
}
}
humble[i]=min;
for(j=0;j<counter;j++) pnow[minj[j]]++;
}
fout<<humble[N]<<endl;
}
int main()
{
init();
work();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: