比较简单的贪心
首先按照\(t_1,t_2\)中连续的\(1\)将其分成若干段。以样例为例，\(t_1=111010\)，那么第一段是\(s_1[1\sim3]\)，第二段是\(s_1[5]\)；\(t_2=101101\)，那么第三段是\(s_2[1]\)，第四段是\(s_2[3\sim4]\)，第五段是\(s_2[6]\).同时统计每一段中，\(s_1(s_2)\)的\(1\)和\(0\)的数量
然后可以知道，如果对一个位置\(i\)，有\(t_1[i]=t_2[i]=0\)，那么答案是可以直接统计的（若\(s_1[i]=s_2[i]\)则答案加一，否则答案不变）；若\(t_1[i]+t_2[i]=1\)则我们尽量匹配（比如\(t_1=1,t_2=0,s_2[i]=0\)，那么考虑\(i\)所在的段剩下的\(0\)的个数，如果还有剩下的\(0\)，那么将这个\(0\)与\(s_2[i]\)进行匹配，并将\(i\)所属的这个段的\(0\)的个数减一）；在优先考虑完所有的\(t_1[i]+t_2[i]=1\)的位置后，再考虑\(t_1[i]+t_2[i]=2\)的位置\(i\)，随意将剩下的\(0/1\)进行匹配即可
上述做法的正确性可以用决策包容性证明。简单来说，就是任意一个位置对答案的贡献只有\(1\)，上面的做法，我们在分配任意一个\(0/1\)的时候，都保证了这个\(0/1\)对答案的贡献增加了一。如果我们不把这个\(0/1\)分配到这个位置，分配到其他位置的贡献也是一，等价于就放在这个位置
标签：那么,匹配,位置,编辑,这个,答案,字符串,NOIP2024 From： https://www.cnblogs.com/dingxingdi/p/18678980