自动搬运

查看原文

来自洛谷，原作者为

	SerenityWay 我曾经毁了我的一切 只想永远地离开

搬运于2025-08-24 23:10:52，当前版本为作者最后更新于2025-03-08 12:19:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目要求处理一个压缩后的字符串，并将其无限重复后找到第 $c$ 个字符。

思路

压缩字符串的格式是字母+数字。例如 $\texttt{a4b1c2d4}$ 表示 $\texttt{aaaabccdddd}$。

将解压缩后的字符串无限重复，形成一个循环字符串。找到第 $c$ 个字符，可以通过模运算实现。由于 $c$ 和字符串长度较大（$10^{12}$），需要避免实际生成无限字符串，而是通过计算直接找到第 $c$ 个字符。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//找到第c个字符
char get(string s,ll c){
	ll l=0;//解压缩后的总长度
	int i=0;
	
	while(i<s.length()){
		char c=s[i++];//当前字符
		ll n=0;
		
		while(i<s.length()&&isdigit(s[i])){
			n=n*10+(s[i]-'0');//计算数字
			i++;
		}
		
		l+=n;//累加长度
	}
	
	//计算第c个字符的位置
	ll pos=c%l;
	
	//重新遍历字符串，找到第pos个字符
	i=0;
	ll l2=0;
	
	while(i<s.length()){
		char c=s[i++];//当前字符
		ll n=0;
		
		while(i<s.length()&&isdigit(s[i])){
			n=n*10+(s[i]-'0');//计算数字
			i++;
		}
		
		if(l2+n>pos)
			return c;//找到字符
		
		l2+=n;//累加长度
	}
	
	return '\0';//默认返回空字符
}

int main(){
	string str;
	ll c;
	cin>>str>>c;
	cout<<get(str,c)<<"\n";
	return 0;
}

$\operatorname{get}$ 函数第一次遍历字符串，计算解压缩后的总长度 $l$。通过模运算找到第 $c$ 个字符的位置 $pos$。第二次遍历字符串，找到第 $pos$ 个字符。

时间复杂度 $O(n)$， 空间复杂度为 $O(1)$。