专栏文章

题解：AT_agc019_d [AGC019D] Shift and Flip

hhoko
AT_agc019_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miob1vrj
此快照首次捕获于
2025/12/02 16:17
3 个月前
此快照最后确认于
2025/12/02 16:17
3 个月前
查看原文

题目传送门

题意

给出两个 0101 序列 AA 和 BB，有三种操作：把序列 AA 左移一位，把序列 AA 右移一位，选择序列 BB 中的一个位置 ii，满足 Bi=1B_i=1，把 AiA_i 变成 1−Ai1-A_i。求使 AA 和 BB 相等的操作次数的最小值。

分析

首先我们分类讨论，如果把所有操作看成一个操作序列，我们会发现一个规律。无论是什么样的序列，它的操作序列一定满足对于位置 ii 先左移，再右移，到达目标位置 jj 后再右移，再左移回到位置 jj，或者反过来，而第三种操作就穿插在这些操作中。
我们考虑怎么样枚举这些操作，我们注意到，从位置 ii 移动到位置 jj 的距离是不确定的，所以考虑枚举这个，而其他的则可以再确定这个距离后计算出来。
现在假定我们确定了移动距离 xx，确定方向向右。那么在移动的过程中，如果发现对于 Ai=0A_i=0 但是 Bi+x=1B_{i+x}=1 的情况，这样只需要在平移完后进行一次操作三即可，那么如果是 Ai=1A_i=1 但是 Bi+x=0B_{i+x}=0 的情况就会复杂一些，如果在从 ii 平移到 i+xi+x 的这段区间中存在 Bj=1B_j=1 那么我们可以再平移到这里时进行一次操作三即可，这里的区间判断，我们用前缀和即可。
那么如果这段区间不存在 Bj=1B_j=1 怎么办，那么我们就只能在平移开始前或者结束后再进行平移使得 Bj=1B_j=1。该怎么计算呢，这里需要我们先预处理出对于每一个序列 BB 中的位置 ii 找到它左边最近的 11 的位置，记为 preipre_i，找到右边最近的 11 的位置，记为 nxtinxt_i。每次发现某一个位置需要这样操作是，就用一个数组记下它的左边和右边的 11 的距离。之后对这个数组进行排序，枚举哪些位置是在平移前进行操作三，和哪些位置在操作后进行操作三。之后计算答案就很简单了，每次把一个位置从原先在平移前处理改成在平移处理后处理，计算新的答案即可。
因为这只是对右边平移的情况，所以之后还要再做一次对左边的处理。
同时注意要化链成环，所以我在代码中复制了一份相同的序列 AA 和 BB，这样就可以正常处理了。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...