CF1148A Another One Bites The Dust

题目链接

https://www.luogu.org/problemnew/show/CF1148A

题解

这道题其实很简单,意思就是拼一个要求 相邻字符不一样 的字符串,而且要越长越好。

$a$ 就是 a 字符的数量,$b$ 就是 b 字符的数量,$c$ 就是 ab 字符串的数量。

由于 ab 是合规的字符串,先把 $c$ 个 ab 全部拼起来。所以答案至少也会有 $c*2$。

然后我们继续把剩下单独的 ab 拼起来,也就是一个 a 一个 b 地拼。先用 temp 加上 min(a, b),然后答案再加上 $temp*2$。因为最多只可能拼 min(a, b)ab,剩下的只有落单的一个 a 或者 b

到这里就完了吗?其实没有。

我们拿一个样例 2 1 2 来试一下:

  1. 首先把 $c$ 个 ab 全部拼起来,$ans += 2*2$
  2. 继续把剩下单独的 ab 拼起来,$ans += min(a, b) * 2$ 也就是 $ans += 1*2$

到这里,$ans$ 就是 $6$ 了。但是正确的答案是 $8$,为什么呢?

我们来看看,先把 $2$ 个 ab 拼起来,这个字符串就是 abab 了。

然后再加 $1$ 个 a、$1$ 个 b 拼起来,字符串又加了 ab 也就是 ababab 了。

到了这里,$a$ 变量其实还剩下 1 个,$b$ 变量倒是没了。在 ababab 后面其实是还可以加一个 a 的,我们只需要加一个特判就可以解决这个问题。

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
// [CF1148A Another One Bites The Dust] https://www.luogu.org/problemnew/show/CF1148A
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
ios::sync_with_stdio(false); // 加快速度

long long a, b, c, ans = 0;

cin >> a >> b >> c;

long long temp = min(a, b);

ans += c*2;
ans += temp * 2;

a -= temp;
b -= temp;

if (a || b) // 特判
ans++;

cout << ans << endl;
return 0;
}
# 模拟

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×