题解：AT_abc242_d [ABC242D] ABC Transform

· · 题解

AT_abc242_d [ABC242D] ABC Transform

注：本题解参考 @maziming 的代码与思路，这里再做详细解释。

这是一道递推题，我的老师说还可以用分治做。由于 A B C 之间不好互相转换，我采用三者间 ASCLL 码相连的性质，用数字转换。注意，最后输出不能只输出一个数字！

根据变换规则，以 A 为例。变化一次变成 BC，再变变成 CAAB，接着是 ABBCBCCA ，BCCACAABCAABABBC……其实这样下去一点规律也没有，但是聪明的同学已经发现，变化后，第 2i 和 2i + 1 项是由原数组的第 i 项变成的，而且分别是第 i 项数值加一模 3 和加二模 3。此时这道题递推起来就轻松了。

放一下代码：

#include <bits/stdc++.h>

using namespace std;

using LL=long long;
LL q,t,k,l;
string s;

int main(){
    cin>>s;
    for(cin>>q;q--;){
        cin>>t>>k;
        k--;
        LL whr=0;
        if(t<60){
            whr=k>>t;
            k-=whr<<t;
        }
        l=t%3;
        for(int j=59;j>=0;j--){
            LL m=1ll<<j;
            if(k&m){
                k^=m,l+=1;
            }
        }
        char ans=(l+s[whr]-'A')%3+'A';
        cout<<ans<<endl;
    }
    return 0;
}