题解：P11146 「SFMOI Round I」Strange Train Game

喵仔牛奶 · 2024-10-03 12:04:15 · 题解

乱搞然后过了.jpg，完全不会证复杂度。

Solution

将 a_i=b_i 的位置全部删除，操作就变成了区间异或。

Sub2 的做法比较简单，从左往右扫，如果当前位是 0 就翻转。

接下来考虑有多个区间 [l,r_1],[l,r_2],\cdots,[l,r_k] 左端点相同怎么处理。如果当前位是 1，就跳过。如果是 0，先随便选一个区间翻转，然后把 [r_1+1,r_2],[r_2+1,r_3],\cdots,[r_{n-1}+1,r_n] 当作新的区间加入。

正确性就是如果当前选了 [l,r_x]，最优解选 [l,r_y]，后续选 [r_x+1,r_y] 就可以变成最优解。复杂度不会证。

Code

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 1e6 + 5;
    LL n, m, l, r, a[N], b[N], d[N], vs[N], R[N]; char x; vector<int> t, g[N];
    int main() {
        cin >> n >> m;
        REP(i, 1, n) cin >> x, a[i] = x - '0';
        REP(i, 1, n) {
            cin >> x, b[i] = x - '0';
            if (a[i] != b[i]) vs[i] = 1, t.pb(i);
        }
        REP(i, 1, m) {
            cin >> l >> r;
            auto x = lower_bound(ALL(t), l), y = upper_bound(ALL(t), r); 
            if (x < y) g[*x].pb(*prev(y));
        }
        REP(i, 1, n) {
            if (!g[i].size()) continue;
            sort(ALL(g[i])), R[i] = g[i][0];
            REP(j, 1, SZ(g[i]) - 1) {
                int x = g[i][j - 1], y = g[i][j];
                if (x < y) {
                    auto z = upper_bound(ALL(t), x);
                    if (z != t.end()) g[*z].pb(y);
                }
            }
        }
        REP(i, 1, n) {
            d[i] ^= d[i - 1];
            if (!vs[i]) continue;
            if (d[i] == a[i] && R[i] > 0) d[i] ^= 1, d[R[i] + 1] ^= 1;
        }
        REP(i, 1, n) cout << (vs[i] ? a[i] ^ d[i] : a[i]);
        cout << '\n';
        return 0;
    }
}