题目传送门:D - ABC Transform (atcoder.jp)

题目大意
给定一个字符串 S 。给定询问次数 Q ,每次询问为求出变换 t 次之后的第 k 个字符。
每次变换规则为:A -> BC , B -> CA, C -> AB。
思路
不难发现,每个序列的第一个字符是有周期性的。
我们假设字符串下标从 0 开始(便于找规律)。
第 t 次变换后的第 k 个字符由第 t - 1次变换的第 k / 2个字符+ 1 或 + 2 得到(对 3 取模),如果 k 为偶数,那么就是S[t - 1][k / 2] + 1,如果是偶数那么就是S[t - 1][k / 2] + 2。
注意特判 t == 0 和 k == 0 ,否则会超时。
注意在进入dfs时需要将k-1,因为题目中字符串下标从1开始。
时间复杂度O(Q * logK)。
代码
/*Copyright (C) Eriktse 2022*/ #include <iostream> #include <cstdio> #include <stack> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <map> #include <algorithm> #include <bitset> #include <utility> #define fi first #define se second #define gc getchar #define pr printf #define sc scanf #define pb push_back #define int long long //用%lld输出long long类型数据 using namespace std; inline int readInt() { int s = 0,w = 1;char c = gc(); while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();} while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();} return s * w; } /*--------全局变量--------*/ const int maxn = 1e5 + 10; char s[maxn]; /*--------自定义函数-------*/ inline char add(char ch,int x){return (ch - 'A' + x) % 3 + 'A';} inline char dfs(int t,int k)//表示第 t 个序列的第 k 个字符 { if(t == 0)return s[k]; if(k == 0)return add(s[0], t); return add(dfs(t - 1, k / 2), k % 2 + 1); } signed main() { cin >> s; int Q = readInt(); while(Q --) { int t = readInt(), k = readInt(); cout << dfs(t, k - 1) << '\n'; } return 0; }
Comments NOTHING