巧妙的转化为欧拉路径。
将 0 视作 $-1$，将 1 视作 $+1$，转化为前缀和 $s_i$。操作 $[l,r]$ 的条件为 $s_{l-1}=s_r$。尝试研究操作的本质，容易发现就是对于 $[l-1,r]$ 的的前缀和的 reverse 操作。
对于前缀和 $s_i$ 对应的点建 $s_i\to s_{i+1}$ 这条边，而原字符串相当于一条欧拉路径。操作就相当于找到一个环，将上面的边反向。但实际上边集是不会变的，因为只有相邻的 $s_i$ 之间才会连边，所以环一定是若干个二元环拼起来的。更进一步的，我们发现，所有的可能的字符串，对应的图都是一样的，而图也对应所有可能的字符串。因为对于两条不同的欧拉路径，中间不同部分我们一定可以通过操作将其变为相同。所以问题转化为求字典序最小的欧拉路径。
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
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e5+10;
int T,n;
char s[N];
int e[N<<1][2];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%s",s+1);
n=strlen(s+1);
int x=N;
for(int i=1;i<=n;i++)
e[x][s[i]-'0']++,x+=(s[i]=='0'?-1:1);
x=N;
for(int i=1;i<=n;i++)
{
if(e[x][0]&&e[x-1][1])e[x][0]--,x--,putchar('0');
else if(e[x][1])e[x][1]--,x++,putchar('1');
else e[x][0]--,x--,putchar('0');
}
puts("");
}
return 0;
}
|