转一篇好文：poj1338 poj2591 poj2545 这三道题

poj1338 poj2591 poj2545 这三道题

先来看1338

题目定义一种集合，使得其中的元素的素数因子只能是2，3，5

即：1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...

要求这个集合的第n个数是多少

很直接的想法，我们通过题目的要求预处理算出这样的集合，然后再输出第n个数

当然，我们在得到这样的一个数组num[]时，必须是从小到大的，其实这也是关键所在

这个集合是通过集合里的每一个数 × 2，× 3，× 5来扩展的，要想从小到大，从num[1]开始扩展时，由于× 2，× 3，× 5大小不同，所以num[]的下一个元素是这三个数的最小值。所以到下次时，2是在乘以新的元素，而3,5还在乘原来的元素，但这三个数比较后最小的继续添加进集合里。由于有了这样的延迟作用，我们可以设置三个指针p2,p3,p5分别指向2，3，5待乘的数。

要记得处理重复的数，在每扩展一个元素时，判断该数是否能通过其他数来乘得，是的话就右移p

参考自：http://acm.pku.edu.cn/JudgeOnline/showmessage?message_id=113667

代码：

#include<iostream>
using namespace std;
int main(){
 long long ans[1510] = {0,1};
 int p2 = 1,p3 = 1,p5 = 1;
 for(int i =2;i<=1500;i++){
  ans[i] = min(ans[p2]*2,min(ans[p3]*3,ans[p5]*5));

  //他们乘时有延迟，不同数有先乘后乘，但各自的p指向他们下次要乘的数
  if(ans[i]==2*ans[p2])p2++;
  if(ans[i]==3*ans[p3])p3++;
  if(ans[i]==5*ans[p5])p5++;
 }
 int n;
 while(cin>>n,n)cout<<ans[n]<<endl;
 return 0;
}

现在来看poj2591，只是定义集合的方式不同了而已：

Set S is defined as follows:
(1) 1 is in S;
(2) If x is in S, then 2x + 1 and 3x + 1 are also in S;
(3) No other element belongs to S.
代码

#include<iostream>
using namespace std;
int ans[10000010] = {0,1};
int main(){
 int p2 = 1,p3 = 1;
 for(int i =2;i<=10000000;i++){
  ans[i] = min(ans[p2]*2+1,ans[p3]*3+1);
  if(ans[i]==2*ans[p2]+1)p2++;
  if(ans[i]==3*ans[p3]+1)p3++;
 }
 int n;
 while(cin>>n)cout<<ans[n]<<endl;
 return 0;
}

poj2545

#include<iostream>
using namespace std;
long long num[1000000],a,b,c,pa,pb,pc,n;
int main()
{
    cin>>a>>b>>c>>n;
    num[0] = 1;
    pa=pb=pc =0;
    for (int i =1;i<=n;i++)
    {
        num[i] = min(num[pa]*a,min(num[pb]*b,num[pc]*c));
        if (num[i]==num[pa]*a)pa++;
        if (num[i]==num[pb]*b)pb++;
        if (num[i]==num[pc]*c)pc++;
    }
    cout<<num[n]<<endl;
return 0;
}

只要记住那加亮的核心代码就行了，就可以用来按照已给表达式来扩展集合，

主要是设置指针来使元素从小到大，且不重复！

附：poj1338用优先级队列和set实现的版本：

#include<iostream>
#include<queue>
using namespace std;

typedef pair<long long,int> node;//要用long long
int main(){
 vector<long long>ans;
 priority_queue<node,vector<node>,greater<node> > que;//最小堆
 que.push(make_pair(1,2));
 for(int i =1;i<=1500;i++){
    node top = que.top();//每次选最小的作为下一次的被乘数
    que.pop();
  //注意这里每个case后面没有break，这样处理可以避免重复的插入
  switch(top.second){//乘的时候是乘上一次乘时的质数开始，这样从小到大乘就不会重复了，不然大的又回去乘2
   case 2:que.push(make_pair(top.first*2,2));
   case 3:que.push(make_pair(top.first*3,3));
   case 5:que.push(make_pair(top.first*5,5));
    }
    ans.push_back(top.first);//将最小的数加入容器，以后这个容器才是从小到大的
 }
 int n;
 while(cin>>n,n)cout<<ans[n-1]<<endl;
 return 0;
}

#include<iostream>
#include<set>
using namespace std;
int main(){
 long long ans[1510];
 set<long long>se;
 se.insert(1);
 for(int i =1;i<=1500;i++){//set会自动处理重复的数！
    ans[i] = *se.begin();
    se.erase(se.begin());
    se.insert(ans[i]*2);
    se.insert(ans[i]*3);
    se.insert(ans[i]*5);
 }
 int n;
 while(cin>>n,n)cout<<ans[n]<<endl;
 return 0;
}