【hihocoder】 1717 hiho字符串3

地址

https://hihocoder.com/problemset/problem/1717

题目

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 我们定义第一代hiho字符串是"h"。第N代hiho字符串是由第N-1代hiho字符串变化得到,规则是在每一个h后插入i,i后插入o,o后插入h。 例如第二、三、四代hiho字符串分别是: "hi"、"hiio"和"hiioiooh"。 给定K,请你计算第100代hiho字符串中的第K个字符是什么。

输入 第一行包含一个整数T,代表测试数据的组数。 (1 ≤ T ≤ 10)
以下T行每行包含一个整数K。
对于50%的数据,1 ≤ K ≤ 1000000 对于100%的数据, 1 ≤ K ≤ 1000000000000000

输出 对于每组数据,输出一行,包含一个字符代表答案。

样例输入 2
3
7 样例输出 i
o

思路

字符串的数量是指数增长,所以求出100层的字符串不现实。所以从可以从第一层根据k的大小往下查找。 2100远远大于1e15,250刚好大于1e5,所以只需要考虑51层就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
const double pi=acos(-1.0);
const int K=1e5+7;
const int mod=1e9+7;

char nt[200];
LL p[100];
//end 51
void dfs(int n,LL k,char ca,char cb)
{
if(k==1)
{
printf("%c\n",ca);
return ;
}
else if(k==2)
{
printf("%c\n",cb);
return ;
}
if(p[51-n]<k)
dfs(n+1,k-=p[51-n],cb,nt[cb]);
else
dfs(n+1,k,ca,nt[ca]);
}

int main(void)
{
LL k,T;
cin>>T;
p[0]=1;
for(int i=1;i<=50;i++)
p[i]=p[i-1]*2;
nt['h']='i';
nt['i']='o';
nt['o']='h';
while(T--)
cin>>k,dfs(2,k,'h','i');
return 0;
}