2018年ACM-ICPC亚洲青岛区域竞赛 - C:Flippy Sequence
Whiteying
2018-11-13 00:31:09
# C类
# 题目链接：
https://vjudge.net/problem/ZOJ-4060
# 题意：
给你A,B两串二进制数，然后问你有多少种情况，A串翻转两次等于B串 。
翻转的意思是将一段区间内的二进制数，0变为1，1变为0.
# 思路：
定义一个布尔数组C为串A,B是否在i处相等。
首先判断有几个连续区间不相等。
1.当两个串相等的时候,则我们可以在C上随意找到一个区间,对这个区间进行两次反转后还是0串,这样的区间共有n*(n+1)/2个,则共有n*(n+1)/2种方法.
2.当两个串有1个连续区间不相等（设此不相等区间长度为k），对于翻转全在不相等的区间内进行时，共有(k-1)*2 种方法，对于翻转包含不相等区间时，共有(n-k)*2种方法， 因此共有(n-1)*2种方法
3.当两个串有2个连续区间不相等。发现两次操作只要第一次改变一个区间,第二次改变另一个区间就可以把这个串变成0串.当我们单独的操作为1的,不改变0,则有1种方法.当我们两次操作都把中间的0也改变的时候,又有1种方法.当我们第一次操作把两个区间一次全部反转,第二次操作再把中间的0改变过来,又是1种方法.类似于上面,上述操作换一下顺序也是可以的,故这种类型的共有3*2=6种方法.
4.当两个串有3个及以上连续区间不相等,没有任何方法使它变成0串,故有0种方法.
## 因此：
两个串一样: 共有n*(n+1)/2种方法;
一个区间不一样: 共有(n-1)*2种方法;
两个区间不一样: 6种方法;
三个及三个以上: 0种方法.
# AC代码：
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int t,n;
char a[1000006];
char b[1000006];
bool c[1000006];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
scanf("%s",a);
scanf("%s",b);
for(int i=0; i<n; i++)
{
if(a[i]==b[i])
c[i]=false;
else
c[i]=true;
}
int cnt=0;
if(c[0])
cnt++;
for(int i=1; i<n; i++)
if(c[i]&&!c[i-1])
cnt++;
if(cnt==0)
printf("%d\n",((n*(n+1))/2));
else if(cnt==1)
printf("%d\n",(((n-1)*2)));
else if(cnt==2)
printf("6\n");
else
printf("0\n");
}
return 0;
}
```