ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[ABC242]D - ABC Transform(dfs + 规律)

2022年3月12日 1106点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ dfs 算法 规律
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号