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

Sunny_Boybgfcxc · 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记录