CF1370E Binary Subsequence Rotation

题目

转自CF1370E Binary Subsequence Rotation

大意

给你两个 01 串，求最少的操作次数，使这个串相等。

一次操作：任选几个不同位置上的数，然后讲这些数顺时针旋转（就是将第一个挪到最后，其它的往前）。

思路

很显然，两串相同的是不影响答案的。而且不需要选择连续的位置，如果有一个 01 交替的子串，那么只需要 1 次操作，就可以将它们变为一样的。

所谓 01 交替串，举个例子，A 串为0101010，B串则为1010101。

这样就有了一个很裸的想法：每次找到最长的 01 交替串，将它们变成一样的，直到找不出为止。答案就是能找到几个这样的串。

然后我打了一发暴力，T14；记录下每次可以是 01 交替串的位置，WA9，然后凉了。

因为每次要找的是最长的 01 交替串，所以答案其实就是每个位置及之前的0和1数量差的最大绝对值，即前缀最大差值。

为什么呢？

因为我们找的字符串需要是 01 交替的，而每一个 01 交替就对当前位置及之前的0和1数量差贡献了1。

并且不能有连续个 0 或 1，每有几个连续的，那么就对数量差贡献了1。

代码

int ans1 = 0, ans2 = 0;
int tmp = 0;
for(int i = 1; i <= n; i++) {
    tmp += a[i] - '0';
    tmp -= b[i] - '0';
    ans1 = max(tmp, ans1);
    ans2 = min(tmp, ans2);
}
cout << ans1 - ans2 << endl;