给定两个长度为 的 串 和 ,要求串 的任意子序列经过若干次“旋转”操作变为串 。
对于一次“旋转操作”我们这样定义:
如果我们要旋转的序列为
那么旋转之后的序列为
例如对于
如果我们旋转的子序列的下标为 (从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;
}