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

joshua0729 · 2025-05-25 09:25:42 · 题解

题解：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;
}

时空间复杂度分析

时间复杂度：O(26\times n)，每个字符模拟一遍。 空间复杂度：O(n)，仅存储字符串。

AC 记录