题目大意

题目描述

给定两个长度为$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≤n≤10^6)$
第二行输入串$a$

第三行输入串$b$

输出格式

输出为$1$行，为最小的操作次数

思路

首先，如果要求我们改变的次数最小，那么我们就只改变$a$与$b$中不相同的元素。

设集合$c$为$a$中与$b$中的元素不同的元素，并且对于每个元素其值等于$a$的值。

而对于$c$中的元素而言，每一对不同的$1$和$0$都可以进行一次“旋转”操作，我们可以看作其两个元素进行交换。

而若干个元素的“旋转”操作可以看作若干次“交换”操作

因此如果$c$当中的$1$和$0$的个数不同是一定不能将$a$变为串$b$

而现在，我们的目标为用尽量少的操作使得$c$中的元素全部取反（即$1$变成$0$，$0$变成$1$）

那么我们每次进行旋转操作的序列一定是形如$010101$或$101010$这样的序列（必须为偶数位）

如果我们进行旋转操作的序列为形如$111000$这样的序列，那么就等价于我们进行三次$10$这样的旋转操作

那么我们要使得进行的操作次数尽量少，即每次使得我们选的子序列尽量的长

那么我们每进行一次操作就会使得和最大的子段的和减一，即每进行一次操作都能使得$max(\sum_{i=l}^r\left | c_i \right |)$减一

证明：

假设子段$[l,r]$的和为正数，那么子段两边的元素一定是$-1$，否则$\sum_{i=l}^r\left | c_i \right |$可以更大。

同理$c[l]$与$c[r]$必然是$1$，否则缩小区间范围，一定可以更大。

设该子段中一共有$k$个$1$，长度为$m$，那么该子段的$-1$的个数为$m-k$。

那么在该子段外至少有$2\times k -m$个$-1$

对于其中的$-1$，我们至多$m-k$次就可以将所有的$-1$变$1$（即所有的$-1$全都挨在一起的情况）

而对于每次操作，我们选择的$1$的个数比$-1$的个数多一定更优

因为我们当前子段的和是最大的，且为正，因此$1$的个数必然比$-1$的个数多

考虑反证

如果我们选的$-1$比$1$多的话，那么在当前子段至多选

$2\times m-2\times k-1$个元素

如果我们$1$的个数比$-1$的个数多，那么当前子段至多选

$2\times m-2\times k+1$个元素

而对于外面的元素，如果排序方式改变最多损失两个元素

因此至少不会变坏，且会更优

如果我们$-1$选$p$个，那么$1$必然会选$p+1$个

那么，其减少了$1$

如果到最后的序列不存在$-1$，那么每次我们至少可以从当前序列中选出一个$1$取反，因为在该子段外至少有$2\times k -m$个$-1$

因此，每次操作我们都可以使得$max(\sum_{i=l}^r\left | c_i \right |)$减一

并且，因为其和最大，所以能够确保每次操作，都能够作用于当前子段

那么，当$max(\sum_{i=l}^r\left | c_i \right |)$减为$0$时，即最小操作次数。

答案即为$max(\sum_{i=l}^r\left | c_i \right |)$

$QED$

而我们可以用下面代码$O(n)$的求出上述式子

#include <iostream>

using namespace std;

const int maxn = 1e6 + 10;

char a[maxn],b[maxn];

int c[maxn],n;


int get(int x){
    int cur = 0,res = 0;
    for (int i = 0; i < n; i++){
        cur += x * c[i];
        res = max(res,cur);
        if (cur < 0) cur = 0;
    }
    return res;
}

int main(){
    cin >> n >> a >> b;
    int s0 = 0,s1 = 0;
    for (int i = 0; i < n; i++){
        if (a[i] != b[i] && a[i] == '1'){ 
            c[i] = 1;
            s1++;
        }
        if (a[i] != b[i] && a[i] == '0'){ 
            c[i] = -1;
            s0++;
        }
    }
    if (s1 != s0){
        cout << -1;
        //system("PAUSE");
        return 0;
    }
    cout << max(get(1),get(-1));
    //system("PAUSE");
    return 0;
}