hihoCoder - hiho字符串2 ---字符串的递归处理

xiaoxiao2021-02-28  10

时间限制: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); } } } } }
转载请注明原文地址: https://www.6miu.com/read-2350112.html

最新回复(0)