【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的大小往下查找。
2^100远远大于1e15，2^50刚好大于1e5,所以只需要考虑51层就可以了。

代码

#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;
}