CF1705D-Mark and Lightbulbs
题目大意：给定两个仅由01组成的字符串s, t。可以对s做出如下“操作”：取s中一个左右两边的字符互不相同的字符，将该字符翻转。问至少需要对s进行多少次“操作”可以将s变为t。如果不能变则输出-1。
首先，s的第一个字符跟最后一个字符都不能改变，需要与t对应位置的字符相等。
注意到：不论如何进行操作，s中为01、10的子串的数目总是不变的。所以t首先需要满足01、10子串的数目跟s中的相等。通过试验可以发现，通过对相邻字符的连续操作可以实现把01、10子串移动到想要的位置，需要的操作次数为原位置与目标位置的位值之差。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
#define int long long
using namespace std;
char s[200005], t[200005];
int as[200005], at[200005];
signed main()
{
int _, n, i, j;
scanf("%lld", &_);
while (_--)
{
scanf("%lld", &n);
scanf("%s%s", s + 1, t + 1);
if (s[1] != t[1] || s[n] != t[n])
{
printf("-1\n");
continue;
}
int sums = 0, sumt = 0;
for (i = 1; i < n; i++)
{
as[i] = (s[i] != s[i + 1]);
at[i] = (t[i] != t[i + 1]);
sums += as[i];
sumt += at[i];
}
if (sums != sumt)
{
printf("-1\n");
continue;
}
int res = 0;
for (i = j = 1; i < n; i++)
{
if (at[i])
{
for (;; j++)
{
if (as[j])
break;
}
res += llabs(j - i);
j++;
}
}
printf("%lld\n", res);
}
return 0;
}
|