YC323C [ 20240724 CQYC NOIP 模拟赛 T3 ] 手环(ring）

题意

给定两个长为 \(n\) 的 \(0/1\) 串 \(A, B\)。

每次操作：

• 对 \(A\) 向左或向右循环移位。
• 选择 \(0 \le p < n \land B_i = 1\)，则将 \(A_i\) 取反。

求将 \(A\) 变为 \(B\) 的最小操作次数。无解输出 -1。

\(n \le 2000\)

Sol

显然无解当且仅当 \(A\) 和 \(B\) 不相同且 \(B\) 不存在 \(1\)。

考虑枚举一个终止状态 \(i\)，表示 \(A\) 向右循环移动 \(i\) 位，且在过程中使用操作一将两串变成相等。

考虑移动 \(i\) 位后哪些位置不满足条件，不难发现事实上最优的决策一定满足先向左移动，然后向右移动到 \(i\) 右边，最后再移动回来。

原问题变为一个分配问题，每个移动 \(i\) 位后不满足条件的位置，需要向左或是向右找到一个 \(B_i\) 为 \(1\) 的位置消掉。

因此直接预处理出每个位置向左最近的 \(B_i\) 为 \(1\) 的位置，向右最近的位置。

这样直接对一维排序，倒着扫回来，动态维护另一维的最大值即可。

这里直接桶排，复杂度 \(O(n ^ 2)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <vector>
using namespace std;
#ifdef ONLINE_JUDGE

/* #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) */
/* char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf; */

#endif
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
bool _stmer;

const int N = 2e3 + 5;

char strbuf[N];

string s, h;

array <int, N> tpl, tpr;
array <vector <int>, N> isl;

int query(int n) {
    int ans = 2 * n;
    for (int i = 0; i < n; i++) {
        int res = 0, tp = i;
        for (int j = 0; j < n; j++)
            if (s[j] != h[(j + i) % n])
                isl[tpr[j]].push_back(j), res++;
        for (int j = n; j >= i + 1; j--) {
            for (auto k : isl[j])
                tp = max(tp, tpl[(k + i) % n]);
            ans = min(ans, (tp - i + j - 1) * 2 - i + res);
            /* if ((tp - i + j - 1) * 2 - i + res < 10) { */
                /* cerr << i << " " << tp << " " << j << "#" << endl; */
                /* for (auto k : isl[j]) */
                    /* cerr << k << "@@" << endl; */
                /* exit(0); */
            /* } */
        }
        for (int j = 0; j < n; j++) isl[j].clear();
    }
    return ans;
}

void solve() {
    scanf("%s", strbuf);
    s = strbuf;
    scanf("%s", strbuf);
    h = strbuf;

    int n = s.size(), tp = 0;
    for (auto k : h) tp += k - '0';
    if (s == h) return (void)puts("0");
    if (tp == 0) return (void)puts("-1");

    for (int i = 0; i < n; i++) {
        if (h[i] == '1') { tpl[i] = tpr[i] = 0; continue; }
        tpl[i] = tpr[i] = 1;
        while (h[(i - tpl[i] + n) % n] == '0') tpl[i]++;
        while (h[(i + tpr[i]) % n] == '0') tpr[i]++;
    }

    int ans1 = query(n), ans2 = 0;
    reverse(s.begin(), s.end()), reverse(h.begin(), h.end()), swap(tpl, tpr);
    reverse(tpl.begin(), tpl.begin() + n), reverse(tpr.begin(), tpr.begin() + n);
    /* cerr << endl; */
    ans2 = query(n);
    write(min(ans1, ans2)), puts("");
}

bool _edmer;
int main() {
    cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
    int T = read();
    while (T--) solve();
    return 0;
}