The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

C. Mark and His Unfinished Essay

Approach

Given these constraints, we obviously cannot actually copy the string, so we need to find another method.

We can see that every segment newly appended to the end of the string has an identical counterpart earlier in the string, located by an offset.

For example, consider the final insertion in the first sample:

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

If every letter in this $\texttt{rkmark}$ is moved 9 positions backward, we find another $\texttt{rkmark}$ , as follows:

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

Therefore, we can maintain a triple $(l, r, d)$ indicating that the characters in the interval $[l, r]$ are completely identical to those in the interval $[l - d, r - d]$ .

Then, whenever querying position $x$ , we can continually subtract the corresponding $d$ until $x$ lies within the range of the initial string.

Here is some further explanation.

Code

// ttzytt
#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct Seg {
    ll l, r, diff;  // Every point in the range [l, r] has an offset of diff from the preceding segment.
};

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;        // The left endpoint follows the right endpoint of the preceding segment.
            a[i].r = a[i].l + (r - l);      // Add length - 1 to obtain the right endpoint.
            a[i].diff = a[i - 1].r - l + 1; 
            /* 
                | First segment | Previous segment | Newly inserted segment |
                                |----------------|  \
                               /        ↑          \
                              / Segment being copied    \
                             l                    a[i - 1].r

            Therefore, the offset is 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)     // If the position x does not belong to the current segment.
                    continue;
                else
                    x -= a[i].diff; // Subtract the offset.
            }
            cout << str[x] << '\n';
        }
    }
}

D. Mark and Lightbulbs

Approach

First, let us simulate the fourth sample:

1 2	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}\\$

Note: The positions marked in red indicate changes.

We can see that during this process, we can only lengthen or shorten a segment consisting of $1$ s, such as $\texttt{1}$ or $\texttt{111}$ (of course, viewed the other way around, it can be described as a segment consisting of $0$ s), rather than creating a new “ $1$ segment” out of thin air. This is because only when a $1$ changes to a $0$ , or a $0$ changes to a $1$ , will $s_{i - 1}$ and $s_{i + 1}$ differ, allowing us to change $s_i$ .

Therefore, if strings $s$ and $t$ have different numbers of segments, transforming $s$ into $t$ must be impossible.

We can see that in each operation, we can move the beginning or end of a “ $1$ segment” by one position. We can therefore use this fact to calculate the number of steps required to transform $s$ into $t$ .

That is, for every segment in $s$ and $t$ , we calculate the positions at which the segment begins and ends, then calculate the differences between corresponding segment endpoints in $s$ and $t$ . The sum of these differences is the answer.

How do we determine the beginning and end of a segment? They are simply where $0$ changes to $1$ and where $1$ changes to $0$ . Therefore, we create two arrays, $a$ and $b$ . After reading $s$ and $t$ , we traverse the two strings. Whenever $s_i \ne s_{i + 1}$ , we put $i$ into $a$ (and do the same for $t$ and $b$ ). In this way, $a$ and $b$ store all segment endpoints in the two strings.

Code:

#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 and b in the solution.
        ll ans = 0;
        if (s.front() != t.front() || s.back() != t.back()) {
            // Because we cannot change s[0] or s[n - 1], the first and last characters of s and t must be the same.
            goto FAIL;
        }

        for (int i = 0; i < s.size() - 1; i++) {
            if (s[i] != s[i + 1]) sdiff.push_back(i);
            // If two adjacent characters differ, this position is an endpoint.
            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++) {
                // Calculate the sum of endpoint differences.
                ans += abs(sdiff[i] - tdiff[i]);
            }
        }

    SUCC:
        cout << ans << '\n';
        continue;
    FAIL:
        cout << "-1\n";
    }
}