时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 我们定义第一代hiho字符串是”hiho”。 第N代hiho字符串是由第N-1代hiho字符串变化得到，规则是： h -> hio i -> hi o -> ho 例如第二代hiho字符串是： hiohihioho 第三代是： hiohihohiohihiohihohioho 给定N和K，请你计算第N代hiho字符串中的第K个字符是什么。 输入 第一行包含一个整数T，代表测试数据的组数。 (1 ≤ T ≤ 10) 以下T行每行包含两个整数N和K。 对于50%的数据，每一组的N都满足 1 ≤ N ≤ 15 对于100%的数据， 1 ≤ N ≤ 100, 1 ≤ K ≤ 1000000000 输出 对于每组数据，输出一行，包含一个字符代表答案。 样例输入 3 1 1 2 5 3 7 样例输出 h i o 思路 很明显的第n代的字符串与n-1代有关，用递归处理。 第一代是hiho，每次h->hio、i->hi、o->ho。我们可以预处理出，单个字符的第n代有生成了多少个字符，即ss[i][n]，i=0~2，其中0表示h，1表示i，2表示0，如ss[0][2]，表示字符h经过2代生成了ss[0][2]个字符。 代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL ss[3][105];//0是h,1是i,2是o int lim=1e9; void dfs(int type,int n,int k) { if(n==1){ if(type==0) cout<<'h'<<endl; else if(type==1) cout<<'i'<<endl; else cout<<'o'<<endl; return ; } if(type==0){ if(k<=ss[0][n-1]) dfs(0,n-1,k); else{ k-=ss[0][n-1]; if(k<=ss[1][n-1]) dfs(1,n-1,k); else{ k-=ss[1][n-1]; dfs(2,n-1,k); } } } if(type==1){ if(k<=ss[0][n-1]) dfs(0,n-1,k); else{ k-=ss[0][n-1]; dfs(1,n-1,k); } } if(type==2){ if(k<=ss[0][n-1]) dfs(0,n-1,k); else{ k-=ss[0][n-1]; dfs(2,n-1,k); } } } int main() { ss[0][1]=ss[1][1]=ss[2][1]=1; for(int i=2;i<=100;i++){//初始化 ss[0][i]=ss[0][i-1]+ss[1][i-1]+ss[2][i-1]; ss[1][i]=ss[0][i-1]+ss[1][i-1]; ss[2][i]=ss[0][i-1]+ss[2][i-1]; for(int j=0;j<3;j++){ if(ss[j][i]>lim) ss[j][i]=lim+1; } } int T; cin>>T; while(T--) { int n,k; cin>>n>>k; //hiho if(k<=ss[0][n]){ dfs(0,n,k); }else{ k-=ss[0][n]; if(k<=ss[1][n]){ dfs(1,n,k); }else{ k-=ss[1][n]; if(k<=ss[0][n]){ dfs(0,n,k); }else{ k-=ss[0][n]; dfs(2,n,k); } } } } }