这是一道蓝题（我自己都没想到这题我能过），下面是我的解题思路：
首先读题，有 222 个长度为 nnn 的二进制字符串 s,ts,ts,t，每次选择 sss 的一个长度至少为 222 的回文区间，将其按位翻转，直到 sss 和 ttt 相等，需要求出最少的翻转次数。
乍一看题面，首先想到的是动态规划或者是用图论解法，但把所有状态枚举出来时间复杂度太大了，远远超出了 O(n2)O(n^2)O(n2) 的上限。那就先不管那么多，直接上贪心，至少不会超时。
贪心算法：枚举 111 ~ n−2n-2n−2 中的每一个 iii，每次我们需要保证对于任意一个 j∈[1,i]j\in[1,i]j∈[1,i]，sj=tjs_j=t_jsj =tj 成立，换句话说，就是让 iii 从 111 走到 n−2n-2n−2，当发现 si≠tis_i≠t_isi =ti 时，就通过回文翻转使得 si=tis_i=t_isi =ti ，这样我们就保证了 s,ts,ts,t 在 [1,i][1,i][1,i] 区间内的子串是相等的。
那么具体该如何翻转呢？根据贪心思路，我们首先找到一个最大的 ppp，满足对于任意一个 j∈[i,p]j\in[i,p]j∈[i,p]，sj≠tjs_j≠t_jsj =tj 成立，换句话说，就是我们想要找到一个最长的区间 [i,p][i,p][i,p]，使得 s,ts,ts,t 在该区间内的每一个字符都不一样；然后再找一个最大的 qqq，满足 i<q≤pi<q≤pi<q≤p 且 s[i,q]s[i,q]s[i,q] 是个回文串，这样一来，翻转一遍 s[i,q]s[i,q]s[i,q]，我们就使得最开始的要求 si=tis_i=t_isi =ti 满足。
我们现在需要快速判断 sss 的一个子串是否是回文串，很容易想到预处理，定义一个二维数组 zzz，zi,jz_{i,j}zi,j 的值表示 t[i,j]t[i,j]t[i,j] 是否为回文串，这里只需要考虑字符串 ttt 就行了，因为根据我们先前对 qqq 的求法，如果 t[i,q]t[i,q]t[i,q] 是回文串，那么 s[i,q]s[i,q]s[i,q] 必然也是回文串，反之亦然；先令所有的 zi,i=1z_{i,i}=1zi,i =1 以及满足 ti=ti+1t_i=t_{i+1}ti =ti+1 的 zi,i+1=1z_{i,i+1}=1zi,i+1 =1，然后从 333
开始枚举长度，如果 ti+1=tj−1t_{i+1}=t_{j-1}ti+1 =tj−1 ，那么就令 zi,j=zi+1,j−1z_{i,j}=z_{i+1,j-1}zi,j =zi+1,j−1 ，这样我们后续就能 O(1)O(1)O(1) 判断 s[i,q]s[i,q]s[i,q] 是否为回文串。
这里会涉及到一种特殊情况，如果说找不出满足条件的 qqq，那么就令 qqq 为满足大于 iii 且 si=sqs_i=s_qsi =sq 的最小值，如此一来我们能够保证 s[i,q]s[i,q]s[i,q] 一定是回文串，因为夹在 iii 和 qqq 之间的字符都不等于 sis_isi ，翻转 s[i,q]s[i,q]s[i,q]，又使得 si=tis_i=t_isi =ti 满足；但还可能，iii 后面的所有字符都不等于 sis_isi ，这时我们可以确定 s[i+1,n]s[i+1,n]s[i+1,n] 一定是回文串，翻转 s[i+1,n]s[i+1,n]s[i+1,n]，再回到最开始的找
p,qp,qp,q 的步骤。
讲到这，我们终于完成了字符串 sss 前 n−2n-2n−2 个字符的翻转，但是我们仍然需要处理 sss 的最后 222 位字符；这里我用了 132132132 行的分类讨论来处理，大家凑合着看吧，当时我写这段代码的时候，用了整整 222 页草稿纸才把所有情况捋清楚，毕竟最后 222 个字符的归位要涉及到最后 444 个字符的值，像在玩烧脑的 444 位翻转游戏一样，代码里全是 if−elseif-elseif−else 分支。
最后判断 ansansans 是否大于 2n2n2n，然后输出即可，参考代码如下：
