题解：CF1458D Flip and Reverse

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

选择一个满足 $01$ 个数相同的子区间。
将这个区间 flip。
再翻转区间。

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

$01$ 个数相同 $\to$ 容易想到经典的括号序列折线转化，我们将 $0\to -1,1\to +1$ ，然后将原序列变成前缀和序列。这时候我们发现操作只会影响到这一段区间内的前缀和序列。
记一个 $s_0=0$ ，然后 $s_{1\sim n}$ 表示这个前缀和序列。那么我们会发现，操作区间 $[l,r]$ 相当于翻转 $s_{l\sim r-1}$ 。操作的时候需要满足 $s_{l-1}=s_r$ 。

这时候我们容易想到一个牛逼的建模：将

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

条边全用掉，最终桶会在贪心过程中清空掉。

CPP

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;
}

题解：CF1458D Flip and Reverse

文章操作

相关推荐

评论

题解：CF1458D Flip and Reverse