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

lly31415926 · 2025-10-26 22:27:50 · 题解

题目要求处理 26 种情况（每个字母作为特殊字符）对每种情况：

• 续 x 个特殊字符表示要将后续 x 个字符复制 x 次。
• 需要找到破译后字符串的第 k 个字符。

一 暴力出奇迹

遍历 26 种可能性：对每个字母 a \sim z 分别作为特殊字符测试。

实时构建破译字符串：

• 遇到普通字符直接追加。
• 遇到特殊字符时执行复制操作。

提前终止：当字符串长度 \ge K 时立即停止处理。

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

int main() {
    int n， K; 
    string s;
    cin >> n >> K >> s;
    string ans(26, '*');
    for (char c = 'a'; c <= 'z'; c++) {
        string d;
        int i = 0;
        while (i < n && d.size()  < K) {
            if (s[i] != c) { 
                d += s[i++]; 
                continue; 
            }
            int x = 0;
            while (i < n && s[i] == c) x++, i++;
            int t = min(x， n-i); 
            string p = s.substr(i,t);
            i += t;
            while (x-- && d.size()  < K) d += p;
        }
        if (d.size()  >= K) ans[c-'a'] = d[K-1];
    }
    cout << ans;
}

战绩：

十年 OI 一场空，暴力解题见祖宗。

回归正题：

很显然，当 k\ge10^9 时，必定超空间和时间。

所以，

我们只可以不实际构建字符串，而是通过数学计算直接定位第 k 个字符，这是避免 MLE 或者 TLE 的关键！！！

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

int main() {
    long long n, k;
    string s;
    cin >> n >> k >> s;
    string r(26, '*');
    for (char c = 'a'; c <= 'z'; ++c) {
        long long p = 0;
        long long i = 0;
        char a = '*';
        while (i < n && a == '*') {
            if (s[i] != c) {
                if (++p == k) a = s[i];
                ++i;
                continue;
            }
            long long x = 0;
            while (i < n && s[i] == c) ++x, ++i;
            long long t = min(x, n-i);
            if (p + x*t >= k) {
                a = s[i + (k-p-1)%t];
                break;
            }
            p += x*t;
            i += t;
        }
        if (a != '*') r[c-'a'] = a;
    }
    cout << r;
    return 0;
}