CF1705 C, D 题解

C. Mark and His Unfinished Essay

思路

这个数据范围显然不能真的去复制字符串，所以要找到一些别的方法。

可以发现，每次在字符串末尾新加上的那一段，都可以通过一个偏移量在前面找到一模一样的。

比如我们可以观察样例中第一个数据的最后一次插入：

$$\texttt{mark\ mark\ mar\ } \color{red}{\texttt{rkmark}}$$

把这个 $\texttt{rkmark}$ 中的每个字母都向前移动 $9$ 个位置，就是另一个 $\texttt{rkmark}$，如下：

$$\texttt{ma\ } \textcolor{red}{\texttt{rkmark\ }}\texttt{mar\ } \textcolor{red}{\texttt{rkmark}}$$

所以我们可以维护一个三元组 $(l, r, d)$，表示 $[l, r]$ 这段区间内的字符，和 $[l - d, r - d]$ 这段区间内的字符完全一样。

这样每次在查询位置 $x$ 的时候，我们就可以一直减去相应的 $d$，直到 $x$ 被包含在初始字符串的范围内。

这里再说明一下

代码

// 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

$$\texttt{000101} \\ \downarrow\\ \texttt{00}\textcolor{red}{\texttt{1}}\texttt{101}\\ \downarrow\\ \texttt{0}\textcolor{red}{\texttt{1}}\texttt{1101}\\ \downarrow\\ \texttt{011}\textcolor{red}{\texttt{0}}\texttt{01}\\ \downarrow\\ \texttt{01}\textcolor{red}{\texttt{0}}\texttt{001}\\ \downarrow\\ \texttt{0100}\textcolor{red}{\texttt{1}}\texttt{1}\\$$

注：标红的位置表示发生了变化。

可以发现，这个过程中我们只能将一个由 $1$ 组成的段，比如 $\texttt{1}$，或者 $\texttt{111}$（当然反过来看的话可以说是 $0$ 组成的段）延长或者是缩短一点，而不能凭空创造出一个新的“ $1$ 段”。这是因为，只有从 $1$ 变成了 $0$ 或者从 $0$ 变成了 $1$，$s_{i - 1}$ 和 $s_{i + 1}$ 才会是不一样的，我们才能改变 $s_i$。

所以我们可以知道，如果 $s$ 串和 $t$ 串的段数量不一样，那么一定是不可能从 $s$ 转换成 $t$ 的。

可以发现，每一次操作中，我们能将一个 “ $1$ 段” 的开头或者结尾移动一个位置，那么用这个方式就可以计算出从 $s$ 到 $t$ 的变换需要多少步了。

也就是，对于 $s$ 和 $t$ 中的每一个段，我们计算出段开始和结尾的位置，然后再算出 $s$ 中和 $t$ 中的段端点的差，把这些差累加起来就是答案了。

那如何判断段的开始和结尾呢？无非就是 $0$ 变成 $1$ 和 $1$ 变成 $0$。所以我们开两个数组 $a$ 和 $b$，输入 $s$ 和 $t$ 之后遍历一遍这两个字符串。只要 $s_i \ne s_{i + 1}$，就把 $i$ 放入 $a$ 中（对于 $t$ 和 $b$ 相同）。这样 $a$ 和 $b$ 中就存了两个串的所有段端点。

代码：

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