CF1705D Mark and Lightbulbs 题解

· · 题解

可能更好的阅读体验

题目传送门

题目大意

给定一个长度为 n 的 01 字符串 s，现在你可以选定一个 i\in(1,n) 满足 s_{i-1}\not=s_{i+1}，然后把 s_i 变成 s_i\oplus1。现在你需要把 s 变成另一个给定的字符串 t。求最小的操作数。

n\le 2\times 10^5

题目解析

我们考虑这个操作究竟能干什么。
我们可以发现，进行一次操作可以 使 01 分界线移动 1，不会改变 01 的段数。
所以如果 s 和 t 的 01 段数不同，或者 s_1,t_1、s_n,t_n 不同，就无解。

可以证明存在一种方案使得移动分界线的时候仅仅往同一方向移动，所以就不会有额外的操作出现。
所以就只需要扫一次得到 s,t 所有的 01 分界线，然后答案就是这些对应两个分界线的差的绝对值的和。

代码是非常简短的

int n; ll ans; char s1[maxn],s2[maxn];
int p1[maxn],p2[maxn],cnt1,cnt2;
void work(){
    n=read(); scanf("%s%s",s1+1,s2+1); if(s1[1]!=s2[1]||s1[n]!=s2[n]){ puts("-1"); return; }
    int i; cnt1=cnt2=0; ans=0;
    for(i=2;i<=n;i++) if(s1[i]!=s1[i-1]) p1[++cnt1]=i;
    for(i=2;i<=n;i++) if(s2[i]!=s2[i-1]) p2[++cnt2]=i;
    if(cnt1!=cnt2){ puts("-1"); return; }
    for(i=1;i<=cnt1;i++) ans+=mabs(p1[i]-p2[i]);
    print(ans),pc('\n');
}