自动搬运

查看原文

来自洛谷，原作者为

	Sunny_Boybgfcxc 我之所以这么喝咖啡，主要是因为我把别人用来内卷的时间用来成功（画掉）

搬运于2025-08-24 21:17:50，当前版本为作者最后更新于2025-08-18 15:40:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：B4205 [常州市赛 2021] 特殊字符

更好的阅读体验

题意简述

  有一个仅包含小写字母的字符串，现在指定一个特殊字符，连续 $t$ 个特殊字符代表将此后 $t$ 个字母变成其重复 $t$ 次的结果。给定一个长度为 $n$ 的字符串,对于每一个小写字母，问以它为特殊字符时，结果的第 $K$ 为什么字符，如果结果长度小于 $K$ 位则输出*。

解题思路

  很明显单纯模拟是行不通的。我们可以统计每个字符对结果长度的贡献。
  我们遍历这个字符串。只会出现两种情况：

1. 如果当前字符不是特殊字符，则对结果长度产生 $1$ 的贡献。如果结果长度恰为 $K$，则直接输出答案。
2. 如果连续出现了 $t$ 个特殊字符，设此后最多可以取到 $l$ 个字母，那么对结果长度产生 $(t-1) \cdot l$ 的贡献。如果 $K$ 落在这一段中，可以计算出答案。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
string code;
char work(string cd,char s){
	int len=0;
	for(int i=1;i<=n;i++){
		if(cd[i]!=s){
			len++;
			if(len==k)return cd[i];
		}
		else{
			int j=i,cnt=0;
			while(cd[j]==s){
				j++;
				cnt++;
			}
			string t=cd.substr(j,cnt);
			int olen=len+1;
			len+=(cnt-1)*t.size();
			if(k<=len){
				return t[(k-olen)%t.size()];
			}
			i=j-1;
		}
	}
	return '*';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin>>n>>k>>code;
	code=" "+code;
	for(char i='a';i<='z';i++){
		putchar(work(code,i));
	}
	return 0;
}

AC记录