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;