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;