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

这题直接每个特殊字符模拟出破译结果明显会超时。

发现题目只要求出第

k

位，其他的字符都是没用的。

又发现每次复制出来的字符数是可以直接

O(1)

求出来的，而不参与复制的字符则就是只有一个字符不变。

所以对于每个特殊字符：遍历原来字符串，算出当前破译出的字符数量，如果超过了

k

再具体通过取模求出具体字符。这样可以极大优化时间复杂度。

再具体点：对于每个特殊字符，遍历原字符串，对一每个遍历到的字符，执行一下操作。

如果是特殊字符，计数器 $cnt$ 加一， $cnt$ 用来统计一段连续特殊字符的长度。
如果不是特殊字符，且 $cnt$ 为 $0$ ，即不需要复制。则计数器 $sum$ 加一。 $sum$ 表示当前这个已经遍历过的这个子串在破译后的长度。如果 $sum$ 等于 $k$ 那么直接输出这个字符。
如果不是特殊字符，且 $cnt$ 不为 $0$ ，即要执行复制操作了。 $sum$ 要加上 $\min(n-i,cnt)\times cnt$ 。
在上一条操作后如果 $sum$ 大于等于 $k$ 了。提取出被复制的那段子串，记为 $s$ 。先把 $sum$ 还原成上一条操作加之前的值，接着输出 $s_{(k-(sum-\min(n-i,cnt)\times cnt))\mod \min(n-i,cnt)-1}$ 。即 $k$ 超出的部分在复制后的串中对应位置的字符。不过这里要特判取模后为 $0$ 的情况，以免出现 $s_{-1}$ 。如果遍历完一直达到 $k$ 就输出 *。

开 long long 哦。

code

CPP

#include<bits/stdc++.h>
using namespace std;
string a;
long long n,k;
void f(char c){
	long long cnt=0;
	long long sum=0;
	for(long long i=0;i<n;i++){
		if(a[i]==c){
			cnt++;
		}
		else{
			if(cnt!=0){
				sum+=min(n-i,cnt)*cnt;
				if(sum>=k){
					string s=a.substr(i,cnt);
					if((k-(sum-min(n-i,cnt)*cnt))%cnt==0){
						cout<<s[cnt-1];
					}
					else{
						cout<<s[(k-(sum-min(n-i,cnt)*cnt))%min(n-i,cnt)-1];
					}
					return;
				}
				i+=cnt-1;
				cnt=0;
			}
			else{
				sum++;
				if(sum==k){
					cout<<a[i];
					return;
				}
			}
		}
	}
	cout<<'*';
}
int main(){
	cin>>n>>k;
	cin>>a;
	for(char i='a';i<='z';i++){
		f(i);
	}
}

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

文章操作

code

相关推荐

评论

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