题目:P3612 [USACO17JAN] Secret Cow Code S
题面翻译
奶牛正在试验秘密代码,并设计了一种方法来创建一个无限长的字符串作为其代码的一部分使用。
给定一个字符串,对字符串进行一次操作(每一次正确的操作,最后一个字符都会成为新的第一个字符),然后把操作后的字符串放到操作前的字符串的后面。也就是说,给定一个初始字符串,之后的每一步都会增加当前字符串的长度。
给定初始字符串和N,请帮助奶牛计算无限字符串中位置为 N 的字符。
第一行输入一个字符串。该字符串包含最多 30 个大写字母,数据保证 N <= 1e18。
第二行输入 一个整数 N。请注意,数据可能很大,放进一个标准的 $32$ 位整数容器可能不够,所以你可能要使用一个 64位的整数容器(例如,在 C/C++ 中是 long long
)。
请输出从初始字符串生成的无限字符串中的下标为 N 的字符。第一个字符的下标是 N=1。
感谢 @y_z_h 的翻译
样例 #1
样例输入 #1
COW 8
样例输出 #1
C
提示
COW -> COWWCO -> COWWCOOCOWWC
12345678
原题链接
思路:
看的洛谷题解写出来的,只能说我比较笨,虽然看懂了,但是不会解释,具体看看大佬的文章吧:https://www.luogu.com.cn/article/s28ealwz
方法一:
点击查看代码
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define ll long long
#define el '\n'
using namespace std;
const int N = 1e5 + 5;
string str;
ll n;
void solve()
{
cin >> str >> n;
int num = str.size();
while (num < n) {
ll i = num;
while (i < n) i *= 2;
n -= i / 2 + 1;
if (n == 0) n = i / 2;//n==0的时候特判,
}
cout << str[n - 1];//题目说字符从下标1开始计数,所以n-1
}
int main()
{
ios;
solve();
return 0;
}