CF1615C-Menorah
题目大意：给出一个全由0与1组成的数列a，每次操作可以选择一个值为1的元素，让这个元素的值保持不变，其它元素取异或。给出一个数列b，问是否可以将数列a变成数列b，如果可以，输出最少需要的操作次数。
注意到：对一个元素x进行操作之后紧接着对另一个元素y进行操作，结果就是交换了x和y的值，数列中其它数保持不变。结果实际上就是经过这些交换得到的。判断需要从0变成1的数的数量是否等于需要从1变成0的数的数量就可以了。
在开始交换前，可以先取一个保持为1不变的元素，对它进行一次操作，将整个数列反转一遍，判断翻转后的数列中需要从0变成1的数的数量是否等于需要从1变成0的数的数量，即原数列中需要保持1不变的数的数量减去1之后和保持0不变的数的数量是否相等。应该比较两种方法所需操作次数，取较小的。
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
| #include <bits/stdc++.h>
using namespace std;
int sum[2][2];
char a[100005], b[100005];
int main()
{
int n, i, _, res;
scanf("%d", &_);
while (_--)
{
scanf("%d%s%s", &n, a + 1, b + 1);
memset(sum, 0, sizeof(sum));
for (i = 1; i <= n; i++)
sum[a[i] - '0'][b[i] - '0']++;
if (sum[0][1] != sum[1][0] && sum[1][1] - sum[0][0] != 1)
printf("-1\n");
else
{
res = 1e9;
if (sum[0][1] == sum[1][0])
res = sum[0][1] * 2;
if (sum[1][1] - sum[0][0] == 1)
res = min(res, 1 + sum[0][0] * 2);
printf("%d\n", res);
}
}
return 0;
}
|