D - Strange Mirroring(AtCoder Beginner Contest 380)
题目链接：
D - Strange Mirroring (atcoder.jp)
题目描述：
数据范围：
样例输入：
aB
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
样例输出：
a B A b A b a B A b a B a B A b
样例解释：
分析：
每一次询问的大小极限是：1e18，是非常大的。读题发现每次转换后拼接之后 长度就 * 2 了。
考虑用 dfs 递归 的往下找下去，什么时候终止dfs呢？那就是当长度 <= s.size()的时候 然后带上去 每次带上去的时候要转换一下大小写，^ 32 把大写的转换为小写的 把小写的转换为大写的。每一次dfs都会砍掉一半，类似于二分，最多60次不到就能达到极限 1e18。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
char dfs(int x) {
// x小于等于 长度时 注意：x的长度是从1开始的 s的下标是从0开始的
if(x <= s.size() ) {
return s[x - 1];
}
int len = s.size();
while(len * 2 < x) {
len = len * 2;
}
// 其中 ^ 32是转化大小写的
return (char)((int)(dfs(x - len)) ^ 32);
}
signed main() {
cin >> s;
int t;
cin >> t;
while(t -- ) {
int x;
cin >> x;
cout << dfs(x) << " ";
}
return 0;
}