D. Mark and Lightbulbs

The question

Give you two binary strings of the same length s and t, When s[i - 1] != s[i + 1] You can flip s[i], Ask at least how many operations you can make s Flip into t, If not, output -1.

Examination site

thinking

Ideas

• about 0 0 0 1 1 1 1 0 0 0
• We combine the same into a block , namely 0 1 0
• No matter how we operate , The number of blocks does not change .
• So let's calculate s and t Number of blocks for , If the number of blocks is different , It's not feasible .
• If possible , The contribution of each block is the absolute value of the subscript difference of the left endpoint of the block

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;
char s[N], t[N];
int n;
void solve(){
    
	scanf("%d",&n);
	scanf("%s", s + 1);
	scanf("%s", t + 1);
	vector<int>a, b;
	for(int i = 1; i <= n; i ++ ){
    
		if(s[i] != s[i - 1]) a.push_back(i);
		if(t[i] != t[i - 1]) b.push_back(i);
	}
	if(s[1] != t[1] || s[n] != t[n] || a.size() != b.size()) puts("-1");
	else{
    
		long long ans = 0;
		int len = a.size();
		for(int i = 0; i < len; i ++ ) ans += abs(a[i] - b[i]);
		printf("%lld\n", ans);
	}
}
int main(){
    
	int tt;
	scanf("%d",&tt);
	while(tt -- ){
    
		solve();
	}
	return 0;
}