2018ACM青岛 C题

题目链接ZOJ-4060

</br>

题目描述


</br>

思路

此题,我们统计异或后 0 和 1 的数量;


我们要做的就是处理异或后的结果, 也就是对异或后的结果取两个区间进行异或操作,使得最后的序列全为0,问这样的方法有多少种;

化简了问题后,我们分类讨论。
我们用ans_0 记录异或后结果为0的数量, ans_1记录异或后结果为1的数量;

当 ans_0 == len

代表着异或后结果全为0;

我们写一个列子看看

红线代表第一次所取的区间 , 黑线代表第二次所取的区间;

此时为区间长度为 1 时 此时的种类数 为 len

此时为区间长度为 2 时 此时的种类数 为 len - 1

不难得到规律, 异或后结果全为 0 时.
总得方案数量 = (1 + len) * len / 2;

当 ans_1 = len 时

此时代表着异或后的结果全为1;

我们来看一个例子;

红线代表第一次所取的区间 , 黑线代表第二次所取的区间;


显然 我们得到的方案数是 len - 1, 考虑到 上下区间可以交换,
所以。该种情况下, 我们得到的方法数 = (len - 1) * 2

当0存在于两个1中间 此时是无解的


此种情况下就是无解的;

当两边是0, 中间夹着全是1的情况下


我们分两部分考虑
1.忽略两侧的0, 此时与情况2完全一致, 结果为(ans_1 - 1) * 2
2.考虑两侧的0, 此时为 (cnt_l + cnt_r) * 2
所以总得结果就是两种情况求和
[ans_1 - 1] 乘以 2 + [cnt_l + cnt_r] 乘以 2

当两边是1, 中间夹着全是0的情况下


这种情况无论咋样结果都是6,直接输出即可;

剩下的一般情况


正常的中间夹着一个0 或者连续的0 结果都是6,直接输出即可;

讨论完毕

我们只需要按着讨论结果,进行相应的输出即可ac;

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define MAX_N 1000010

char s_1[MAX_N], s_2[MAX_N];

int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int len, ans_0 = 0, ans_1 = 0;// ans_0 统计异或为0 ans_1 统计异或为1
scanf("%d %s %s", &len, s_1, s_2);
vector<int> a;
for(int i = 0; i<len; i++)
{
if(s_1[i] == s_2[i])
{
a.push_back(0);
ans_0++;
}
else
{
a.push_back(1);
ans_1++;
}
}
if(ans_0 == len) // 异或结果全为0
{
printf("%d\n", (len + 1) * len / 2 );
}
else if(ans_1 == len)// 异或结果全为1
{
printf("%d\n", (len - 1) * 2);
}
else
{
int flag = 0, cnt_m = 0, cnt_l = 0, cnt_r = 0;
for(int i = 0; i<a.size(); i++)
{
if(flag == 0)
{
if(a[i] == 1)
flag = 1;
}
else
{
if(a[i] == 1)
{
if(cnt_m != 0)
break;
}
else
{
cnt_m++;
}
}
}
for(int i = 0; i<a.size(); i++)
{
if(a[i] == 1)
break;
else
cnt_l++;
}
for(int i = a.size() - 1; i >= 0; i--)
{
if(a[i] == 1)
break;
else
cnt_r++;
}
if(cnt_l + cnt_r == ans_0)
{
cnt_m = 0;
}
if(cnt_l + cnt_r + cnt_m != ans_0)
{
printf("0\n");
}
else if(cnt_l + cnt_r == ans_0)
{
printf("%d\n", (ans_1 - 1) * 2 + (cnt_l + cnt_r) * 2);
}
else if(cnt_m == ans_0)
{
printf("6\n");
}
else
{
printf("6\n");
}
}
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------