CF1370E Binary Subsequence Rotation
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; 
投递华为等公司10个岗位 >