ABC-380-D - Strange Mirroring（倍增字符串，通过回溯来查询单个） · znzryb

## 思路讲解

哈哈，找规律很难找，找不出来？不妨使用回溯思想，反过来找。

这个操作那其实就是一个倍增操作，我们反过来找我们的这个位置需要倍增几次才能到那？

知道了这个，只需要通过这个（需要倍增几次）%2 进行反转操作就行。

## AC代码

```cpp
#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;
		}
	}
//	return cnt;
}

char dfs(ll x,ll cnt){
	ll needLift=0,standLen=len,res=0;
	needLift=calLift(x,standLen);
	if(needLift==0 /*|| (needLift==1 && x==standLen)*/){
		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;
}
// AC https://atcoder.jp/contests/abc380/submissions/60951665
/*
qWeRtYuIoP
8
1 1 2 3 5 8 13 21

aB161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

*/
```

## 心路历程（WA，TLE，MLE……）

样例给的强，一次提交就过了

[https://atcoder.jp/contests/abc380/submissions/60951665](https://atcoder.jp/contests/abc380/submissions/60951665)

其实调调了半天，尽量函数越少越好（用了一个指针优化掉了一个函数）。