本文共 1249 字，大约阅读时间需要 4 分钟。

伟大的人类智慧

把 0 看作 -1 ，把 1 看作 +1 ，计算前缀和

我们可以发现先转换再翻转一个区间，就是翻转他们的前缀和区间。（可以画一个函数图像来理解），那么答案就变成了可以任意翻转区间 $[l,r],s_l=s_r$ ，求

如序列 $\{$

转换再翻转 $\{$

我们把前缀和序列的每一位看成点，相邻（位置）的点连边，就形成了一条链。因为可以翻转区间，原本的边 $k->k+1$ ，翻转区间后， $k$ 的下一个数就可能变成 $k-1$ 了（见上面那个例子）。这就启发我们相邻（值）的点之间可以直接到达。这样就把翻转操作变成了跳点。显然不是任意的 $k->k-1$ 都是合法的。

合法条件是什么呢？

从 k 走到 k-1 ，当且仅当没有 k+1 或者 k 和 k-1 之间有至少 2 条边。（想想这是为什么

最后贪心的填每位（网上题解说走一条欧拉路其实一个意思），于是就做完啦。

//AC代码#include
   
    using namespace std;int T,n,sum,val[1000100];char s[500100];int main(){   	scanf("%d",&T);	while(T--){   		scanf("%s",s),n=strlen(s),sum=0;		for(int i=0;i
    
     =2)putchar('0'),val[j--]--;			else if(val[j+1]>=2)putchar('1'),val[++j]--;			else if(val[j])putchar('0'),val[j--]--;			else if(val[j+1])putchar('1'),val[++j]--;			else{   puts("FAIL");return 0;} 		}puts("");		for(int i=0;i<=2*n;i++)val[i]=0;	}	return 0;}