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

LotleTos · 2025-09-23 22:20:03 · 题解

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

发现题目只要求出第 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

#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);
    }
}