专栏文章

AT ARC193D Magnets

rrizynvu
AT_arc193_d题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio93mcw
此快照首次捕获于
2025/12/02 15:22
3 个月前
此快照最后确认于
2025/12/02 15:22
3 个月前
查看原文
cnblogs。
考虑刻画这个向中靠齐的操作。
发现操作完后其实元素的相对顺序基本不会改变，唯一的变化就是 i−1,i,i+1i - 1, i, i + 1 都到了 ii 位置上。
那么就相当于是 ai←max⁡{ai−1,ai,ai+1}a_i\gets \max\{a_{i - 1}, a_i, a_{i + 1}\} 并删去 ai−1,ai+1a_{i - 1}, a_{i + 1} 重新编号。
为了放止一些越界问题，可以考虑在操作前在序列头尾各放一个不会影响的 00。
那么就可以把操作刻画成：在序列头尾各放上一个 00，选取 33 个连续的数合并成这 33 个数的 max⁡\max。
但是直接考虑合并成 bb 还是有点困难，于是尝试去二分进行了 kk 次操作 check。
此时就不用考虑每次操作时放 00 了，而是考虑提前在 aa 的头尾放上 kk 个 00，这样的好处就是 aa 被固定好了。
因为每次合并是 33 个元素，所以可以知道 bb 中的每个元素一定是对应的 aa 中的奇数个元素。
于是再对 check 进行转换：把 aa 划分成 nn 个段，满足每个段的长度都为奇数，且段中元素 max⁡\max 等于 bb 中对应元素。
首先考虑调整，bi=0b_i = 0 说明其对应的段肯定都为 00，那么若其段长不为 11，把多的部分甩给周围的段（只要甩出去的是偶数即可）一定也合法，所以 00 在 aa 中对应的也一定是单个 00。
于是考虑以下 check：
  • 按顺序由 1→n1\to n 遍历 bib_i。
  • 对于 bi=1b_i = 1，一直扩张直到区间中含有 11。
  • 对于 bi=0b_i = 0，缩成一段考虑，这是因为 00 对 11 是完全不可的态度。
    所以对于长度为 mm 的段，一直扩张之前的段直到接下来 aa 中存在长度为 mm 的全 00 段，选掉这个全 00 段。
此时就应该有了 O(nlog⁡n)\mathcal{O}(n\log n) 的做法，不过还可以再优化。
考虑答案的下界，bb 的前缀 00 必须匹配上 aa 的前缀 00，bb 的后缀 00 必须匹配上 aa 的后缀 00，于是下界 xx 为 bb 的前缀 00 个数减去 aa 的前缀 00 个数和后缀同样的值（还有 00）取 max⁡\max。
那么会发现，对于 x+2x + 2，check 时其实也就是让 bb 第一个 11 的区间左端点扩展了 22，bb 最后一个 11 的区间右端点扩展了 22，其余都一样。
也就是说，xx 和 x+2k(k≥1)x + 2k(k\ge 1) 的 check 后的结果是相同的。
同样的，x+1x + 1 和 x+2k+1(k≥1)x + 2k + 1(k\ge 1) 的结果也是一样的。
所以只需要代入 x,x+1x, x + 1 去 check，时间复杂度 O(n)\mathcal{O}(n)。
CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...