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

思路

因为 $n\le10^6$ 且 $K\le10^9 $，直接构造整个字符串会超时甚至内存爆炸。因此考虑模拟加上跳过模拟扩展的片段。

代码逻辑

对于每个特殊字符，从左往右遍历：

若遇到一段连续的 $c$ 长度为 $t$，取出后续的 min(t,n-i) 个字符 $p$。
经过处理后，这段会变成 $p$ 重复 $t$ 遍。
然后判断：
- 若当前 $K$ 还在这段之前，正常推进；
- 若 $K$ 落在这段里，用取模找出具体落在 $p$ 的哪一位。
若不是特殊字符，就正常推进 $K$。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;


int n,k;
string s;
int main(){
	cin>>n>>k;
	cin>>s;
	for(char c='a';c<='z';c++){
		ll d=k;
		int t=0;
		int i;
		for(i=0;i<=n;i++){			  
			if(s[i]==c) t++;//符合条件，t++
			else{
				if(t){
					ll z=min(t,n-i);//取t和n-i的最小值
					if(d>z*t){//如果d>z*t，d减去z*t，i加上z-1，t置0
						d-=z*t;
						i+=z-1;
						t=0;
					}
					else{
						d%=z;
						if(!d) d=z;
						cout<<s[i+d-1];
						d=0;
						t=0;
						break;
					}
				}else if(i!=n){//如果t=0，i!=n，d--，如果d=0，输出s[i]
					d--;
					if(d==0){
						cout<<s[i];
						break;
					}			   
				}

			}
		}
		if(d) cout<<"*";//如果d>0，输出*
	}
	return 0;
}