专栏文章

题解：AT_abc242_d [ABC242D] ABC Transform

DDragonForge
AT_abc242_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq8cwcp
此快照首次捕获于
2025/12/04 00:37
3 个月前
此快照最后确认于
2025/12/04 00:37
3 个月前
查看原文

AT_abc242_d [ABC242D] ABC Transform

注：本题解参考 @maziming 的代码与思路，这里再做详细解释。
这是一道递推题，我的老师说还可以用分治做。由于 A B C 之间不好互相转换，我采用三者间 ASCLL 码相连的性质，用数字转换。注意，最后输出不能只输出一个数字！
根据变换规则，以 A 为例。变化一次变成 BC，再变变成 CAAB，接着是 ABBCBCCA ，BCCACAABCAABABBC……其实这样下去一点规律也没有，但是聪明的同学已经发现，变化后，第 2i2i 和 2i+12i + 1 项是由原数组的第 ii 项变成的，而且分别是第 ii 项数值加一模 3 和加二模 3。此时这道题递推起来就轻松了。
放一下代码：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...