IV.CF1458D Flip and Reverse
神仙题。
首先,很容易想到我们另开一个数组,在0
的位置记作(-1),在1
的位置记作(+1),然后作一遍前缀和。这样,若两个位置前缀和相等,则显然它们间的子串是01
数量相等的。
然后,对于这种01
数列上套前缀和的,一个显然的想法是将其画成折线图的样式。
/
/ /
// /
101100111000
我们考虑对整个序列执行操作。区间翻转(指左右交换),画出图来会发现是将整个图旋转(180^{circ});区间反转(指01
交换),画出图来会发现是将整个图上下颠倒。两个操作叠成buff
,我们发现效果就是左右翻转上述折线图。
明显,在任意两个高度相等的点,我们都可以翻转中间的所有东西。
我们还可以大胆猜结论。比如说,假如上述折线图中有一条从高度 (i) 到高度 (j) 的线段(明显 (i,j) 必定差为 (1);同时我们并不关心到底是 (i) 到 (j) 还是 (j) 到 (i)),我们就再开一张新图,并在新图中连一条 (i) 到 (j) 的无向边。则我们发现,上述的折线路径,在新图中就变成了从 (0) 点到某一点的一条欧拉路径(从一点到另一点,经过且仅经过每条无向边一次的路径)。大胆假设的结论,就是新图中任意一条欧拉路径皆可以通过上述翻转由原图得到。
证明?OI不需要证明,干就完了
于是就直接贪心即可。
代码:
#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;
}