树分枝问题（Kolakoski）

2024-02-14 15:48

文章标签 问题分枝 kolakoski

本文主要是介绍树分枝问题（Kolakoski），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
Problem - 6130
http://acm.hdu.edu.cn/showproblem.php?pid=6130
Kolakoski
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 766 Accepted Submission(s): 408

Problem Description

This is Kolakosiki sequence: 1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1……. This sequence consists of 1 and 2, and its first term equals 1. Besides, if you see adjacent and equal terms as one group, you will get 1,22,11,2,1,22,1,22,11,2,11,22,1……. Count number of terms in every group, you will get the sequence itself. Now, the sequence can be uniquely determined. Please tell HazelFan its nth element.

Input

The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.
For each test case:
A single line contains a positive integer n(1≤n≤107).

Output

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

Sample Input

2
1
2

Sample Output

1
2
题意：，有一个数列，他是这样的：1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1……. 。并且还符合这种规律：1,22,11,2,1,22,1,22,11,2,11,22,1…….。问你输入n，输出原数列的第你项。
思路：刚开始一直没看懂，后来终于明白了。变化后的数列，每一小组的数量个数刚好等于前面那个数列的数。比如，第二个数列的第二小组的22长度是2等于第一个数列的第二项。我的方法，建立一个数组。然后他的每一项可以决定当前的要存的数。比如：下图
这里写图片描述
（画的有点丑，箭头符合表示，那个数决定那个）
看不懂，可以自己模拟一小，
代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[10000001];
int main(){a[1]=1;a[2]=2;int i,j;int n;int k;k=3;for(i=2;i<10000001,k<10000001;i++){if(a[i]==1){if(a[k-1]==1)a[k++]=2;else a[k++]=1;}else {a[k]=a[k-1];k++; if(k>=10000001)break;if(a[k-1]==1)a[k++]=2;else a[k++]=1;}
}int t;cin>>t;while(t--){cin>>n;cout<<a[n]<<endl;}return 0;
}