ZOJ 4060 - Flippy Sequence - [思维题][2018 ACM-ICPC Asia Qingdao Regional Problem C]

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4060

题意：

给出两个 $0,1$ 字符串 $S,T$，现在你有两次对 $S$ 作区间翻转（$0 \rightarrow 1,1 \rightarrow 0$）的操作，

用四元组 $(l_1,r_1,l_2,r_2)$ 表示，代表第一次翻转区间 $[l_1,r_1]$，第二次翻转区间 $[l_2,r_2]$。

问你有多少个四元组可以使得 $S=T$。

题解：

把 $S$ 尽可能少地分割成若干个子串。若某一子串和相应区间的 $T$ 一样，记作 $B$；反之，则记作 $A$。

因此若 $A$ 的数量大于两个，就不可能通过区间翻转两次使得 $S=T$，因此 $A$ 最多是两个。

分类讨论：

$A$ 有 $0$ 个，即整个$S$ 可表示为 $B$，任意翻转两次相同区间 $[i,j]$ 即可。整个 $1 \sim |S|$ 可以有 $|S| + (|S|-1) + \cdots + 1 = \frac{|S|(|S|+1)}{2}$。
$A$ 有 $1$ 个，即$S$ 可表示为 $(B)A(B)$。若两边都没有 $B$，则可以将 $A$ 分成两个部分 $[l,m],[m+1,r]$ 分别翻转，考虑 $m$ 取值的可能有 $2 \times (|A|-1)$ 种；若两侧都有 $B$，即 $BAB$，则应在前面那种基础上，再算上，在某一侧的 $B$ 中挑选一个左端点，再以 $A$ 的右端点为区间右端点，这样一来有 $2 \times |B|$ 种选择。两者加起来即 $2 \times (|A|-1+|B|) = 2 \times (|S|-1)$。
$A$ 有 $2$ 个，即$S$ 可表示为 $(B)ABA(B)$。只能有三种翻法：①ABA,B；②AB,BA；③A,A。因此即 $2 \times 3 = 6$ 种可能性。

AC代码：

#include<bits/stdc++.h>

using namespace std;

int n;

string s,t;

int main()

{

    ios::sync_with_stdio();

    cin.tie();

    int T;

    cin>>T;

    while(T--)

    {

        cin>>n>>s>>t;

        int cnt=;

        for(int i=;i<n;i++) {

            if((i== || s[i-]==t[i-]) && s[i]!=t[i]) cnt++;

        }

        if(cnt>) cout<<"0\n";

        else if(cnt==) cout<<"6\n";

        else if(cnt==) cout<<(*n-)<<'\n';

        else cout<<((long long)n*(n+)/)<<'\n';

    }

}

巴特西

ZOJ 4060 - Flippy Sequence - [思维题][2018 ACM-ICPC Asia Qingdao Regional Problem C]

最新文章

热门文章