【寒假每日一题】AcWing 4261. 孤独的照片(补)

简介: 文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解

一、题目

1、原题链接

4261. 孤独的照片


2、题目描述

Farmer John 最近购入了 N 头新的奶牛,每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。

奶牛目前排成一排,Farmer John 想要为 每个连续不少于三头奶牛 的序列拍摄一张照片。

然而,他不想拍摄这样的照片,其中只有一头牛的品种是更赛牛,或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。

在为每个连续不少于三头奶牛的序列拍摄了一张照片后,他把所有「孤独的」照片,即其中只有一头更赛牛或荷斯坦奶牛的照片,都扔掉了。

给定奶牛的排列方式,请帮助 Farmer John 求出他会扔掉多少张孤独的照片。

如果两张照片以不同位置的奶牛开始或结束,则认为它们是不同的。


输入格式

输入的第一行包含 N。

输入的第二行包含一个长为 N 的字符串。如果队伍中的第 i 头奶牛是更赛牛,则字符串的第 i 个字符为 G。否则,第 i 头奶牛是荷斯坦牛,该字符为 H。


输出格式

输出 Farmer John 会扔掉的孤独的照片数量。


数据范围

3≤N≤5×105


输入样例:

5

GHGHG

1

2


输出样例:

3

1


样例解释

这个例子中的每一个长为 3

的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片,并会被 Farmer John 扔掉。

所有更长的子串(GHGH、HGHG 和 GHGHG)都可以被接受。


二、解题报告

1、思路分析

思路来源:AcWing 4261. 孤独的照片(寒假每日一题2023)

y总yyds

(1)枚举每个字母作为只出现一次的字母。

(2)因为照片中要至少3头奶牛,所以针对每种情况:如果该字母为G则它左边需要有至少两个H或右边至少有两个H或左边和右边都至少有一个H;该字母若为H,与上述情况一致,只是左边或右边需要的字母为G。

(3)枚举每个字母,统计左边和右边的连续的G或H的数量,来分别计算符合上述情况的结果数,即为答案。

2、时间复杂度

时间复杂度为O(n)


3、代码详解

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

typedef long long LL;

const int N=500010;

int l[N],r[N];  //l[]、r[]分别统计字母左边、右边连续的G或H的数量

LL ans;

int n,g,h;

string s;

int main()

{   cin>>n;

   cin>>s;

   //记录l数组

   for(int i=0;i<s.size();i++){

       if(s[i]=='G') l[i]=h,h=0,g++;  //如果字母为G,记录左边连续H的数量,此时连续H的数量归0,连续G的数量加1(下面操作类似)

       else l[i]=g,g=0,h++;

   }

   //记录r数组

   h=0,g=0;

   for(int i=s.size()-1;i>=0;i--){

       if(s[i]=='G') r[i]=h,h=0,g++;

       else r[i]=g,g=0,h++;

   }

   //结果可能超int范围,将其中一个转成long long

   for(int i=0;i<s.size();i++){

       ans+=(LL)l[i]*r[i]+max(l[i]-1,0)+max(r[i]-1,0);   //l[i]和r[i]可能为0,减1结果可能为负数,需与0取max

   }

   cout<<ans;

   return 0;

}


目录
相关文章
AcWing 4261. 孤独的照片(每日一题)
AcWing 4261. 孤独的照片(每日一题)
【寒假每日一题】AcWing 4455. 出行计划
目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 差分与前缀和
116 0
【AcWing每日一题】4261. 孤独的照片
【AcWing每日一题】4261. 孤独的照片
72 0
|
算法 C++ Python
【每日算法Day 87】今天我脱单了,所以大家不用做题了!
【每日算法Day 87】今天我脱单了,所以大家不用做题了!
122 0
|
机器学习/深度学习 测试技术
AcWing - 寒假每日一题2023(DAY 16——DAY 20)
AcWing - 寒假每日一题2023(DAY 16——DAY 20)
|
存储 人工智能 BI
AcWing - 寒假每日一题2023(DAY 11——DAY 15)
AcWing - 寒假每日一题2023(DAY 11——DAY 15)
|
机器学习/深度学习 Java C++
【寒假每日一题】AcWing 4818. 奶牛大学(补)
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
92 0
|
存储 人工智能 JavaScript
【寒假每日一题】AcWing 4510. 寻宝!大冒险!
目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
136 0
|
机器学习/深度学习 并行计算
【寒假每日一题】AcWing 4729. 解密(补)
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 韦达定理及其逆定理
78 0
|
机器学习/深度学习
【蓝桥杯集训·每日一题】 AcWing 3996. 涂色
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 区间DP Unique函数
118 0