【AtCoder Grand Contest 019 D】Shift and Flip | Mrsrz's blog

枚举，思维题。

题目大意：

给定两个 01 串 $A,B$，每次可以执行下列操作之一：

• 将 $A$ 向左循环位移一位（第一位移动到最后）。
• 将 $A$ 向右循环位移一位（最后一位移到第一位）。
• 对于一个 $B_i=1$ 的 $i$，令 $A_i=1-A_i$。

问至少操作多少次，才能使 $A=B$。

题解：

先判断无解情况。可以发现，当 $B$ 中有 $1$ 时，一定有解。当且仅当 $B$ 中没有 $1$ 且 $A$ 中有 $1$ 时无解。

我们考虑一开始每个位置最后移到了哪里。枚举偏移量 $t$。那么这样操作次数至少为 $t$ 加上对应位置不相等的数对个数。

考虑一个 $1$ 要变成 $0$，必须找到一个 $B=1$ 的位置进行翻转，$0$ 变成 $1$ 同理（其实 $0$ 变成 $1$ 可以直接在目标位置完成）。

我们假设最终每个位置都向右偏移。那么一个位置要翻转，要么找到左边第一个 $1$，要么找到右边第一个 $1$ 进行翻转。这个可以通过二分得到。

如果往左走，需要走到后返回原位，然后继续走偏移量。就是说需要额外走两倍的这个点到 $1$ 的路程。

如果往右走，有两种情况：

1. $1$ 在它到目标位置的路径上。那么额外的路径为 $0$。
2. $1$ 在目标位置右侧。那么我们到目标位置后，还要到那个 $1$ 处往返一趟，额外路径就是两倍的路程。

对一个点，我们显然只需要左、右二选一。所以我们处理出每个点往左、右的额外花费。

计算时，一部分点选择往左，一部分点选择往右。往左和往右的额外花费都取这些点的最大值。

我们计算最优解，可以按照一维排序，另一维求后缀最大值，然后扫一遍即可。

最终往左偏移同理可得。

时间复杂度 $O(n^2\log n)$。

Code：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2333;
int n,ans=0x3f3f3f3f;
char s[N],ss[N];
vector<int>pos;
vector<pair<int,int> >vc;
int main(){
    scanf("%s%s",s+1,ss+1);
    n=strlen(s+1);
    bool ok1=0,ok2=0;
    for(int i=1;i<=n;++i)ok1|=s[i]=='1',ok2|=ss[i]=='1';
    if(!ok2){puts(ok1?"-1":"0");return 0;}
    for(int i=1;i<=n;++i)if(ss[i]=='1')
    pos.push_back(i-n),pos.push_back(i),pos.push_back(i+n);
    sort(pos.begin(),pos.end());
    for(int t=0;t<n;++t){
        vc.clear();
        int tot=0;
        for(int i=1;i<=n;++i)if(s[i]!=ss[(i+t-1)%n+1]){
            ++tot;
            int L=*(upper_bound(pos.begin(),pos.end(),i)-1);
            int R=*lower_bound(pos.begin(),pos.end(),i);
            int pre=i+(t-n)%n,nxt=i+t;
            int lft=i-L,rgt=R<=nxt?0:R-nxt;
            vc.emplace_back(lft,rgt);
        }
        sort(vc.begin(),vc.end());
        int mx=0;
        for(int i=vc.size()-1;~i;--i)
        ans=min(ans,tot+2*(mx+vc[i].first)+t),mx=max(mx,vc[i].second);
        ans=min(ans,tot+2*mx+t);
        vc.clear();
        tot=0;
        for(int i=n;i;--i)if(s[i]!=ss[(i-t+n-1)%n+1]){
            ++tot;
            int L=*(upper_bound(pos.begin(),pos.end(),i)-1);
            int R=*lower_bound(pos.begin(),pos.end(),i);
            int pre=i-t,nxt=i-(t-n)%n;
            int lft=pre<=L?0:pre-L,rgt=R-i;
            vc.emplace_back(lft,rgt);
        }
        sort(vc.begin(),vc.end());
        mx=0;
        for(int i=vc.size()-1;~i;--i)
        ans=min(ans,tot+2*(mx+vc[i].first)+t),mx=max(mx,vc[i].second);
        ans=min(ans,tot+2*mx+t);
    }
    printf("%d\n",ans);
    return 0;
}