CF1370E Binary Subsequence Rotation 做题记录

给定两个长度为 $n$ 的 $01$ 串 $a$ 和 $b$，要求串 $a$ 的任意子序列经过若干次“旋转”操作变为串 $b$。

对于一次“旋转操作”我们这样定义：

如果我们要旋转的序列为

$c_1,c_2,c_3,c_4,c_5...c_n$

那么旋转之后的序列为 $c_n,c_1,c_2,c_3,c_4...c_{n-1}$

例如对于 $s=1110100$

如果我们旋转的子序列的下标为 ${2,6,7}$（从1开始）

那么旋转之后的串为 $1010110$

求至少进行多少次“旋转”操作，能够把串 $a$ 变成串 $b$

$n(1\le n\le 10^6)$。

首先 $0$、$1$ 数量不同显然无解。

发现 $a_i=b_i$ 的位置不动是最优的，只考虑 $a_i\not=b_i$ 的位置。

设剔除掉所有 $a_i=b_i$ 的位置后的 $a$ 为 $c$，那么显然 $c$ 中 $0$ 的个数和 $1$ 的个数是相等的。

考虑一次操作能干什么，显然可以选择 $c$ 中的一个 $0$ 和一个 $1$，消除这两个位置。更进一步，每一次操作都可以选一个 $0101010101$ 或者 $1010101010$ 这样 $01$ 相间的长度为偶数的子序列，把这些位置都消除。

那么问题就变成了把 $c$ 划分成尽量少的 $01$ 相间的偶长子序列，有一个朴素的贪心算法：

• 设 $cnt_0,cnt_1$ 分别表示当前以 $0$ 和 $1$ 结尾的子序列有多少个，那么扫一遍 $c$，能接就接，否则新建即可。

这样选出来的 $01$ 相间的子序列显然是最少的，但是不一定都是偶长。不难发现，由于 $c$ 中 $0$ 和 $1$ 的个数相等，所以一定不会出现长度为 $1$ 的子序列，以 $0$ 结尾的长度为奇数的子序列个数也一定与以 $1$ 结尾的长度为奇数的子序列个数相等。那么让这些长度为奇数的子序列按照结尾字符两两配对，每对中结尾靠后的字符拼到结尾靠前的子序列后面即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=1000005;

int n;
char a[S],b[S];

int main()
{
	scanf("%d",&n);
	scanf("%s%s",a+1,b+1);
	int cnta=0,cntb=0;
	for(int i=1;i<=n;i++) cnta+=a[i]=='1',cntb+=b[i]=='1';
	if(cnta!=cntb)
	{
		puts("-1");
		return 0;
	}
	int cnt0=0,cnt1=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=b[i])
		{
			if(a[i]=='0')
			{
				if(cnt1>0) cnt1--;
				cnt0++;
			}
			else
			{
				if(cnt0>0) cnt0--;
				cnt1++;
			}
		}
	}
	printf("%d\n",cnt0+cnt1);
	return 0;
}