D1. Zero-One (Easy Version) codeforces 1733D1

90 阅读 0 评论 60 点赞

我是靠谱客的博主俊逸香水，这篇文章主要介绍D1. Zero-One (Easy Version) codeforces 1733D1，现在分享给大家，希望可以做个参考。

Problem - 1733D1 - Codeforces

题目大意：有两个长度为n的仅包含0和1的字符串s1,s2，如果对于同一个位置i，s1[i]!=s2[i],可以选择另一个位置j，将这两个位置上的数取反，如果i和j是相邻的，花费是x，否则花费为y,问要使两个字符串相同，最小花费是多少

5<=n<=3000,1<=y<=x<=1e9

思路：因为每次操作都是两个位置同时取反，所以我们先统计满足s1[i]!=s2[i]的i的数量cnt，如果为奇数，则无法使两个字符串相同,然后只要cnt!=2,那么我们一定可以对每个不匹配的位置都找到一个不相邻的不匹配的位置，两个位置同时取反，消耗为y，最小的花费为cnt/2*y，当cnt=2时，且如果两个不匹配的位置相邻，那么我们可以将这两个位置取反，或者找到另一个位置，使这两个不匹配的位置分别与这个位置取反，最小费用为2y和x的最小值，如果两个不匹配的位置不相邻，最小费用为y

复制代码

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
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;//注意数据范围
int main()
{
int t;
cin >> t;
while (t--)
{
ll n, x, y;
scanf_s("%lld%lld%lld", &n, &x, &y);
string s1, s2;
cin >> s1 >> s2;
ll cnt = 0, cnt2 = 0;
for (int i = 0; i < n; i++)
{
if (s1[i] != s2[i])
{
cnt++;//记录不匹配的位置的数量
}
}
for (int i = 0; i < n; i++)
{
if (i != 0 && s1[i] != s2[i] && s1[i - 1] != s2[i - 1])
{
cnt2++;//记录相邻的不匹配的位置的组数
i++;
}
}
if (cnt & 1)
{//只有奇数个不匹配，直接输出-1
printf("-1n");
continue;
}
ll ans = 0;
if (cnt == 2 && cnt2 == 1)
{//不匹配的有两个且相邻
ans = min(x,2 * y);
}
else
{
ans = cnt/2 * y;
}
printf("%lldn", ans);
}
return 0;
}