2018年ACM-ICPC亚洲青岛区域竞赛 - C:Flippy Sequence

http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5830

Time Limit: 1 Second      Memory Limit: 65536 KB

Problem solving report:

Description: 给出A和B两个01串,通过两次反转使得A串变成B串,问有多少种方法(这个反转指的是连续的一段区间)

Problem solving: 分类讨论:

我们可以先定义一个数组利用异或来判断两个串是否相等,例如串A:010100和串B:001110,异或后得串C:011010,我们只要把这个串C变成全为0(即000000),即可判定两串相等。

首先我们可以判断有几个连续区间不相等时(即串C有几个连续为1的),例如:011010就有两个连续为1的.

1. 当两个串相等的时候(即串C全为0),则我们可以在串C上随意找到一个区间,对这个区间进行两次反转后还是0串,这样的区间共有n*(n+1)/2个,则共有n*(n+1)/2种方法.

2. 当两个串有1个连续区间不相等(即串C有1个连续为1的),例如:000111、011100、111000.我们可以把这种有1个连续为1的串看成x(0个数)y(1的个数)z(0个数),假设串C为:011100,则(011100:132).当我们把前面的0也改变的时候共有x种方法:我们可以改变1~4和1~1即(1,4,1,1).当我们把后面的0也改变的时候共有z种方法:我们可以改变2~5和5~5即(2,5,5,5),也可以改变2~6和5~6即(2,6,5,6),即可把串C变为0串.当我们不改变0的时候共有y-1种方法:改变2~2和3~4即(2,2,3,4),改变2~3和4~4即(2,3,4,4),就是把y个1分成两个区间共有y-1种方法,上述操作换一下顺序也是可以的,即改变1~4和1~1和改变1~1和1~4是一样的,但这是两种操作,故是该串C变为0串共有(x+y-1+z)*2=(n-1)*2=10种方法.

3. 当两个串有2个连续区间不相等(即串C有2个连续为1的),例如:010111、010100、111010.我们很容易发现两次操作只要第一次改变一个区间,第二次改变另一个区间就可以把这个串变成0串.当我们单独的操作为1的,不改变0,则有1种方法.当我们两次操作都把中间的0也改变的时候,又有1种方法.当我们第一次操作把两个区间一次全部反转,第二次操作再把中间的0改变过来,又是1种方法.类似于上面,上述操作换一下顺序也是可以的,故这种类型的共有3*2=6种方法.

4. 当两个串有3个及以上连续区间不相等(即串C有3个及以上连续为1的),例如:010101、1010101、101010.我们很容易发现,我们没有任何方法使它变成0串,故有0种方法.

综上:

两个串一样: 共有n*(n+1)/2种方法;
一个区间不一样: 共有(n-1)*2种方法;
两个区间不一样: 6种方法;
三个及三个以上: 0种方法.

#include <stdio.h>
#define N 1000020
int c[N];
char a[N], b[N];
int main()
{int t, n, temp;scanf("%d", &t);while (t--){temp = 0;scanf("%d", &n);scanf("%s%s", a, b);for (int i = 0; i < n; i++)c[i] = (a[i] - '0') ^ (b[i] - '0');if (c[0])temp++;for (int i = 1; i < n && temp <= 2; i++)if (c[i] && !c[i - 1])temp++;if (!temp)printf("%d\n", n * (n + 1) / 2);else if(temp == 1)printf("%d\n", (n - 1) * 2);else if (temp == 2)printf("6\n");else printf("0\n");}return 0;
}