Codeforces Round #807 (Div. 2) - D. Mark and Lightbulbs

思维

Problem - D - Codeforces

题意

给两个长度为 \(n(3<=n<=2*10^5)\) 的 01 串 s 与 t，求最小操作次数，使 s 变成 t；不存在则输出 -1

操作为：对于 2 <= i <= n - 1, 若 \(s_{i-1}\neq s_{i+1}\), 则 \(s_i\) 反转

思路

1. 这种思维题一半需要从操作的特殊性质、操作前后序列的不变性入手
2. 分析各种操作，一共有 4 种
   1. 001 -> 011
   2. 011 -> 001
   3. 100 -> 110
   4. 110 -> 100
3. 位置 1 和 n 永远不会改变，所有若 \(s_1\neq t_1或s_n\neq t_n\) 则返回 -1
4. 这里可能需要经验或者灵机一动了，反正我是想不出来。。。

​ 令 \(a_i=s_i \oplus s_{i+1}\), 记 \(ss_i\)为 s 的特征数组，上述 4 种操作只有两种情况，即 01 -> 10 与 10 -> 01

​ 类似地，求出 t 的特征数组 \(tt_i\), 当且仅当 ss 与 tt 中的 1 数目相同时有解

5. 因为 \(s_1=t_1\), 若两个特征数组相等，则 s == t, 所以把 s 变成 t 等价于 把 ss 变为 tt

6. 把 ss 中的 1 的位置记到 a 数组中，tt 中 1 的位置记到 b 数组中

7. 每次操作可看作是 a 中的 1 在向左或右移动，但永远无法跨过另一个1，因此 a 中的 1 与 b 中的 1 是一一对应的

操作数为 \(\sum abs(a_i-b_i)\)

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
#define endl "\n"

typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 10;
int n;
string s, t;


ll solve()
{
	if (s[1] != t[1] || s[n] != t[n])
		return -1;
	vector<int> a, b;
	for (int i = 1; i < n; i++)
	{
		if (abs(s[i+1] - s[i]) == 1)
			a.push_back(i);
		if (abs(t[i+1] - t[i]) == 1)
			b.push_back(i);
	}
	if (a.size() != b.size())
		return -1;
	ll ans = 0;
	for (int i = 0; i < a.size(); i++)
		ans += abs(a[i] - b[i]);
	return ans;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		cin >> s >> t;
		s = " " + s, t = " " + t;
		cout << solve() << endl;
	}
    return 0;
}