题解 P3612 【[USACO17JAN]Secret Cow Code S】

· · 题解

题目链接

题目很好懂，就是对于任意一个字符串s，将它的最后一个字符 s[s.length()-1] 继续拼接到原字符串后，再把原字符串的 s[0] 到 s[s.length()-2] 拼接到自己的后面，形成一个新字符串。
eg. COW
COW WCO
COWWCO OCOWWC
因为数据范围是 N≤10^18 ，太大，所以直接模拟全部的字符串会爆空间，只能得到 40 分。
那么，不难想出，题目要我们给出的一个字符，那我们就只求这一个字符就可以了。 对于一个长度为 n 的字符串：

1,2,3,4,5，···n。（这个表示的是编号）

如果对它进行一次操作，就会变成：

1,2,3,4,5,···，n,n+1,n+2···2*n.

s[n]==s[n+1] , s[1] 到 s[n-1] 依次与 s[n+2] 到 s[2n] 相等。 如果我们要求一个规模为 2n 的问题，根据上面的对应相等原则，我们就可以把它转换成一个求规模为 n 的问题了。 因此，对于我们要求的第 k 位置上的字符，都只有两种情况：

（1） k 位于第 n+1 的位置上，那么我们就可以把它转换成一个求 k-1 位置上的字符的问题，因为 s[k] 与 s[k-1] 一定相等。

（2） k 不位于第 n+1 的位置上，而位于第 n+2 到第 2n 的位置上的一个。那么如果我们要让 n+2 与 1 相等的话，就要把 n+2 减去 n ，再减去一个 1 .考虑一下 n 为多少呢？ n 就是 s.length()2^x （ x 的取值要使 n 为小于 k 的最大值），因为每次操作都会增加 n 的长度，这种关系就是 2 ^ x 的函数关系，再乘以字符串长度，就是 n 的大小了。

这样问题就解决了，当我们要求的k不断缩小直到 k<s.length() 时，就可以直接输出了。

注意：在上文中我用的是 k ，在实际代码中我用的是题目中的 n ，即代码中的 n 就是题目中的 n 的意思，但在代码注释中我用的还是上文中的含义。（原谅本人的懒惰····

CODE:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
string s;
int length;
void work(long long n)
{
    if(n<=length)//边界条件：k<s.length()
    {
        cout<<s[n-1];
        return ;
    }
    long long i=length;//初始赋值为length，就不用在后面再乘了。
        while((i<<1)<n) i<<=1;//位运算更快，相当于i*2。
        n-=(i+1);
        if(n==0) n=i;//对于k在第n+1位置上的特判。
        work(n);//递归调用
}
int main()
{
    long long n;
    cin>>s>>n;
    length=s.length();
    work(n);
    return 0;
}