题目描述
Farmer John
最近购入了 $N$ 头新的奶牛,每头奶牛的品种是更赛牛(Guernsey
)或荷斯坦牛(Holstein
)之一。
奶牛目前排成一排,Farmer John
想要为每个连续不少于三头奶牛的序列拍摄一张照片。
然而,他不想拍摄这样的照片,其中只有一头牛的品种是更赛牛,或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。
在为每个连续不少于三头奶牛的序列拍摄了一张照片后,他把所有「孤独的」照片,即其中只有一头更赛牛或荷斯坦奶牛的照片,都扔掉了。
给定奶牛的排列方式,请帮助 Farmer John
求出他会扔掉多少张孤独的照片。
如果两张照片以不同位置的奶牛开始或结束,则认为它们是不同的。
输入格式
输入的第一行包含 $N$。
输入的第二行包含一个长为 $N$ 的字符串。如果队伍中的第 $i$ 头奶牛是更赛牛,则字符串的第 $i$ 个字符为 G
。否则,第 $i$ 头奶牛是荷斯坦牛,该字符为 H
。
输出格式
输出 Farmer John
会扔掉的孤独的照片数量。
数据范围
$3 \le N \le 5 \times 10 ^ 5$
输入样例:
5
GHGHG
输出样例:
3
样例解释
这个例子中的每一个长为 $3$ 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片,并会被 Farmer John
扔掉。
所有更长的子串(GHGH
、HGHG
和 GHGHG
)都可以被接受。
解题思路
输入的原字符串可能会有连续的多段 G
或 H
,所以我们考虑把连续的 G
和 H
缩成一段区间 $[a _ l, a _ r]$。
然后就可以用乘法原理和分类讨论:
- 如果某一段有连续多个
G
或H
,该丢掉的照片的个数为左边 + 右边
, 即len (a[i - 1]) - 1 + len (a[i + 1]) - 1
,$len$ 是区间长度。由于照片要求有 $3$ 头及以上的奶牛,两边要各减去 $1$。 - 如果某一段只有一个
G
或H
,那么我们要分 $3$ 种情况进行讨论: - 当这段区间在最左边时,按照多个的右边计算,即
len (a[i + 1]) - 1
。 - 当这段区间在最右边时,按照多个的左边计算,即
len (a[i - 1]) - 1
。 - 当这段区间在中间是,可以用到乘法原理,即
(len (a[i - 1]) + 1ll) * (len (a[i + 1]) + 1)
,最后还要减去 $3$(区间长度 $< 3$ 的)。
这样我们就完成了统计,最后输出答案即可。
时间复杂度
因为我们用的是数学方法,即每一段的时间都是 $\Theta (1)$。所以最终的时间复杂度为 $\Theta (n)$。
AC Code
#include <iostream>
#define N 500005
using namespace std;
struct node {int l, r;} a[N];
int n, tot;
long long ans;
string s;
int len (node x)
{
return x.r - x.l + 1;
}
int main ()
{
ios :: sync_with_stdio (0), cin.tie (0), cin >> n >> s;
for (int i = 1; i <= n; i ++) // 分隔成区间
{
if (i == 1 || s[i - 1] != s[i - 2])
{
a[++ tot] = {i, i};
}
else
{
a[tot].r = i;
}
}
if (tot == 1) // 特判
{
cout << 0;
return 0;
}
for (int i = 1; i <= tot; i ++) // 统计
{
if (len (a[i]) > 1)
{
ans += len (a[i - 1]) - 1 + len (a[i + 1]) - 1;
}
else
{
if (i == 1)
{
ans += len (a[i + 1]) - 1;
}
else if (i == tot)
{
ans += len (a[i - 1]) - 1;
}
else
{
ans += (len (a[i - 1]) + 1ll) * (len (a[i + 1]) + 1) - 3;
}
}
}
cout << ans;
return 0;
}
感谢观看!
$$\href {/blog/content/29204/} {\color {DarkOrchid} {【寒假每日一题】题解}}$$
此题选自$USACO$