题解：AT_agc019_d [AGC019D] Shift and Flip

· · 题解

题目传送门

题意

给出两个 01 序列 A 和 B，有三种操作：把序列 A 左移一位，把序列 A 右移一位，选择序列 B 中的一个位置 i，满足 B_i=1，把 A_i 变成 1-A_i。求使 A 和 B 相等的操作次数的最小值。

分析

首先我们分类讨论，如果把所有操作看成一个操作序列，我们会发现一个规律。无论是什么样的序列，它的操作序列一定满足对于位置 i 先左移，再右移，到达目标位置 j 后再右移，再左移回到位置 j，或者反过来，而第三种操作就穿插在这些操作中。

我们考虑怎么样枚举这些操作，我们注意到，从位置 i 移动到位置 j 的距离是不确定的，所以考虑枚举这个，而其他的则可以再确定这个距离后计算出来。

现在假定我们确定了移动距离 x，确定方向向右。那么在移动的过程中，如果发现对于 A_i=0 但是 B_{i+x}=1 的情况，这样只需要在平移完后进行一次操作三即可，那么如果是 A_i=1 但是 B_{i+x}=0 的情况就会复杂一些，如果在从 i 平移到 i+x 的这段区间中存在 B_j=1 那么我们可以再平移到这里时进行一次操作三即可，这里的区间判断，我们用前缀和即可。

那么如果这段区间不存在 B_j=1 怎么办，那么我们就只能在平移开始前或者结束后再进行平移使得 B_j=1。该怎么计算呢，这里需要我们先预处理出对于每一个序列 B 中的位置 i 找到它左边最近的 1 的位置，记为 pre_i，找到右边最近的 1 的位置，记为 nxt_i。每次发现某一个位置需要这样操作是，就用一个数组记下它的左边和右边的 1 的距离。之后对这个数组进行排序，枚举哪些位置是在平移前进行操作三，和哪些位置在操作后进行操作三。之后计算答案就很简单了，每次把一个位置从原先在平移前处理改成在平移处理后处理，计算新的答案即可。

因为这只是对右边平移的情况，所以之后还要再做一次对左边的处理。

同时注意要化链成环，所以我在代码中复制了一份相同的序列 A 和 B，这样就可以正常处理了。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010101;
ll n,a[N],b[N],f[N],pre[N],nxt[N],sa,sb,ans=1e18;
struct node{ll l,r;}p[N];
bool cmp(node a,node b){
    if(a.l==b.l)return a.r<b.r;
    return a.l>b.l;
}
void solvel(ll x){
    ll pos=x,tot=0;
    for(int i=1;i<=n;i++){
        if(!a[i]&&b[i+x])pos++;
        if(a[i]&&!b[i+x]){
            pos++;
            if(!(f[i+x]-f[i-1]))p[++tot]={pre[i+n],nxt[i+x]};
        }
    }
    sort(p+1,p+tot+1,cmp);
    p[tot+1]={0,0};
    ll maxn=0;
    for(int i=1;i<=tot+1;i++){
        ans=min(ans,pos+(maxn+p[i].l)*2);
        maxn=max(maxn,p[i].r);
    }
}
void solver(ll x){
    ll pos=-x,tot=0;
    for(int i=n+1;i<=2*n;i++){
        if(!a[i]&&b[i+x])pos++;
        if(a[i]&&!b[i+x]){
            pos++;
            if(!(f[i]-f[i+x-1]))p[++tot]={pre[i+x],nxt[i-n]};
        }
    }
    sort(p+1,p+tot+1,cmp);
    p[tot+1]={0,0};
    ll maxn=0;
    for(int i=1;i<=tot+1;i++){
        ans=min(ans,pos+(maxn+p[i].l)*2);
        maxn=max(maxn,p[i].r);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string s1,s2;
    cin>>s1>>s2;
    n=s1.size();
    s1=" "+s1;
    s2=" "+s2;
    for(int i=1;i<=n;i++)a[i]=s1[i]-'0',b[i]=s2[i]-'0',sa+=a[i],sb+=b[i];
    if(sa&&!sb){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++)a[i+n]=a[i],b[i+n]=b[i];
    for(int i=1;i<=2*n;i++)f[i]=f[i-1]+b[i];
    for(int i=1;i<=2*n;i++){
        pre[i]=pre[i-1]+1;
        if(b[i])pre[i]=0;
    }
    for(int i=2*n;i>=1;i--){
        nxt[i]=nxt[i+1]+1;
        if(b[i])nxt[i]=0;
    }
    for(int i=1;i<=n;i++)solvel(i-1);
    for(int i=1;i<=n;i++)solver(1-i);
    cout<<ans;
    return 0;
}