【寻找位置】

题目描述

现在我们定义一个字符串序列 {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”出现的位置。

样例数据 1

输入

3

输出

4

备注

【数据范围】
对于 20% 的数据,满足1≤k≤100
对于 60% 的数据,满足1≤k≤500
对于 100% 的数据,满足1≤k<231

开始直接打了个表过了60%……然而知道了题解才发现根本不用存字符串……,下面是题解:

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]表示S中字母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)。
总之感觉自己弱爆了…下面是代码:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*