CF 1382C2 Prefix Flip (Hard Version)

题目描述

https://codeforces.com/contest/1382/problem/C2

Solution

我们考虑倒序枚举，如果相同则跳过，否则就把第一位换上来，容易得到总操作次数为 $2n$

但这样做的时间复杂度为 $O(n^2)$，当然可以用平衡树来维护，但是太麻烦了

注意到每次翻转的仅为前缀且倒叙枚举，所以我们可以记录一下所在位置而不是真正的去翻转

#include <iostream>
#include <cstdio>
#include <vector>
#define maxn 100010
using namespace std;

int n, a[maxn], b[maxn]; 

char s[maxn], t[maxn];

void work() {
    cin >> n >> s + 1 >> t + 1; vector<int> ans;
    for (int i = 1; i <= n; ++i) a[i] = s[i] - '0', b[i] = t[i] - '0';
    for (int i = n, r = n, l = 1, t = 0; i; --i, r += l < r ? -1 : 1) {
        if ((a[r] ^ t) == b[i]) continue;
        if ((a[l] ^ t) == b[i]) ans.push_back(1);
        ans.push_back(i); swap(l, r); t ^= 1; 
    }
    cout << ans.size() << " ";
    for (auto u : ans) cout << u << " "; cout << "\n"; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
} 

另外一种做法，我们注意到可以 $n$ 此操作将 $a$ 变成全 $0$

具体的操作大概就是如果 $a[i]\neq a[i+1]$，那么我们直接翻转 $pre[i]$

那么我们可以 $a\rightarrow 0\rightarrow b$

#include <iostream>
#include <cstdio>
#include <vector>
#define maxn 100010
using namespace std;

int n, a[maxn], b[maxn]; 

char s[maxn], t[maxn];

void work() {
    cin >> n >> s + 1 >> t + 1; vector<int> op1, op2;
    for (int i = 1; i <= n; ++i) a[i] = s[i] - '0', b[i] = t[i] - '0';
    a[n + 1] = b[n + 1] = 0; 
    for (int i = 1; i <= n; ++i) {
        if (a[i] != a[i + 1]) op1.push_back(i);
        if (b[i] != b[i + 1]) op2.push_back(i); 
    }
    op1.insert(op1.end(), op2.rbegin(), op2.rend());
    cout << op1.size();
    for (int u : op1) cout << " " << u; cout << "\n"; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work();
    return 0;
}