$Link$
有一个 $01$ 串 $s$。
你可以执行任意多次操作，每次操作可以选择一段 $0$ 和 $1$ 个数相同的子串，然后把它翻转，再把其中的 $0$ 变成 $1$，$1$ 变成 $0$。
求可以得到的字典序最小的 $s$。
多组数据，$\sum|s|\le5\times10^5$。
妙妙题，讲的可能不是很清楚。
首先我们考虑把 $0$ 变成 $-1$，然后做个前缀和。于是修改的区间需要满足 $sum_{l-1}=sum_r$。
考虑操作对于 $sum$ 的影响，稍微手玩一下可以得到，操作一次区间 $[l,r]$ 实际上就是翻转 $sum_{l-1}\sim sum_r$。
那多次操作呢？
注意到 $sum$ 的值实际上不会被改变，只是访问顺序不一样了。所以我们可以把 $sum$ 看作一个链表，一次操作相当于把区间 $[l-1,r]$ 的边反向，再修改一下 $l-1$ 和 $r$ 的前驱后继。
考虑直接按 $sum$ 建图，相邻的 $sum$ 就在对应的点间连边。那原串就相当于按照一定的顺序访问每条边，从 $0$ 开始在图上走了一条欧拉路。
那直接大胆猜想，一条欧拉路就相当于一个有可能变换得到的 $s$。
反映到序列上，也就是假设 $sum_i=x,sum_{i+1}=x+1,sum_j=x,sum_{j+1}=x-1,sum_{k-1}=x-1,sum_k=x(i<j<k)$ 我们可以利用操作使得 $sum_{i+1}=x-1$。
这是废话，我们直接令 $l=i+1,r=k$，操作一次不就好了。
那直接建图找字典序最小的欧拉路就好啦。
时间复杂度 $O(\sum|s|)$。
$code$
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
int f = 1, x = 0;
char ch;
do{
ch = getchar();
if (ch == '-')
f = -1;
}while(ch < '0' || ch > '9');
do{
x = x * 10 + ch - '0';
ch = getchar();
}while(ch >= '0' && ch <= '9');
return f * x;
}
const int N = 5e5;
int tt;
string s;
int edge[2 * N + 1][2];
int main()
{
tt = read();
while (tt--) {
cin >> s;
for (int i = 0, sum = 0; i < s.size(); i++) {
if (s[i] == '0') {
edge[sum + N][0]++;
sum--;
} else {
edge[sum + N][1]++;
sum++;
}
}
int now = N;
while (true) {
if (edge[now][0] && edge[now - 1][1]) {
putchar('0');
edge[now][0]--;
now--;
} else {
if (edge[now][1]) {
putchar('1');
edge[now][1]--;
now++;
} else {
if (edge[now][0]) {
putchar('0');
edge[now][0]--;
now--;
} else {
break;
}
}
}
}
putchar('\n');
}
return 0;
}
|