P10766 「CROI · R2」01-string

给定两个长度为 $n$ 的 $01$ 串 $S,T$，你可以对串 $S$ 执行无限次操作，每次都可以从以下操作中任选一个执行： - 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r \ 01$ 反转。 - 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r $ 全部改为 $0$。 - 选择两个正整数 $l,r(1\le l\le r\le n)$，将 $S_l\dots S_r $ 全部改为 $1$。 你需要回答最少使用几次操作才能把 $S$ 变成 $T$。

无

无

**【样例解释】** 以下提供样例三组数据的合法方案之一： 对于第一组数据，选取 $l=1,r=5$，将 $S_l\dots S_r$ 全部变成 $1$。 对于第二组数据，选取 $l=1,r=5$，将 $S_l\dots S_r \ 01$ 反转。 对于第三组数据，先选取 $l=4,r=8$，将 $S_l\dots S_r$ $01$ 反转，再选取 $l=5,r=8$，将 $S_l\dots S_r$ 全部变成 $0$。 **【数据范围】** **本题采用捆绑测试**。 - Sub 0（10 points）：$n\le 5$。 - Sub 1（10 points）：$n\le 18$。 - Sub 2（30 points）：$n\le 2000$。 - Sub 3（50 points）：无特殊限制。 对于所有的数据，$1\le T \le 10$，$1\le n\le 5\times 10^5$。