思路讲解
哈哈，找规律很难找，找不出来？不妨使用回溯思想，反过来找。
这个操作那其实就是一个倍增操作，我们反过来找我们的这个位置需要倍增几次才能到那？
知道了这个，只需要通过这个（需要倍增几次）%2 进行反转操作就行。
AC代码
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
#include <cctype>
#include <array>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,len;
string s;
inline char invert(char a) {
if(a<='z' && a>='a') {
a-=32;
return a;
}else {
a+=32;
return a;
}
}
ll calLift(ll x, ll &standLen){
ll cnt=0;
while(true){
if(standLen>x){
standLen/=2;
return cnt;
}else if(standLen==x){
return cnt;
}else{
cnt+=1;
standLen*=2;
}
}
}
char dfs(ll x,ll cnt){
ll needLift=0,standLen=len,res=0;
needLift=calLift(x,standLen);
if(needLift==0 ){
if(cnt%2==0)
return s[x-1];
else
return invert(s[x-1]);
}
res= x==standLen ? standLen/2:x-standLen;
return dfs(res,cnt+1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll q;
s.clear();
cin>>s;
len=s.size();
cin>>q;
for(int i=1;i<=q;++i){
ll k;
cin>>k;
char ans=dfs(k,0);
cout<<ans<<" ";
}
cout<<endl;
return 0;
}
|
心路历程（WA，TLE，MLE……）
样例给的强，一次提交就过了
https://atcoder.jp/contests/abc380/submissions/60951665
其实调调了半天，尽量函数越少越好（用了一个指针优化掉了一个函数）。