CSP-S 2020 第一轮 第33题：若两个字符串的长度均为 n，且 0<m<n-1，且两个字符串的构成相同

题目

#include <iostream>
#include <queue>
using namespace std;

const int maxl = 20000000;

class Map {
    struct item {
        string key; int value;
    } d[maxl];
    int cnt;
  public:
    int find(string x) {
        for (int i = 0; i < cnt; ++i)
            if (d[i].key == x)
                return d[i].value;
        return -1;
    }
    static int end() { return -1; }
    void insert(string k, int v) {
        d[cnt].key = k; d[cnt++].value = v;
    }
} s[2];

class Queue {
    string q[maxl];
    int head, tail;
  public:
    void pop() { ++head; }
    string front() { return q[head + 1]; }
    bool empty() { return head == tail; }
    void push(string x) { q[++tail] = x;  }
} q[2];

string st0, st1;
int m;

string LtoR(string s, int L, int R) {
    string t = s;
    char tmp = t[L];
    for (int i = L; i < R; ++i)
        t[i] = t[i + 1];
    t[R] = tmp;
    return t;
}

string RtoL(string s, int L, int R) {
    string t = s;
    char tmp = t[R];
    for (int i = R; i > L; --i)
        t[i] = t[i - 1];
    t[L] = tmp;
    return t;
}

bool check(string st , int p, int step) {
    if (s[p].find(st) != s[p].end())
        return false;
    ++step;
    if (s[p ^ 1].find(st) == s[p].end()) {
        s[p].insert(st, step);
        q[p].push(st);
        return false;
    }
    cout << s[p ^ 1].find(st) + step << endl;
    return true;
}

int main() {
    cin >> st0 >> st1;
    int len = st0.length();
    if (len != st1.length()) {
        cout << -1 << endl;
        return 0;
    }
    if (st0 == st1) {
        cout << 0 << endl;
        return 0;
    }
    cin >> m;
    s[0].insert(st0, 0); s[1].insert(st1, 0);
    q[0].push(st0); q[1].push(st1);
    for (int p = 0;
            !(q[0].empty() && q[1].empty());
            p ^= 1) {
        string st = q[p].front(); q[p].pop();
        int step = s[p].find(st);
        if ((p == 0 &&
                (check(LtoR(st, m, len - 1), p, step) ||
                 check(RtoL(st, 0, m), p, step)))
                ||
                (p == 1 &&
                 (check(LtoR(st, 0, m), p, step) ||
                  check(RtoL(st, m, len - 1), p, step))))
            return 0;
    }
    cout << -1 << endl;
    return 0;
}

（4 分）若两个字符串的长度均为 $n$，且 $0<m<n-1$，且两个字符串的构成相同（即任何一个字符在两个字符串中出现的次数均相同），则下列说法正确的是（ ）。提示：考虑输入与输出有多少对字符前后顺序不一样。

选项

• A. 若 $n,m$ 均为奇数，则输出可能小于 0。
• B. 若 $n,m$ 均为偶数，则输出可能小于 $0$。
• C. 若 $n$ 为奇数、$m$ 为偶数，则输出可能小于 $0$。
• D. 若 $n$ 为偶数、$m$ 为奇数，则输出可能小于 $0$。

答案

C

题解

选 C。提示中的“前后顺序不一样”，就是让我们考虑逆序对数量的奇偶性。

先考虑所有字符都不同的情况。交换两个相邻字符，会使逆序对数量的奇偶性改变一次。程序从 st0 出发，有两种操作（下标从 0 开始）：

• LtoR(st, m, n-1)：把下标 m 的字符移到末尾，相当于进行了 \(n-m-1\) 次相邻交换。
• RtoL(st, 0, m)：把下标 m 的字符移到开头，相当于进行了 \(m\) 次相邻交换。

如果这两个次数都是偶数，那么无论操作多少次，逆序对数量的奇偶性都不会改变。条件是 \[ m\equiv 0\pmod 2,\qquad n-m-1\equiv 0\pmod 2, \] 也就是 \(n\) 为奇数、\(m\) 为偶数，对应 C。

例如输入： ``text abcde bacde 2 ``

此时 \(n=5,m=2\)，两种操作都相当于做 2 次相邻交换，始终保持逆序对数量的奇偶性。但：

• abcde 有 0 个逆序对，为偶数；
• bacde 有 1 个逆序对，为奇数。

因此二者不可能互相转换，程序最终输出 -1。从另一端搜索时使用的是逆操作，同样保持奇偶性，也无法使两边相遇。

题目问的是“可能”，所以用字符互不相同的这个例子，就足以证明 C 正确。