AT ARC193D Magnets

· · 题解

cnblogs。

考虑刻画这个向中靠齐的操作。

发现操作完后其实元素的相对顺序基本不会改变，唯一的变化就是 i - 1, i, i + 1 都到了 i 位置上。
那么就相当于是 a_i\gets \max\{a_{i - 1}, a_i, a_{i + 1}\} 并删去 a_{i - 1}, a_{i + 1} 重新编号。
为了放止一些越界问题，可以考虑在操作前在序列头尾各放一个不会影响的 0。

那么就可以把操作刻画成：在序列头尾各放上一个 0，选取 3 个连续的数合并成这 3 个数的 \max。

但是直接考虑合并成 b 还是有点困难，于是尝试去二分进行了 k 次操作 check。

此时就不用考虑每次操作时放 0 了，而是考虑提前在 a 的头尾放上 k 个 0，这样的好处就是 a 被固定好了。

因为每次合并是 3 个元素，所以可以知道 b 中的每个元素一定是对应的 a 中的奇数个元素。
于是再对 check 进行转换：把 a 划分成 n 个段，满足每个段的长度都为奇数，且段中元素 \max 等于 b 中对应元素。

首先考虑调整，b_i = 0 说明其对应的段肯定都为 0，那么若其段长不为 1，把多的部分甩给周围的段（只要甩出去的是偶数即可）一定也合法，所以 0 在 a 中对应的也一定是单个 0。

于是考虑以下 check：

此时就应该有了 \mathcal{O}(n\log n) 的做法，不过还可以再优化。

考虑答案的下界，b 的前缀 0 必须匹配上 a 的前缀 0，b 的后缀 0 必须匹配上 a 的后缀 0，于是下界 x 为 b 的前缀 0 个数减去 a 的前缀 0 个数和后缀同样的值（还有 0）取 \max。

那么会发现，对于 x + 2，check 时其实也就是让 b 第一个 1 的区间左端点扩展了 2，b 最后一个 1 的区间右端点扩展了 2，其余都一样。
也就是说，x 和 x + 2k(k\ge 1) 的 check 后的结果是相同的。

同样的，x + 1 和 x + 2k + 1(k\ge 1) 的结果也是一样的。

所以只需要代入 x, x + 1 去 check，时间复杂度 \mathcal{O}(n)。

#include <bits/stdc++.h>

int ans;
inline void check(int k, std::vector<int> a, std::vector<int> b) {
    a.insert(a.begin(), k, 0), a.insert(a.end(), k, 0);

    const int n = (int)a.size(), m = (int)b.size();
    std::vector<std::pair<int, int> > pb;

    for (int l = 0, r = 0; l < m; l = r) {
        if (b[l] == 1) {
            pb.emplace_back(1, 1);
            r++; continue;
        }
        while (r < m && b[r] == 0) r++;
        pb.emplace_back(0, r - l);
    }

    std::vector<int> pre(n);
    pre[0] = a[0];
    for (int i = 1; i < n; i++) {
        pre[i] = pre[i - 1] + a[i];
    }

    int i = -1;
    for (auto [op, len] : pb) {
        if (op == 0) {
            while (true) {
                if (i >= n - len) return ;
                if (pre[i + len] - (i == -1 ? 0 : pre[i]) == 0) break;
                i += 2;
            }
            i += len;
        }

        if (op == 1) {
            int j = i + 1;
            while (j < n && a[j] == 0) j++;

            i = j + (std::abs(i) % 2 == j % 2);
            if (i > n) return ;
        }
    }

    ans = k;
}

inline void solve() {
    int n; scanf("%d", &n);
    std::vector<int> a(n), b(n);
    for (int &x : a) scanf("%1d", &x);
    for (int &x : b) scanf("%1d", &x);

    int pa = 0, pb = 0, sa = n - 1, sb = n - 1;
    while (! a[pa]) pa++;
    while (! a[sa]) sa--;
    while (! b[pb]) pb++;
    while (! b[sb]) sb--;

    ans = -1;
    const int low = std::max({pb - pa, sa - sb, 0});
    check(low + 1, a, b);
    check(low, a, b);

    printf("%d\n", ans);
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}