Mark and Lightbulbs（思维）

Codeforces Round #807 (Div. 2)

Problem

给出两个长度为n的01字符串s和t。s可以执行以下操作：

• 选择一个下标 $i$, 满足： $s[i-1]\ne s[i+1]$
• 使 $s[i]=s[i]\oplus 1$

问：最小需要多少次该操作，才能把s变成t？

Solution

这题挺考研观察力的。

1. 题目中的操作序列长度为3，总共有4种：001，011，100，110
   $001\to 011,011\to 001,100\to 110,110\to 100$
   该操作可以用语言描述为：选择三个首尾不同的连续字符: 将中间位取反。
2. 这些连续字符，中间位要么与左边相同，要么与右边相同。
   所以，上面的四种操作可以归结成为两种：
   $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$
   熟悉地换成异或操作后就是：
   $01\to 10$
   $10\to 01$
3. 此时便豁然开朗了一丢丢
4. $令a=(s_1\oplus s_2)(s_2\oplus s_3)...(s_{n-1}\oplus s_n)$， t同理，假设为b
   举个例子：
   $s=000101\to a=00111$
   $t=010011\to b=11010$
   那么现在问题便转化成：使用上面的两种操作（$01\to 10$，$10\to 01$）将a转化为b，最少需要多少次操作。
   那么结果显而易见：最小操作数就是将a中对应的1移动到b中对应的位置所有操作的和。
   简单的说就是：所有对应的1的下标之差求和即为结果。（不懂可以看代码）
5. 无解的情况：
   • a和b中1的数量不同
   • $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;
}