题解：CF1458D Flip and Reverse

· · 题解

520 表白出题人，真的是非常好的 Ad-Hoc，令我原地升天。

一般遇到这种诡异的操作都考虑找一找不变的量和变化了的量。

这时候我们容易想到一个牛逼的建模：将 s_i\to s_{i+1}。那么图上的一条路径就会对应一个可能出现的原串子串。为什么这么说呢？我们考虑操作的含义，相当于选择了一个以 s_{l-1}=s_r 为起点和终点的环（欧拉回路），然后翻转上面所有边的方向。因为连边的时候只可能有 x\to x+1,x\to x-1 这两种边，所以实际上这个图上任意一个环都是 x\to x+1\to \cdots\to y-1\to y\to y-1\to\cdots \to x+1\to x 的形式，也就是说翻转边的方向对于一个环是没有影响的。以 x 为起点和终点的欧拉回路应当是由若干个包含 x 的环组成的，所以翻转操作相当于翻转了这些环的访问顺序。

因为可以任意地翻转欧拉回路，所以就相当于，环的访问顺序可以是任意的。这时候，任意欧拉回路就会代表在最终字符串（经过操作的）中可能出现的一个子串，保证一一对应。

那么最终的字符串可以表示为由 0 开始的一条欧拉回路，后面接一个到 s_n 的路径。所以我们只要找一个图上字典序最小的欧拉回路就好了，显而易见，我们从起点 x=0 开始，走 n 条边，每次贪心地走 0 边，走的过程中要维护连通性，从而保证最后可以走到 s_n。

复杂度 O\left(n\right)。比较有意思的是如果用的是桶记录边，多测不用清空，因为在贪心找回路的过程中会把 n 条边全用掉，最终桶会在贪心过程中清空掉。

constexpr tp N = 1e6 + 8, K = 5e5 + 2;
tp n;
string s;
array<array<tp, 2>, N> e;

tp HARUTO() {
   cin >> s, n = s.size(), s = ' ' + s;
   tp u = 0;
   //for (tp i = 0; i <= n + K; ++i) e[i][0] = e[i][1] = 0;
   for (tp i = 1; i <= n; ++i) {
      e[u + K][s[i] - '0']++;
      u += s[i] == '0' ? -1 : 1;
   }
   u = 0;
   for (tp i = 1; i <= n; ++i) {
      if (e[u + K][0] && e[u - 1 + K][1]) cout << '0', e[u + K][0]--, u--;
      else if (e[u + K][1]) cout << '1', e[u + K][1]--, u++;
      else cout << '0', e[u + K][0]--, u--;
   }
   cout << "\n";
   return 0;
}

int main() {
   QWQ();
   tp t = 1; cin >> t;
   while (t--) HARUTO();
   return 0;
}