现在我们定义一个字符串序列 {S0,S1,S2,…} ，其中 S0=“A”,对于任意的 i>0，Si 可以由 Si-1 产生，具体产生方法为：替换 Si-1 中的每个字母“A”为“AAB”, 替换每一个字母“B”为“A”。
比如按照此规则，前五个字符串为： S0 = “A” S1 = “AAB” S2 = “AABAABA” S3 = “AABAABAAABAABAAAB” S4 = “AABAABAAABAABAAABAABAABAAABAABAAABAABAABA” 请问：在字符串 S100 中，第 k 个“A”出现的位置。
只有一行，一个正整数 k（1≤k＜231）。
只有一行，一个正整数，表示在字符串 S100 中，第 k 个“A”出现的位置。
输入
3输出
4【数据范围】 对于 20% 的数据，满足1≤k≤100 对于 60% 的数据，满足1≤k≤500 对于 100% 的数据，满足1≤k＜231
解题报告：
S0 = “A”
S1 = “AAB” = S0S0B
S2 = S1S1A = S1S1S0
因此得到：Si = Si-1Si-1Si-2 (i>1)
先求出Si-1和Si-2 分别包含A的个数，然后确定第k个A是出现在构成Si的三部分中的哪一部分，所以问题转化为在Si-1和 Si-2 中求第k个A的位置。
a[i]表示Si 中字母A的个数，b[i]表示Si 中字母B的个数，则Si 的长度可以表示成：len[i]:=a[i]+b[i]。
如果a[i-1]>=k，说明第k个A出现在Si的第一部分，只需要求出Si-1中第k个A出现的位置即可；
否则，如果2*a[i-1]>=k，说明我们需要的第k个A是出现在Si的第二部分，需要求Si-1中第k-a[i-1]个A出现的位置即可，然后再加上len[i-1]的偏移量。
如果不是以上两种情况，则说明第k个A是出现在Si的第三部分，需要求Si-2中第k-2*a[i-1]个A出现的位置即可，然后再加上2*len[i-1]的偏移量。
实现方法：递归。
a和b数组可以由Si的定义来递推计算
由于S0 =“A”，有a[0]=1 ,b[0]=0
因为 Si-1 中每个A都在Si 中产生2个A，而Si-1 中每个B都在Si 中变成了A，所以有：a[i]=2*a[i-1]+b[i-1];
因为 Si-1 中每个A都变成AAB，所以Si 中B的个数等于Si-1 中A的个数 ，即: b[i]=a[i-1]。
a[100]或b[100]会超过64位整数范围，注意到题目给出的k的范围是1≤k＜231，通过计算发现a[25] > 231，因此只需要从S25 中确定第k个A出现的位置即可。
时间复杂度：O(N)。
#include<iostream> #include<cstdio> long long a[26],b[26],len[26]; inline long long ca(int n,int k) { if(n==0) return 1; if(a[n-1]>=k) return ca(n-1,k); else if(2*a[n-1]>=k) return len[n-1]+ca(n-1,k-a[n-1]); else return 2*len[n-1]+ca(n-2,k-2*a[n-1]); } int main() { int k; a[0]=1; len[0]=1; for(int i=1;i<=25;++i) { a[i]=2*a[i-1]+b[i-1]; b[i]=a[i-1]; len[i]=a[i]+b[i]; } scanf("%d",&k); printf("%lld",ca(25,k)); return 0; } var a,b:array[0..26]of longint; len,k:longint; i,j:integer; begin read(k); a[0]:=1; b[0]:=0; len:=0; j:=1; for i:=1 to 26 do if(j=1)then begin a[i]:=a[i-1]+a[i-1]+b[i-1]; b[i]:=a[i-1]; end; while(k>1)do begin for i:=0 to 26 do if(a[i]>=k)and(a[i-1]<k)then begin k:=k-a[i-1]; len:=len+a[i-1]+b[i-1]; break; end; end; len:=len+1; write(len); end.
