1006
轉一篇好文：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
參考自：https://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;
}
最後更新：2017-04-03 14:53:55