cf1458D. Flip and Reverse

http://codeforces.com/contest/1458/problem/D

题意

给定一个01串，定义一次操作为 选择一个01个数相同的子串,将其取反再翻转
询问经过任意次操作后这个串字典序最小是什么
\(|s|,T<=5*10^5\)

思路

将所有0看做-1 1看做-1
计算它们的前缀和
对一个区间取反再翻转 就相当于把这个前缀和区间翻转
按照原字符串建一张图，对于每个x建一个点
设当前x值为k 遇到一个1 就从k到k+1连一条无向边
当一个子串可以操作时,相当于在一个环上走一圈
然后贪心能往小的数走就往小的数走
从k走到k-1当且仅当没有k+1或者k和k-1之间有至少2条边(还有1条边返回k)
\(O(\Sigma(n))\)

错误

莫名其妙tle 换个快读输出换成puts、string换成char 就好了。。。

参考：https://blog.csdn.net/RA100FDM/article/details/113838183
https://www.cnblogs.com/zkyJuruo/p/14163445.html

cf1458D. Flip and Reverse

原文：https://www.cnblogs.com/a-little-mushroomspy/p/14438773.html