题目传送门
题意
给出两个 \(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;
}