C. Menorah(思维+数字反转)

Problem - 1615C - Codeforces

光明节烛台上有n支蜡烛，其中一些蜡烛最初被点燃。我们可以用一个二进制字符串s来描述哪些蜡烛被点燃，其中第i根蜡烛被点燃，当且仅当si=1。

最初，蜡烛的光亮是由一个字符串a描述的。在一个操作中，你选择一个当前被点燃的蜡烛。通过这样做，你选择的蜡烛将保持点亮，而其他每根蜡烛都将发生变化（如果它是点亮的，它将变成不亮，如果它是不亮的，它将变成亮的）。

你的任务是确定这是否可行，如果可行，找出所需的最少操作数。

输入
第一行包含一个整数t（1≤t≤104）--测试案例的数量。接着是t个案例。

每个测试案例的第一行包含一个整数n（1≤n≤105）--蜡烛的数量。

第二行包含一个长度为n的字符串a，由符号0和1组成--灯光的初始模式。

第三行包含一个长度为n的字符串b，由符号0和1组成--期望的灯光模式。

保证n的总和不超过105。

输出
对于每个测试案例，输出将a转化为b所需的最少操作数，如果不可能，则输出-1。

例子
inputCopy
5
5
11010
11010
2
01
11
3
000
101
9
100010111
101101100
9
001011011
011010101
输出拷贝
0
1
-1
3
4
注意
在第一个测试案例中，两个字符串已经相等，所以我们不需要进行任何操作。

在第二个测试案例中，我们可以进行一次操作，选择第二个蜡烛，将01转化为11。

在第三个测试案例中，不可能进行任何操作，因为没有点燃的蜡烛可以选择。

在第四个测试案例中，我们可以执行以下操作，将a转化为b。

选择第7支蜡烛。100010111→011101100.
选择第2根蜡烛。011101100→110010011.
选择第1根蜡烛。110010011→101101100.
在第五个测试案例中，我们可以进行以下操作，将a转化为b。

选择第6根蜡烛。001011011→110101100
选择第2根蜡烛。110101100→011010011
选择第8根蜡烛。011010011→100101110
选择第7根蜡烛。100101110→011010101
题解:
根据题目所给操作我们观察到

如果同一个位置操作一次,当前位置不变,其他位置都会改变

如果操作两次,都不会发生任何变化

如果两个不同的位置操作一次,除这两个位置外的都不会变化

这两个位置的数会发生交换

所以题就变成了交换两个位置的数,是序列1变为2

假如此时位置不同

如果

ai = 1 ai = 0 ai = 0 ai = 1

bi = 0 bi = 1 bi = 1 bi = 0

可以发现如果a与b不同位置的0,1数目相同,0与1的数目必然相同

交换次数为偶数 = 不同位置的数目

如果不同位置为奇数

我们可以先做一次变换

本来为1的位置,除了我们变化的位置,其他均为0,本来为0的位置,全为1

如果此时情况符合刚才我们讨论的情况,就是可以

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
string a,b;
int n,k;
void solve()
{
	int n;
	cin >> n >> a>>b;
	if(a == b)
	{
		cout<<"0\n";
		return ;
	}
	int x1 = 0,x2 = 0,y1 = 0,y2 = 0;
	for(int i = 0;i < n;i++)
	{
		if(a[i] != b[i])
		{
			if(a[i] == '1')
			{
				x1 ++;
			}
			else
			{
				x2++;
			}
		}
		else
		{
			if(a[i] == '1')
			{
				y1++;
			}
			else
			{
				y2++;
			}
		}
	}
	int res = 1e9;
	if(x1 == x2)
	{
		res = min(res ,x1+x2);
	}
	if(y1)
	{
		y1--;
		if(y1 == y2)
		{
			res = min(res ,y1+y2+1);
		}
	}
	if(res == 1e9)
	{
		cout<<"-1\n";
	}
	else
	{
		cout<<res<<"\n";
	}
 
}
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}
 
//1 10 11
 
//001
//010
//011
//100