[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;
}

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41/**
 * 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-08-14 15:08
 * update_at: 2026-08-14 15:08
 */
#include <iostream>
#include <string>

std::string s;       // 初始字符串
long long base_len;  // 初始字符串的长度
long long n;         // 要找第 n 个字符（n 可能达到 1e18，必须用 long long）

// 在长度为 len 的串中找第 pos 个字符：
// 后半段等于前半段整体右移一位，所以把 pos 映射回前半段，问题规模折半
char find(long long pos, long long len) {
    if (pos <= base_len) { // 已经落回初始字符串内，直接返回
        return s[pos - 1];
    }
    long long half = len / 2;
    if (pos == half + 1) { // 后半段第 1 个字符来自前半段最后一个字符
        pos = half;
    } else if (pos > half + 1) { // 其余位置比前半段对应位置多 1
        pos = pos - half - 1;
    }
    return find(pos, half);
}

int main() {
    std::cin >> s >> n;
    base_len = static_cast<long long>(s.size());

    long long len = base_len;
    while (len < n) { // 倍增到第一个不小于 n 的长度
        len *= 2;
    }

    std::cout << find(n, len) << '\n';
    return 0;
}

复杂度

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

总结

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

[USACO17JAN] Secret Cow Code S

目录

题意

思路

位置映射示例

Python 知识

代码

Guide 风格代码

复杂度

总结