[USACO17JAN] Secret Cow Code S

题意

给定初始字符串 s。每次把当前字符串变成：

text

1s + rotate_right(s)

长度不断翻倍。给定位置 N，求无限扩展字符串中第 N 个字符。

思路

不能真的构造字符串，因为 N 可以到 10^18。

先找到一个长度 length，使扩展后的字符串长度至少覆盖目标位置。当前字符串由两半组成：

前半：上一轮字符串；
后半：上一轮字符串右旋一位。

如果目标在后半，设后半中的位置为 j = position - half：

j == 1 时，对应上一轮的最后一个字符；
j > 1 时，对应上一轮的第 j-1 个字符。

这样不断把 position 映射回上一轮，直到落回原始字符串。

位置映射示例

样例 COW：

text

1COW -> COWWCO -> COWWCOOCOWWC

第 8 位在长度 12 的字符串中。前半长度 6，后半位置 2，映射回上一轮位置 1，也就是 C。

Python 知识

Python int 可以直接保存 10^18。
只维护 position 和当前长度，不保存扩展字符串。
input().split() 可以读取字符串和数字两个字段。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16text, position_text = input().split()
position = int(position_text)

length = len(text)
while length < position:
    length *= 2

while position > len(text):
    half = length // 2
    if position == half + 1:
        position = half
    elif position > half + 1:
        position = position - half - 1
    length = half

print(text[position - 1])

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

string s;
long long n;

int main() {
    cin >> s >> n;
    long long len = s.size();
    while (len < n) len *= 2;
    while (n > (int)s.size()) {
        long long half = len / 2;
        if (n == half + 1) n = half;
        else if (n > half + 1) n = n - half - 1;
        len = half;
    }
    cout << s[n - 1] << endl;
    return 0;
}

复杂度

长度每次减半，所以时间复杂度为 $O(\log N)$ ，空间复杂度为 $O(1)$ 。

总结

遇到指数级增长的字符串，优先考虑“反推位置”而不是构造内容。

[USACO17JAN] Secret Cow Code S

目录

题意

思路

位置映射示例

Python 知识

代码

复杂度

总结