专栏文章
题解：B4205 [常州市赛 2021] 特殊字符
B4205题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @minhmfcy
- 此快照首次捕获于
- 2025/12/02 02:33 3 个月前
- 此快照最后确认于
- 2025/12/02 02:33 3 个月前
题目要求处理种情况(每个字母作为特殊字符)对每种情况：
- 续个特殊字符表示要将后续个字符复制次
- 需要找到破译后字符串的第个字符
一 暴力出奇迹
遍历26种可能性:对每个字母分别作为特殊字符测试
实时构建破译字符串:
- 遇到普通字符直接追加
- 遇到特殊字符时执行复制操作
提前终止:当字符串长度 时立即停止处理
CPP#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;
}
不会有入以为这就结束了吧，那你就被坑惨咯
战绩:
回归正题:
很显然,当时
时间复杂度说:你当我很闲是吧
空间复杂度说:你想撑死我是吧
所以,我们只可以
不实际构建字符串,而是通过数学计算直接定位第个字符,这是避免的关键!!!
CPP#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
string s;
cin >> n >> k >> s;
string r(26, '*');
for (char c = 'a'; c <= 'z'; ++c) {
long long p = 0;
int i = 0;
char a = '*';
while (i < n && a == '*') {
if (s[i] != c) {
if (++p == k) a = s[i];
++i;
continue;
}
int x = 0;
while (i < n && s[i] == c) ++x, ++i;
int 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;
}
喜提分:
应该没有人会揍我吧
为什么会两个点呢?
相关推荐
评论
共 0 条评论，欢迎与作者交流。
正在加载评论...