CF1705 C, D 题解
C. Mark and His Unfinished Essay
思路
这个数据范围显然不能真的去复制字符串,所以要找到一些别的方法。
可以发现,每次在字符串末尾新加上的那一段,都可以通过一个偏移量在前面找到一模一样的。
比如我们可以观察样例中第一个数据的最后一次插入:
把这个 中的每个字母都向前移动 个位置,就是另一个 ,如下:
所以我们可以维护一个三元组 ,表示 这段区间内的字符,和 这段区间内的字符完全一样。
这样每次在查询位置 的时候,我们就可以一直减去相应的 ,直到 被包含在初始字符串的范围内。
这里再说明一下
代码
// ttzytt
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct Seg {
ll l, r, diff; // [l, r] 这个范围内的每一个点,都和上一段有 diff 的偏移
};
int main() {
int t;
cin >> t;
while (t--) {
int n, c, q;
cin >> n >> c >> q;
string str;
cin >> str;
vector<Seg> a(c + 1);
a[0].l = 0, a[0].r = n - 1;
for (int i = 1; i <= c; i++) {
ll l, r;
cin >> l >> r;
l--, r--;
a[i].l = a[i - 1].r + 1; // 左端点和上一段的右端点一样
a[i].r = a[i].l + (r - l); // 右端点就加上长度 -1
a[i].diff = a[i - 1].r - l + 1;
/*
| 第一段 | 上一段 | 新插入的段 |
|--------| \
/ ⬆ \
/ 正在复制的段 \
l a[i - 1].r
所以偏移量为 a[i - 1].r - l + 1
*/
}
while (q--) {
ll x;
cin >> x;
x--;
for (int i = c; i >= 1; i--) {
if (x < a[i].l) // 如果 x 的位置不属于当前段
continue;
else
x -= a[i].diff; // 那就减去偏移量
}
cout << str[x] << '\n';
}
}
}
D. Mark and Lightbulbs
思路
先来模拟一下第四个样例:
000101
010011
注:标红的位置表示发生了变化。
可以发现,这个过程中我们只能将一个由 组成的段,比如 ,或者 (当然反过来看的话可以说是 组成的段)延长或者是缩短一点,而不能凭空创造出一个新的“ 段”。这是因为,只有从 变成了 或者从 变成了 , 和 才会是不一样的,我们才能改变 。
所以我们可以知道,如果 串和 串的段数量不一样,那么一定是不可能从 转换成 的。
可以发现,每一次操作中,我们能将一个 “ 段” 的开头或者结尾移动一个位置,那么用这个方式就可以计算出从 到 的变换需要多少步了。
也就是,对于 和 中的每一个段,我们计算出段开始和结尾的位置,然后再算出 中和 中的段端点的差,把这些差累加起来就是答案了。
那如何判断段的开始和结尾呢?无非就是 变成 和 变成 。所以我们开两个数组 和 ,输入 和 之后遍历一遍这两个字符串。只要 ,就把 放入 中(对于 和 相同)。这样 和 中就存了两个串的所有段端点。
代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int t;
cin >> t;
while (t--) {
string s, t;
int n;
cin >> n >> s >> t;
vector<int> sdiff, tdiff; // 题解中的 a 和 b
ll ans = 0;
if (s.front() != t.front() || s.back() != t.back()) {
// 因为我们不能改变 s[0] 和 s[n - 1],所以 s 和 t 的第一和最后一位必须一样
goto FAIL;
}
for (int i = 0; i < s.size() - 1; i++) {
if (s[i] != s[i + 1]) sdiff.push_back(i);
// 如果相邻两位变化了,说明是端点
if (t[i] != t[i + 1]) tdiff.push_back(i);
}
if (sdiff.size() != tdiff.size()) {
goto FAIL;
} else {
for (int i = 0; i < sdiff.size(); i++) {
// 计算端点差的和
ans += abs(sdiff[i] - tdiff[i]);
}
}
SUCC:
cout << ans << '\n';
continue;
FAIL:
cout << "-1\n";
}
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 tzyt的博客!
评论
GiscusWaline