C. Mark and His Unfinished Essay

思路

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

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

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

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

把这个 rkmark\texttt{rkmark} 中的每个字母都向前移动 99 个位置,就是另一个 rkmark\texttt{rkmark},如下:

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

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

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

这里再说明一下

代码

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

000101001101011101011001010001010011\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}\\

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

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

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

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

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

那如何判断段的开始和结尾呢?无非就是 00 变成 1111 变成 00。所以我们开两个数组 aabb,输入 sstt 之后遍历一遍这两个字符串。只要 sisi+1s_i \ne s_{i + 1},就把 ii 放入 aa 中(对于 ttbb 相同)。这样 aabb 中就存了两个串的所有段端点。

代码:

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