我们定义第一代hiho字符串是"hiho"。
第N代hiho字符串是由第N-1代hiho字符串变化得到&＃xff0c;规则是&＃xff1a;
h -> hio
i -> hi
o -> ho
例如第二代hiho字符串是&＃xff1a; hiohihioho
第三代是&＃xff1a; hiohihohiohihiohihohioho
给定N和K&＃xff0c;请你计算第N代hiho字符串中的第K个字符是什么。
Input第一行包含一个整数T&＃xff0c;代表测试数据的组数。 (1 ≤ T ≤ 10)
以下T行每行包含两个整数N和K。
对于50%的数据&＃xff0c;每一组的N都满足 1 ≤ N ≤ 15
对于100%的数据&＃xff0c; 1 ≤ N ≤ 100, 1 ≤ K ≤ 1000000000
Output对于每组数据&＃xff0c;输出一行&＃xff0c;包含一个字符代表答案。
Sample Input
3
1 1
2 5
3 7
Sample Output
h
i
o
大意&＃xff1a;初始字符串为hiho&＃xff0c;一轮过后&＃xff0c;h变为hio&＃xff0c;i变成hi&＃xff0c;o变成ho
问N轮过后字符串中第K个字符是什么。
题解&＃xff1a;f[j][i]代表第 j 种字符经过 i-1 轮变换后变成了多少字符。&＃xff08;j&＃61;&＃61;1代表 h &＃xff0c;j&＃61;&＃61;2 代表 i ,j&＃61;&＃61;3代表 o&＃xff09;
然后划分第N轮的字符&＃xff0c;确定第K个在哪部分&＃xff0c;然后进入第N-1轮&＃xff0c;继续划分……很明显的递归性质。
1 /*
2 Welcome Hacking
3 Wish You High Rating
4 */
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include<string>
13 using namespace std;
14 int read(){
15 int xx&＃61;0,ff&＃61;1;char ch&＃61;getchar();
16 while(ch>&＃39;9&＃39;||ch<&＃39;0&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)ff&＃61;-1;ch&＃61;getchar();}
17 while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){xx&＃61;(xx<<3)&＃43;(xx<<1)&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}
18 return xx*ff;
19 }
20 const int limit&＃61;1000000000;
21 int T,N,K;
22 long long f[4][110];//h:1 i:2 o:3
23 void dfs(int arg,int depth,int sum){
24 if(depth&＃61;&＃61;1){
25 if(arg&＃61;&＃61;1)
26 printf("h\n");
27 else if(arg&＃61;&＃61;2)
28 printf("i\n");
29 else
30 printf("o\n");
31 return;
32 }
33 if(arg&＃61;&＃61;1){
34 if(sum<&＃61;f[1][depth-1])
35 dfs(1,depth-1,sum);
36 else{
37 sum-&＃61;f[1][depth-1];
38 if(sum<&＃61;f[2][depth-1])
39 dfs(2,depth-1,sum);
40 else{
41 sum-&＃61;f[2][depth-1];
42 dfs(3,depth-1,sum);
43 }
44 }
45 }
46 else if(arg&＃61;&＃61;2){
47 if(sum<&＃61;f[1][depth-1])
48 dfs(1,depth-1,sum);
49 else{
50 sum-&＃61;f[1][depth-1];
51 dfs(2,depth-1,sum);
52 }
53 }
54 else{
55 if(sum<&＃61;f[1][depth-1])
56 dfs(1,depth-1,sum);
57 else{
58 sum-&＃61;f[1][depth-1];
59 dfs(3,depth-1,sum);
60 }
61 }
62 }
63 int main(){
64 //freopen("in","r",stdin);
65 //freopen("out","w",stdout);
66 for(int i&＃61;1;i<&＃61;3;i&＃43;&＃43;)
67 f[i][1]&＃61;1;
68 for(int i&＃61;2;i<&＃61;100;i&＃43;&＃43;){
69 f[1][i]&＃61;f[1][i-1]&＃43;f[2][i-1]&＃43;f[3][i-1];
70 f[2][i]&＃61;f[1][i-1]&＃43;f[2][i-1];
71 f[3][i]&＃61;f[1][i-1]&＃43;f[3][i-1];
72 for(int j&＃61;1;j<&＃61;3;j&＃43;&＃43;)
73 if(f[j][i]>limit)
74 f[j][i]&＃61;limit&＃43;1;
75 }
76 T&＃61;read();
77 while(T--){
78 N&＃61;read(),K&＃61;read();
79 if(K<&＃61;f[1][N])
80 dfs(1,N,K);
81 else{
82 K-&＃61;f[1][N];
83 if(K<&＃61;f[2][N])
84 dfs(2,N,K);
85 else{
86 K-&＃61;f[2][N];
87 if(K<&＃61;f[1][N])
88 dfs(1,N,K);
89 else{
90 K-&＃61;f[1][N];
91 dfs(3,N,K);
92 }
93 }
94 }
95 }
96 return 0;
97 }
京公网安备 11010802041100号