[C++知识库]C. Menorah

题意

用两个01序列代表一串蜡烛的的亮灭情况.每次可以选择一个亮着的蜡烛,保持它的状态,对其他位置进行取反,问第一个序列变为第二个序列的最小步数.

题解

官方：
First, let’s define the “type” of a candle i to be the string aibi. For example, if a candle is currently unlit and must be lit in the end, its type is 01. It’s useful to think about the number of candles of each type because the position of a candle is irrelevant in this problem.

Now, let’s consider what happens when we do two operations consecutively. All candles except the ones we select will flip twice, so let’s focus on what happens to the candles we select. If we select the same candle twice, nothing changes. And if we select two different candles, it’s equivalent to swapping a 1 and a 0 in the string.

Since we have a really nice description of two consecutive operations, any sequence of an even number of operations is just a sequence of swaps. So it’s possible in an even number of operations as long as the number of 1’s in both strings is the same, and the minimum number of operations will be the number of positions where the strings differ.

Now, what about an odd number of operations? Well, it’s the same as performing one operation and then reducing it to the case of an even number of operations. There are two types of candles we can select on the first operation: type 10 and type 11. Simply try both options if they’re present, and find the minimum number of operations after it’s reduced to the even case.

Finally, there are some strings where it’s possible to do in either an even or an odd number of operations, so in those cases we have to take the minimum of both options. The total complexity is O(n).
个人：
首先考虑进行偶数次操作序列1能变成序列2，如果对于同一个蜡烛操作两次，序列将不会变化，如果选择不同的蜡烛操作两次，可以知道对于这两个蜡烛以外的所有蜡烛状态不变，且这两个蜡烛的状态互相调换，即原先为0变为1，原先为1变为0，即交换两个蜡烛的状态，那么现在的问题就变为，一个01序列在每次可以选择 两个数字交换能不能变成另外一个01序列，这样我们就分析出只有两个01串的0与1数目相同才可以互相转换，那么需要调换的次数就是不同的位置/2（每次将一组变为正确的位置）每次又需要2次操作即答案为不同的位置的数量。同样的对于奇数次操作可以把序列1变为序列2来说，操作一次后变成偶数次的情况，那么我们选择序列1选择任意一个1取反，要满足01的个数相同，所以原序列1的0比原序列2的1少一个，同样的，操作次数为变化后的不同位置。

#include<bits/stdc++.h>
using namespace std;
void solve()
{   
	int n,oa=0,ob=0,dif=0;
	cin >> n;
	string a, b;
	cin >> a >> b;
	for (int i = 0; i < n; i++)
	{
		oa += a[i] - '0', ob += b[i] - '0', dif += a[i] != b[i];//统计序列1、2的1的个数并且统计不同位置
	}
	int A = 1e9;
	if (oa == ob)A = dif;//1的个数相同自然0的个数也相同答案可以为dif
	if ((n - oa) == ob - 1)A =min(A, n - dif);//将ob操作一次，ob-1是翻转后序列b拥有1的个数 n-oa为操作序列1的个数，答案为不同的位置即为原来的n-dif，原先不同的都变相同，原先相同的都变不同
	cout << (A == 1e9 ? -1 : A )<<endl;

}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
}