CF1458D Flip and Reverse 题解

JiaY19 / 2024-10-21 / 原文

思路

由于它要求 $\text{01}$ 数量相等，我们可以考虑站在前缀和的角度看待这个问题。

我们将 $0$ 看作负一，$1$ 看作一。

可以把它化成一个折线图（方便观察）。

观察一下它的操作实际上在干什么。

容易发现，在折线图上，我们把操作的 $[l,r]$ 的整段折线 reverse 了一遍。

同样的，我们也就可以把前缀和数组相等的两个位置中间的一段进行 reverse。

这个操作其实是很强的。

由于我们不会改变前缀和数组。

那么我们可以对每一个前缀和建一张图。

初始变量 $s=0$。
遇到一个 $1$，我们连一条 $s\rightarrow s+1$ 的边，并让 $s$ 加一。
遇到一个 $0$，我们连一条 $s\rightarrow s-1$ 的边，并让 $s$ 减一。

我们可以发现，操作相当于我们可以可以从一个点出发，任意的跑一条回路。

只需要求一个字典序最小的欧拉回路即可。

Code

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1000010], *b;
string s;

inline void solve() {
  cin >> s;
  n = s.length();
  b = a + 500005;
  int c = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i - 1] == '0') {
      c--;
      b[c]++;
    } else {
      b[c]++;
      c++;
    }
  }
  int d = 0;
  for (int i = 1; i <= n; i++) {
    if (!b[d] || (b[d - 1] >= 2)) {
      d--;
      b[d]--;
      cout << 0;
    } else {
      b[d]--;
      d++;
      cout << 1;
    }
  }
  cout << "\n";
}

int main() {
  int t;
  cin >> t;
  while (t--) solve();
}