首页 > 代码库 > 集合元素

集合元素

2024-11-05 13:16:02   204人阅读

2407 集合元素

Time Limit : 2000/1000 MS(Java/Others) | Memory Limit :65312/32656 KB(Java/Others)

Submits : 30 | Solved : 7

 

Description

已知集合A定义如下：
（1）1属于A，2属于A；
（2）若x和y都属于A则2x+3y也属于A；
（3）再无其他数属于A。
试求集合A中元素从小到大排列的序列的前n项。

 

 

Input

有多组测试，每组输入一个正整数n（n<=1000）。

 

 

Output

输出集合A中符合题意的前n项，输出格式如样例。

 

 

Sample Input

1
2
3

 

 

Sample Output

1->end
1->2->end
1->2->5->end

思路：可以估计前1000个数可以由最小的500个数组合得到。

代码：

 1 #include "cstdio"
 2 #include "algorithm"
 3 #include "string"
 4 #include "cstring"
 5 #include "queue"
 6 #include "cmath"
 7 #include "vector"
 8 #include "map"
 9 #include "stdlib.h"
10 #include "set"
11 #define mj
12 #define db double
13 #define ll long long
14 using  namespace std;
15 const int N=5e3+5;
16 int a[N];
17 bool f[N];
18 int main()
19 {
20 //#ifdef mj
21 //freopen("data.in","r",stdin);
22 //freopen("data.out","w",stdout);
23 //#endif // mj
24     int n;
25     a[0]=1,a[1]=2;
26     memset(f,0,sizeof(f));
27     int cnt=2;
28     for(int ii=0;ii<5;ii++){
29         for(int i=0;i<cnt && i<500;i++ ){//i<500!!
30             for(int j=0;j<cnt && j<500;j++){//j<500!!
31                     if(cnt<N-10)
32                     {
33                             int v=a[i]*2+a[j]*3;
34                             if(v<N&&!f[v]){
35                                 a[cnt++]=v;
36                                 f[v]=1;
37                             }
38                     }
39             }
40         }
41         sort(a,a+cnt);
42     }
43     while(scanf("%d",&n)==1)
44     {
45         for(int i=0;i<n-1;i++){
46             printf("%d->",a[i]);
47         }
48         printf("%d->end\n",a[n-1]);
49     }
50     return 0;
51 
52 }

 

集合元素


联系
我们