CF1458D Flip and Reverse 建图+欧拉路

CF1458D Flip and Reverse

伟大的人类智慧

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

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

如序列 { a i } \{a_i\} { ai?} 为 $100101$ ，则前缀和序列 { s i } \{s_i\} { si?} 为 $010?10?10$ （第 0 位为 0

转换再翻转 { a i } \{a_i\} { ai?} 的区间 $[1,4]$ ，就相当于翻转 { s i } \{s_i\} { si?} 的区间 $[0,4]$ ，第 0 位值不变，那么 { s i } \{s_i\} { si?} 第 0 位的下一位就变成了原来 { s i } \{s_i\} { si?} 的第 3 位。

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

合法条件是什么呢？

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

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

//AC代码
#include<bits/stdc++.h>
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<n;i++)s[i]=(s[i]=='1'?1:-1);for(int i=0;i<n;i++)val[max(sum,sum+s[i])+n]++,sum+=s[i];for(int i=0,j=n;i<n;i++){
    if(val[j]>=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;
}