查看原题请戳这里
首先，题目中对字符串的操作是这样的：
$$ABCD$$
$$ABCD+DABC$$
$$ABCDDABC$$
数据范围是$N \leq 10^{18}$，模拟显然是行不通的。
首先，我们需要求出$N$在哪个重复区间内（即字符串最少重复到多长可以把$N$包含进去）。若用$t$来记录这个长度，则$t$可以这样求：
我们可以发现，对于第$N$个字符，它其实是由第$N-(t/2+1)$个字符复制得到的，其中若$N = t / 2 + 1$，则$N$是由第$t/2$个字符复制得到的。所以我们只需要不断按此规则递归就可以把$N$减小，直至$N<l$，从而求解。其中$l$为输入字符串的长。
code:
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
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define qwq printf("qwq\n");
using namespace std;
ll read() {
register ll x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
ll n, t, l;
char s[1005];
int main() {
cin >> s + 1 >> n;
t = strlen(s + 1); l = t;
while(t < n) t <<= 1;
while(t > l) {
t >>= 1;
if(n <= t) continue;
if(t + 1 == n) n = t;
else n = n - t - 1;
}
cout << s[n] << endl;
return 0;
}
|
