题解 CF1458D 【Flip and Reverse】

· · 题解

现场试图看这道题结果什么思路都没有。

考虑记 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。

看到没？什么超纲的算法都没有。所以啊，菜是原罪/kk

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fz(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define ffe(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
template<typename T> void read(T &x){
    char c=getchar();T neg=1;
    while(!isdigit(c)){if(c=='-') neg=-1;c=getchar();}
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    x*=neg;
}
const int MAXN=5e5;
const int DELTA=5e5+2;
int n,cnt[MAXN*2+5][2];
char s[MAXN+5];
void solve(){
    scanf("%s",s+1);n=strlen(s+1);
    int cur=0;
    for(int i=1;i<=n;i++){
        cnt[DELTA+cur][s[i]-'0']++;
        if(s[i]=='0') cur--;else cur++;
    }
    int x=0;
    for(int i=1;i<=n;i++){
        if(cnt[x+DELTA][0]&&cnt[x-1+DELTA][1]) cnt[x+DELTA][0]--,x--,putchar('0');
        else if(cnt[x+DELTA][1]) cnt[x+DELTA][1]--,x++,putchar('1');
        else cnt[x+DELTA][0]--,x--,putchar('0');
    }
    printf("\n");
}
int main(){
    int qu;scanf("%d",&qu);
    while(qu--) solve();
    return 0;
}