洛谷题单指南-递推与递归-P3612 [USACO17JAN] Secret Cow Code S

原题链接：https://www.luogu.com.cn/problem/P3612

题意解读：字符串加长的时候，是先把最后一个字符接上，再拼接其余字符，注意不是翻转，要找第n个字符，就要看字符串加长几次后长度能超过n，

然后在加长后的字符串中找第n个字符。

解题思路：

如果直接通过模拟法，字符串长度太长，且要找的第n个数值也太大，空间和时间都吃不消。

可以设定计算字符串加长k倍之后，长度为l时，可以找到第n个字符

如果n <= l / 2，说明在加长k倍的字符串前一半中就可以找到第n个字符，即在加长k-1倍的字符串中找第n个字符

如果n > l / 2，说明要在加长k倍的字符串后一半中才能找到第n个字符，而后一半和前一半的区别就在于后一半的第一个字符是前一半的最后一个字符

这样以来，在k倍长字符串中找第n个字符，就可以转化为在k-1倍长字符串中找第x个字符，x根据上述规则来计算

整个过程可以通过递归来实现。

100分代码：

#include <bits/stdc++.h>
using namespace std;

string s;
long long n;

//在长度是k倍原始长度、k倍后长度是l的字符串中，找第x个字符
char find(int k, long long l, long long x)
{
    if(k == 1) 
    {
        return s[x - 1];
    }
    if(x <= l / 2) return find(k - 1, l / 2, x); //如果x在l / 2范围内，则直接在k-1倍的字符串中找第x个字符
    else //否则x在两个k-1倍的字符串中
    {
        x = x -  l / 2; //在第二个k-1倍字符串中的位置
        if(x == 1) x = l / 2; //映射到第一个k-1倍字符串的位置，如果x % (l / 2)是1，表示对应最后一个字符
        else x = x - 1; //否则表示对应到第一个k-1倍字符串的第x % (l / 2) - 1个字符
        return find(k - 1, l / 2, x);
    }
}

int main()
{
    cin >> s >> n;
    long long len = s.length();
    int k = 1;
    while(len < n) //计算字符串加长k倍后，长度为len时可以找到第n个字符
    {
        len *= 2;
        k++;
    } 
    cout << find(k, len, n);
    return 0;
}