CF1458D-Flip and Reverse

题目:

题目描述:

You are given a string $ s $ of 0’s and 1’s. You are allowed to perform the following operation:

2. choose a non-empty contiguous substring of $ s $ that contains an equal number of 0’s and 1’s;

3. flip all characters in the substring, that is, replace all 0’s with 1’s, and vice versa;

4. reverse the substring. For example, consider $ s $ = 00111011, and the following operation:

5. Choose the first six characters as the substring to act upon: 00111011. Note that the number of 0’s and 1’s are equal, so this is a legal choice. Choosing substrings 0, 110, or the entire string would not be possible.

6. Flip all characters in the substring: 11000111.

7. Reverse the substring: 10001111. Find the lexicographically smallest string that can be obtained from $ s $ after zero or more operations.

输入格式:

The first line contains a single integer $ T $ ( $ 1 \leq T \leq 5 \cdot 10^5 $ ) — the number of test cases. Each of the following $ T $ lines contains a single non-empty string — the input string $ s $ for the respective test case.

All strings consist of characters 0 and 1, and their total length does not exceed $ 5 \cdot 10^5 $ .

输出格式:

For each test case, on a separate line print the lexicographically smallest string that can be obtained from $ s $ after zero or more operations.

样例:

样例输入1:

1
2
3
4

3
100101
1100011
10101010

样例输出1:

1
2
3

010110
0110110
10101010

思路:

考虑记 $0$ 为 $-1$，$1$ 为 $+1$，这样可以得到一个长度为 $|s|$ 的由 $+1$ 和 $-1$ 组成的序列。

然后对这个序列做一遍前缀和，并连一条 $s_i\to s_{i+1}$ 的有向边，这样可以得到一张图，一个欧拉回路就对应着一个字符串。

考虑题目中那个奇怪的操作的本质。假设我们对区间 $[l,r]$ 进行操作。既然 $[l,r]$ 要求 01 个数相等，那么肯定有 $s_{l-1}=s_r$，而翻转+反转实际上等于将这些边反向。所以实际上该操作等价于选择一个环然后将环上所有边反向。

这里需要观察出一个性质：就是操作前后，原图所包含的边集 $E$ 是不变的。因为每次操作是将边反向，所以如果把有向边改为无向边，那么边集显然是不变的。又由于我们操作的是一个环，所以对于一条边 $(x,y)$，$x\to y$ 和 $y\to x$ 的次数是一样的，所以 $x\to y$ 和 $y\to x$ 在操作前后出现次数都是相同的。

有了这个性质，我们还需观察出另一个性质：原图任意一条欧拉回路（起点和终点必须与初始相同）代表的都可以由原字符串进行一系列操作得到。这里楼下的题解没有给出证明，这里给出简略的证明：首先我们假设原路径与当前路径在 $x$ 位置出现了分歧，一个走了 $x \to x+1$ 的边，一个走了 $x\to x-1$ 的边。而这两个路径终究还是要走 $x\to x-1$ 和 $x\to x+1$ 的边的，所以肯定有一条边 $x+1 \to x$，也有一条边 $x-1\to x$，此时我们选择 $x\to x-1\to x\to x+1\to x$，并将其翻转，看看会发生什么。此时我们惊奇地发现 ，原来先走 $x\to x-1$ 的路径改走 $x\to x+1$ 了！以此类推，最后两个路径一定会重合。

于是此题就变为：求字典序最小的欧拉序。直接贪心就可以了。能填 $0$ 就填 $0$，不能就填 $1$。

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// Problem: CF1458D Flip and Reverse
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1458D
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
map<int, int> cnt;
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        string s;
        yin >> s;
        int n = s.size(), p = 0;
        cnt.clear();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '1')
            {
                ++cnt[p++];
            }
            else
            {
                ++cnt[--p];
            }
        }
        p = 0;
        for (int i = 0; i < n; i++)
        {
            if (cnt[p - 1] > 0 && (!cnt[p] || cnt[p - 1] > 1))
                --p, cnt[p]--, putchar('0');
            else
                cnt[p]--, p++, putchar('1');
        }
        yout << endl;
    }
    return 0;
}