ACM 2018 青岛区域赛 C-Flippy Sequence（模拟 思维 分类讨论）

ZOJ - 4060 

题目大意：

       给出2个长度为n的01串s和t，对s进行两次操作，每次操作选择s串的一段区间，将区间内的数字0变成1,1变成0，问将s变为t一共有多少种方法

题解：

      先统计一下s和t有几段不相同的区间num

      ①num>=3,无解，没法s经过两次从操作变为t，方法数为0

      ②num=2，固定为6种

      ③num=1，

可以先反转a+b，再反转a；先反转b+c，再反转c；b内部分成两半反转

      ④num=0，即全都相同，这时候就可以把整个串分为两半反转,方法数为 

#include<bits/stdc++.h>
#include<cstring>
#define ll long long
using namespace std;
char s1[1000010],s2[1000010];
int main()
{int T;scanf("%d",&T);int n;while(T--){scanf("%d",&n);getchar();scanf("%s",s1);getchar();scanf("%s",s2);int i=0;vector<pair<int,int> >seg;int pre=-1;while(i<n){pre=i;if(s1[i]!=s2[i]){while(s1[i]!=s2[i] && i<n)++i;if(i<n || (i==n && s1[n-1]!=s2[n-1]))seg.push_back(make_pair(pre,i));}++i;}int num=seg.size();ll ans=0;if(num>=3)ans=0;else if(num==1)ans=2*(seg[0].first+(n-seg[0].second)+seg[0].second-seg[0].first-1);else if(num==0)ans=(ll)n*(n+1)/2;else   //num==2ans=6;printf("%lld\n",ans);}return 0;
}