题解：CF2254C2 Marenol (hard version)

fish_love_cat · 2026-08-10 03:02:09 · 题解

首先你要会弱化。

依旧奇偶拆开来考虑，这个题要最小化操作次数，那么也就意味着我们肯定需要保证同个颜色的点相对顺序不变。

于是我们可以依次匹配，显然对应点和当前点的距离就是这个点的贡献。双指针即可。

线性。

inline void solve(){
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    s=" "+s,t=" "+t;
    int op[2][2]={};
    for(int i=1;i<=n;i++)
    op[i&1][s[i]-'0']++,op[i&1][t[i]-'0']--;
    if(op[0][0]||op[1][0])cout<<"-1\n";
    else{
        int ans=0;
        for(int i=1,j=1;i<=n&&j<=n;i+=2,j+=2){
            while(i<=n&&s[i]!='1')i+=2;
            while(j<=n&&t[j]!='1')j+=2;
            if(i<=n)ans+=abs(i-j)/2;
        }
        for(int i=2,j=2;i<=n&&j<=n;i+=2,j+=2){
            while(i<=n&&s[i]!='1')i+=2;
            while(j<=n&&t[j]!='1')j+=2;
            if(i<=n)ans+=abs(i-j)/2;
        }
        cout<<ans<<'\n';
    }
}
// ？

// 不净 是青灯俗债
// 不灭 是沉舟摆
// 未契 命运的号牌
// 系着 琉璃灯彩
// 谁能够 万般自在
// 贪瞋痴 论斤贩卖
// 敲碎了 最后期待
// 未契那 人生百载