题解 [ABC242D] ABC Transform
cjh20090318
·
·
题解
很巧妙的一道题。
题意
给定一个字符串 S，只包含字符 A，B，C。
每过一个时刻，字符会发生变化：A\toBC，B\toCA，C\toAB。
设 0 时刻为 S_0=S。
进行 Q 次询问，每次询问时刻 t 时，字符串 S_t 中第 k 个字符。
分析
为了方便处理，我这里将所有下标减一。
经过观察可以得出，t \ (t>0) 时刻的第 k 个字符，一定是由 t-1 时刻的第 \left\lfloor\dfrac k 2\right\rfloor 个字符变化而来的。
如果 k \bmod 2 = 0 则是变化后的第一个字符，否则是第二个。
此时就可以倒推出 0 时刻对应的字符，再返回得到答案。
但是发现这样一个递归求解的复杂度是 O(t) 的，无法接受。
单次询问时间复杂度 $O(\min(t,\log_2 k))$。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#define MAXN 100005
using namespace std;
typedef long long LL;
char s[MAXN];
const char T[3][3]={"BC","CA","AB"};//打表每种字符对应的情况，避免大量的分类讨论。
char dfs(const LL&t,const LL&k){return k?(t?T[dfs(t-1,k>>1)-'A'][k&1]:s[k]):(s[0]-'A'+t%3)%3+'A';}//k=0 不再变化时，直接由循环节得出，否则如果 t=0 返回第 k 位字符，否则获取上个时刻的字符。
int main(){
int q;
scanf("%s %d",s,&q);
for(LL t,k;q--;) scanf("%lld%lld",&t,&k),putchar(dfs(t,k-1)),putchar('\n');//因为下标减一，所以查询的时候也要减一。
return 0;
}
```