2018icpc青岛Flippy Sequence 思维

题意：

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的字符串s1,s2，每个字符串必须且只能反转一个连续的区间（0变1，1变0），问两个字符串反转完毕变成相同字符串的方案数？

思路：

​ 我们把两个字符串每一位相同的设为0，不同的设为1.若出现了3个及3个以上连续的1，那么永远无法通过反转一次得到相同字符串，此时输出0；若出现了2个连续的1，那么一定是6种方案；若出现了1个连续的1，方案数= (连续1的个数 - 1) ✖️ 2 + （n - 连续1的个数) ✖️2；若没有出现连续的1，方案数=（1 + n）✖️ n / 2。

​ 一定要细心细心再细心！！因为细节没处理好WA了4发当时心态都崩了。

代码：

#include <stdio.h>
#define N 1000005
char s1[N], s2[N];
int main () {int T, n, c;scanf("%d", &T);while (T--) {scanf("%d", &n);scanf("%s%s", s1, s2);int num = 0;int flag = 0, flaa = 0;int start, endd;int num1 = 0, num2 = 0, num3 = 0;for (int i = 0; i < n; i++) {if (s1[i] == s2[i]) c = 0;else c = 1;if (c == 0) {if (flag) {num++;if (num == 1) {endd = i - 1;}flag = 0;}if (num == 1) {num2++;}} else {if (num == 0) {if (flag == 0) {start = i;}num1++;} else if(num == 1) {num3++;} else {flaa = 1;break;}if(i == n - 1) {num++;if (num == 1) {endd = i;}}flag = 1;}}if (flaa) {printf("0\n");}else if (num == 0) {long long sum = (long long)(1 + n) * n / 2;printf("%lld\n", sum);}else if (num == 1) {long long sum = (long long)(num1 - 1) * 2;sum += (n - (endd - start + 1)) * 2;printf("%lld\n", sum);} else if (num == 2) {printf("6\n");}}return 0;
}

转载请注明出处！！！

如果有写的不对或者不全面的地方 可通过主页的联系方式进行指正，谢谢