题目
分析
首先是一些明确的事实。
- 原始字符串的长度
L不超过30，每进行一次操作，字符串的长度会翻倍，所以原始字符串进行N次操作后，长度变成\(L\times 2^N\)。 - 如果要生成这个最终的字符串，哪怕是最大的
unsigned long long都搞不定。 - 但是我们只是跟踪
N，所以用unsigned long long就够了。
然后看下算法过程。
- 我们要得到一个长度
size，它是比N大的最小长度。这样我们可以保证我们要找的第N个字符一定已经生成。 - 根据构造过程的描述，我们知道第
N个字符要么出现在前半段（原始字符串）或者后半段（所谓旋转操作后得到的、附加上去的字符串）。这个判定是通过N是否大于size/2=half进行判定的。 - 如果出现在前半段（\(N\le half\)），那么
N不用调整了。 - 如果出现在后半段（\(N\gt half\)），那么相对后半段来说，
N的位置要调整为N-half=pos_in_rotated，也就是N相对于后半段的位置。不过这里有两个情况：pos_in_rotated==1，这个位置是后半段的起始位置，根据题意，它就是原始字符串的最后一个字符，所以N要调整为half。pos_in_rotated!=1，这个位置不是后半段的起始位置，根据题意，它就是原始字符串的第pos_in_rotated-1个字符，所以N要调整为pos_in_rotated-1。
- 我们已经将
N调整到原始字符串的对应位置，所以可以取（前）半段字符串——也就是原始字符串再进行判定。而此时的原始字符串，是上一次操作得到的，它也是由更原始的字符串加上旋转字符串得到的。
核心代码如下：
while (size > L)
{
ull half = size / 2;
if (N > half)
{
ull pos_in_rotated = N - half;
if (pos_in_rotated == 1)
{
N = half;
}
else
{
N = pos_in_rotated - 1;
}
}
// Update size outside the if-else
size = half;
}答案
思考
这道题目代码不算太长，但体现了几个重要的算法和思想：
- 分治思想：代码通过将问题分解为更小的子问题来解决。它首先确定包含第N个字符的最小迭代大小，然后通过逆向追踪来确定该字符的原始位置。
- 二分查找的变体：算法使用了类似二分查找的方法来定位字符。它将字符串的大小不断减半，直到回到原始字符串的大小。
- 递归追踪：虽然代码中没有显式使用递归，但它使用了迭代方式实现的递归追踪思想，通过不断回溯来找到第N个字符在原始字符串中的位置。