CF1370E Binary Subsequence Rotation 做题记录

给定两个长度为 nn0101aabb,要求串 aa 的任意子序列经过若干次“旋转”操作变为串 bb

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

如果我们要旋转的序列为

c1,c2,c3,c4,c5...cnc_1,c_2,c_3,c_4,c_5...c_n

那么旋转之后的序列为 cn,c1,c2,c3,c4...cn1c_n,c_1,c_2,c_3,c_4...c_{n-1}

例如对于 s=1110100s=1110100

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

那么旋转之后的串为 10101101010110

求至少进行多少次“旋转”操作,能够把串 aa 变成串 bb

n(1n106)n(1\le n\le 10^6)

首先 0011 数量不同显然无解。

发现 ai=bia_i=b_i 的位置不动是最优的,只考虑 ai=bia_i\not=b_i 的位置。

设剔除掉所有 ai=bia_i=b_i 的位置后的 aacc,那么显然 cc00 的个数和 11 的个数是相等的。

考虑一次操作能干什么,显然可以选择 cc 中的一个 00 和一个 11,消除这两个位置。更进一步,每一次操作都可以选一个 01010101010101010101 或者 10101010101010101010 这样 0101 相间的长度为偶数的子序列,把这些位置都消除。

那么问题就变成了把 cc 划分成尽量少的 0101 相间的偶长子序列,有一个朴素的贪心算法:

  • cnt0,cnt1cnt_0,cnt_1 分别表示当前以 0011 结尾的子序列有多少个,那么扫一遍 cc,能接就接,否则新建即可。

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

代码如下:

#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;
}