HDU 3130 17多校7 Kolakoski（思维简单）

Problem Description

This is Kolakosiki sequence:

th element.

Input

The first line contains a positive integer

Output

For each test case:
A single line contains a nonnegative integer, denoting the answer.

Sample Input

Sample Output

题意：

Kolakoski序列是一个仅由1和2组成的无限数列，是一种通过“自描述”来定义的数列[1] 。他的前几项为

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,…

它的定义很简单，若把数列中相同的数定为一组，令a(1)=1，a(2)=2，则a(n)等于第n组数的长度。

可以根据这个定义来推算第三项以后的数：例如由于a(2)=2，因此第2组数的长度是2，因此a(3)=2,；

由于a(3)=2，所以第三组数的长度是2，因此a(4)=a(5)=1；由于a(4)=1，a(5)=1，所以第四组数和第五组数的长度都为1，因此a(6)=2，a(7)=1，以此类推。

给出n求第n项的数字是多少

题解：

直接预处理根据性质算出序列

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<algorithm>
 6 #include<cmath>
 7 using namespace std;
 8 const int maxn=1e7+5;
 9 int a[maxn];
10 int b[maxn];
11 
12 void pre()
13 {
14     int cnta=1,cntb=1;
15     a[1]=1;b[1]=1;b[2]=2;
16     for(cnta=2,cntb=1;cnta<maxn&&cntb<maxn;cnta++)
17     {
18         a[cnta]=b[cnta];
19         if(a[cnta]==1)
20         {
21             if(b[cntb]==1)
22             {
23                 b[cntb+1]=2;
24             }
25             else
26             {
27                 b[cntb+1]=1;
28             }
29             cntb++;
30         }
31         else
32         {
33             if(b[cntb]==1)
34             {
35                 b[cntb+1]=2;
36                 b[cntb+2]=2;
37             }
38             else
39             {
40                 b[cntb+1]=1;
41                 b[cntb+2]=1;
42             }
43             cntb+=2;
44         }
45     }
46 }
47 
48 int main()
49 {
50     pre();
51     int T,n;
52     scanf("%d",&T);
53     while(T--)
54     {
55         scanf("%d",&n);
56         printf("%d
",b[n]);
57     }
58     return 0;
59 }

HDU 3130 17多校7 Kolakoski（思维简单）

相关推荐