洛谷 P7993 [USACO21DEC] Lonely Photo B

题目描述

Farmer John 最近购入了 $N$ 头新的奶牛（$3\le N\le 5\times 10^5$），每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。

奶牛目前排成一排，Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。 然而，他不想拍摄这样的照片，其中只有一头牛的品种是更赛牛，或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。 在为每个连续不少于三头奶牛的序列拍摄了一张照片后，他把所有「孤独的」照片，即其中只有一头更赛牛或荷斯坦奶牛的照片，都扔掉了。

给定奶牛的排列方式，请帮助 Farmer John 求出他会扔掉多少张孤独的照片。如果两张照片以不同的奶牛开始或结束，则认为它们是不同的。

分析

首先将相邻的品种相同的牛缩成一块，用 $a_i$ 表示第 $i$ 块的奶牛数量，进行分类讨论：

• 如果 $a_i=1$ 则把他两边的块根据乘法原理算出数量，在减去少于三头奶牛的，代码：

ans += a[i - 1] * a[i + 1] + a[i + 1] - 1;

• 如果 $a_i>1$ 则只考虑他右边的根据乘法原理算出数量，在减去少于三头奶牛的，代码：

ans = ans + a[i] + a[i + 1] - 2;

代码

#include <bits/stdc++.h>
#define debug puts("Y")

using namespace std;

const int N = 5 * 1e5 + 5;
int n, cnt = 1;
long long a[N];
string s;

int main(){
	cin >> n >> s;
	a[cnt] ++;
	for(int i = 1; i < n; i ++){
		if(s[i] == s[i - 1]){
			a[cnt] ++;
		}else{
			cnt ++, a[cnt] ++;
		}
	}
	long long ans = 0;
	for(int i = 1; i < cnt; i ++){
		if(a[i] == 1){
			ans += a[i - 1] * a[i + 1] + a[i + 1] - 1;
		}else{
			ans += a[i] + a[i + 1] - 2;
		}
	}
	cout << ans;
	return 0;
}
/*

*/