Mark and lightbulbs (thinking)

Codeforces Round #807 (Div. 2)

Problem

Give two lengths of n Of 01 character string s and t.s You can do the following ：

• Select a subscript $i$, Satisfy ： $s[i-1]\ne s[i+1]$
• send $s[i]=s[i]\oplus 1$

ask ： How many times is the minimum required for this operation , To put s become t？

Solution

This question is quite observant in the postgraduate entrance examination .

1. The length of the operation sequence in the title is 3, All in all 4 Kind of ：001,011,100,110
   $001\to 011,011\to 001,100\to 110,110\to 100$
   This operation can be described as ： Select three consecutive characters with different beginning and end : Reverse the middle position .
2. These consecutive characters , The middle position is either the same as the left , Or the same as the right .
   therefore , The above four operations can be summed up into two ：
   $s=s_1{s}_2{s}_3$
   $s_1=s_2,s_2\ne s_3\to s_1\ne s_2,s_2=s_3$
   $s_1\ne s_2,s_2=s_3\to s_1=s_2,s_2\ne s_3$
   After the familiar XOR operation is ：
   $01\to 10$
   $10\to 01$
3. At this time, it suddenly became clear... DIU DIU
4. $Makea=(s_1\oplus s_2)(s_2\oplus s_3)...(s_{n-1}\oplus s_n)$, t Empathy , Assuming that b
   for instance ：
   $s=000101\to a=00111$
   $t=010011\to b=11010$
   Now the problem turns into ： Use the above two operations （$01\to 10$,$10\to 01$） take a Turn into b, The minimum number of operations required .
   Then the result is obvious ： The minimum operand is to a Corresponding 1 Move to b The sum of all operations at the corresponding position in .
   Simply put ： All the corresponding 1 The sum of the differences of subscripts of is the result .（ If you don't understand, you can read the code ）
5. There is no solution ：
   • a and b in 1 The number of different
   • $s[0]\ne t[0]$
   • $s[n-1]\ne t[n-1]$

Code

const int N = 2e5 + 5, M = 1e6 + 7;

int a[N], b[N];

int main()
{
    
	IOS;
	int T; cin >> T;
	while (T--)
	{
    
		int n; cin >> n;
		string s, t; cin >> s >> t;
		if (s[0] != t[0] || s[n - 1] != t[n - 1])
		{
    
			cout << "-1\n";
			continue;
		}

		int cnt1 = 0, cnt2 = 0;
		for (int i = 1; i <= n - 1; i++)
		{
    
			a[i] = s[i] != s[i - 1];
			b[i] = t[i] != t[i - 1];
			cnt1 += a[i];
			cnt2 += b[i];
		}

		if (cnt1 != cnt2)
		{
    
			cout << "-1\n";
			continue;
		}

		ll ans = 0;
		int r = 1;
		for (int i = 1; i <= n - 1; i++)
			if (a[i])
			{
    
				while (r <= n - 2 && b[r] == 0) r++;
				ans += abs(i - r);
				r++;
			}
		cout << ans << endl;
	}


	return 0;
}