P3612 [USACO17JAN] Secret Cow Code S题解

洛谷一道比较有意思的题目

P3612 [USACO17JAN] Secret Cow Code S

题面翻译

奶牛正在试验秘密代码，并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。

给定一个字符串，对字符串进行一次操作（每一次正确的操作，最后一个字符都会成为新的第一个字符），然后把操作后的字符串放到操作前的字符串的后面。也就是说，给定一个初始字符串，之后的每一步都会增加当前字符串的长度。

给定初始字符串和 $N$，请帮助奶牛计算无限字符串中位置为 $N$ 的字符。

第一行输入一个字符串。该字符串包含最多 $30$ 个大写字母，数据保证 $N \leq 10^{18}$。

第二行输入 一个整数 $N$。请注意，数据可能很大，放进一个标准的 $32$ 位整数容器可能不够，所以你可能要使用一个 $64$ 位的整数容器（例如，在 C/C++ 中是 long long）。

请输出从初始字符串生成的无限字符串中的下标为 $N$ 的字符。第一个字符的下标是 $N=1$。

感谢 @y_z_h 的翻译

题目描述

The cows are experimenting with secret codes, and have devised a method for creating an infinite-length string to be used as part of one of their codes.

Given a string $s$, let $F(s)$ be $s$ followed by $s$ “rotated” one character to the right (in a right rotation, the last character of $s$ rotates around and becomes the new first character). Given an initial string $s$, the cows build their infinite-length code string by repeatedly applying $F$; each step therefore doubles the length of the current string.

Given the initial string and an index $N$, please help the cows compute the character at the $N$th position within the infinite code string.

输入格式

The input consists of a single line containing a string followed by $N$. The string consists of at most 30 uppercase characters, and $N \leq 10^{18}$.

Note that $N$ may be too large to fit into a standard 32-bit integer, so you may want to use a 64-bit integer type (e.g., a “long long” in C/C++).

输出格式

Please output the $N$th character of the infinite code built from the initial string. The first character is $N=1$.

样例 #1

样例输入 #1

COW 8

样例输出 #1

C

提示

In this example, the initial string COW expands as follows:

COW -> COWWCO -> COWWCOOCOWWC

12345678

题解

直接暴力模拟会MLE，所以我们必须要考虑规律。

设最开始，即原字符串的长度为$len$

不难注意到，假设我们把一个字符串分割成A+B的部分，其中B是最后一个字符，那么经过一次操作之后，我们就会得到A+B+B+A的形式。

我们设某一时刻字符串的长度已经扩增到了$l$，且位置n恰好处于$l$的后半部分，也即这个时候的$l$恰好”扩增到了能够让s[n-1]有意义的情况“。

考虑第n个字符处于后半部分的A的情况，这个时候根据对称性我们不难发现n处的字符==n-$l$/2-1处的字符。

考虑第n个字符处于后半部分的B的情况，那么根据对称性我们可以把n倒推回n-1。

这样我们成功分治，把原问题转化成了多个子问题。

现在我们就可以让n不断地减小，直到$len$≥n的时候，就可以直接输出了。

也即使用一个while(len<n)的循环即可

代码实现如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,l;
string s;

int main(){
    cin>>s>>n;
    int len=s.length();
    //我们画个图可以发现，当字符串的长度l恰好递增到我们可以求出n的时候，有n处的字符与n-l/2-1处的相同
    //并且n-l/2-1恰好就在len的范围之内
    //如何实现将n不断往回倒成n-l/2-1？
    //还需要特判，当n正好卡在中间的时候，也即n=l/2+1时，n往回倒成n-1（因为中间两个相同）

    //我们需要的是一直往回倒，能倒到直接在最开始的字符串里面求出来
    //也就是说，我们需要先把l求到
    //然后这个时候的n-l/2-1可以保证一定是在开始的len范围之内的
    while(len<n){//假设字符串的长度不够,n开始就超标使得我们无法直接求出
        l=len; //l表示当前的字符串长度，这里开始递增
        while(n>l) l*=2;//当字符串的长度还不够整个包住n的时候，就一直翻倍
        //上面的循环结束的时候，就是恰好能够包住n了（k>=n）
        //依据上面的思路，我们需要n-l/2-1
        n-=l/2+1; //这样就实现了迭代，n在不断地减小，通过外层的while循环可以反复倒回去
        if(n==0) n=l/2; //即n=l/2+1时，n往回倒成n-1
    }
    cout<<s[n-1];
}