ZOJ4060 Flippy Sequence（思维题）

题目链接：传送门

题目大意：

　　两个长度为n的二进制串s，t，每次操作可以将s串的一段区间取反。求操作exactly twice后使得s=t的方法数。

思路：

　　连续的尽可能长的 s_i ≠ t_i 的区间简称A，连续的尽可能长的 s_i = t_i 的区间简称B。

　　则1-n可以划分为若干个AB交替出现，要求操作exactly twice后s=t，就是消去所有的A。

　　发现每次操作最多只能使得A的数量减少1个。

所以若对于给出的s，t：

　　① cnt(A) ≥ 3：

　　　　不能完成，方法数为0。

　　② cnt(A) = 2：

　　　　有2 × 3 = 6种：（下划线表示反转，顺序对调就翻一倍）

　　　　1）ABA + ABA

　　　　2）ABA + ABA

　　　　3）ABA + ABA

　　③ cnt(A) = 1：

　　　　只要第一次操作能使得A的数量还是1即可：

　　　　1）把A分两次翻转，有2 × (len(A)-1)种；

　　　　2）翻转B的一段+A，有2 × (N-len(A))种；

　　④ cnt(A) = 0：

　　　　此时整个1-n为B，任意取一段区间翻两次，有n × (n+1) / 2种。

代码：

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 5;

char s[MAX_N], t[MAX_N];

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int N;
        scanf("%d", &N);
        scanf("%s%s", s+1, t+1);
        int l, r, cntdif = 0;
        for (int i = 1; i <= N; i++) {
            if (s[i] != t[i]) {
                cntdif++;
                if (cntdif == 3)
                    break;
                l = r = i;
                while (i+1 <= N && s[i+1] != t[i+1]) {
                    r++;
                    i++;
                }
            }
        }
        if (cntdif == 3) {
            puts("0");
        }
        else if (cntdif == 2) {
            puts("6");
        }
        else if (cntdif == 1) {
            int len = r-l+1;
            ll ans = 0;
            ans += (len-1)*2;
            ans += (N-len)*2;
            printf("%lld
", ans);
        }
        else if (cntdif == 0) {
            ll ans = 1LL * N * (N+1)/2;
            printf("%lld
", ans);
        }
//        puts("");
    }
    return 0;
}
/*
10
1
1
0
2
00
11
5
01010
00111
3
111
111
7
1010101
1111111
*/