2018年ACM-ICPC青岛区域赛 C题 Flippy Sequence

本文主要是介绍2018年ACM-ICPC青岛区域赛 C题 Flippy Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接-浙大oj
Sample Input
3
1
1
0
2
00
11
5
01010
00111
Sample Output
0
2
6
Hint
For the second sample test case, there are two valid operation pairs: (1, 1, 2, 2) and (2, 2, 1, 1).

For the third sample test case, there are six valid operation pairs: (2, 3, 5, 5), (5, 5, 2, 3), (2, 5, 4, 4), (4, 4, 2, 5), (2, 4, 4, 5) and (4, 5, 2, 4).
题意：
T 组测试用例
字符串长度 N
两个二进制01字符串A、B
分别对AB字符串进行一次反转操作（0变1，1变0，可反转一段区间）
通过两次反转操作，使得AB相等
问有多少种方法

例：01010 和 00111
方法1： (2, 3, 5, 5)
A区间 [2,3] 反转 => 00110
B区间 [5,5] 反转 => 00110
思路：
分类讨论
把字符串分为相同段和不同段

无不同段（全相同）：两次操作需反转同一区间方法数：n*(n+1)/2
一段不同：将不同段分割进行两次反转操作，或一次反转操作覆盖不同段和一段相同段，第二次操作再将相同段反转复原，两次区间操作交换顺序，方法数x2：(n-1)*2
两段不同：两段分别操作，或一次操作覆盖两段不同和两段中间的相同段，第二次操作将中间段复原，变更顺序x2 方法数固定为6
多与两段：无法在两次操作完成方法数：0

#include <iostream>
#include <cstdio>
#include <string>using namespace std;string s1,s2;int main()
{ios::sync_with_stdio(false);cout.tie(NULL);int t;cin >>t;while(t--){int n;cin >>n>>s1>>s2;int cnt=0;for(int i=0; i<n; i++){if((i==0||s1[i-1]==s2[i-1])&&s1[i]!=s2[i]){cnt++;}}if(cnt==0)printf("%lld\n",(long long)n*(n+1)/2);else if(cnt==1)printf("%d\n",(n-1)*2);else if(cnt==2)printf("6\n");elseprintf("0\n");}return 0;
}