【AcWing】蓝桥杯集训每日一题Day7|贡献法|4261.孤独的照片(C++)

2024-03-30 21:28

本文主要是介绍【AcWing】蓝桥杯集训每日一题Day7|贡献法|4261.孤独的照片(C++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

4261.孤独的照片
AcWing 4261. 孤独的照片(每日一题) - AcWing
难度:简单
时/空限制:1s / 64MB
总通过数:9889
总尝试数:26088
来源:

USACO 2021 December Contest Bronze
算法标签

贡献法乘法原理

题目内容

Farmer John 最近购入了 N 头新的奶牛,每头奶牛的品种是更赛牛(Guernsey)或荷斯坦牛(Holstein)之一。
奶牛目前排成一排,Farmer John 想要为每个连续不少于三头奶牛的序列拍摄一张照片。
然而,他不想拍摄这样的照片,其中只有一头牛的品种是更赛牛,或者只有一头牛的品种是荷斯坦牛——他认为这头奇特的牛会感到孤立和不自然。
在为每个连续不少于三头奶牛的序列拍摄了一张照片后,他把所有「孤独的」照片,即其中只有一头更赛牛或荷斯坦奶牛的照片,都扔掉了。
给定奶牛的排列方式,请帮助 Farmer John 求出他会扔掉多少张孤独的照片。
如果两张照片以不同位置的奶牛开始或结束,则认为它们是不同的。

输入格式

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

输出格式

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

数据范围

3≤N≤5×10^5

输入样例:
5
GHGHG
输出样例:
3
样例解释

这个例子中的每一个长为 3 的子串均恰好包含一头更赛牛或荷斯坦牛——所以这些子串表示孤独的照片,并会被 Farmer John 扔掉。
所有更长的子串(GHGHHGHGGHGHG)都可以被接受。

题目解析
贡献法

是一个数学思想,在枚举一些数的时候,有些枚举可能比较难算,可能换一种枚举方式比较好算
比如要统计矩阵里面所有数的和
如果按行统计比较复杂,按列统计比较简单,就按列统计
换一种统计的方式,就叫贡献法
看每一列对答案的贡献是什么
按行去统计的话,就是计算每一行它所有数的和
按列去统计的话,就是计算每一列所有数的和,再相加
第i列的总和,可以看成是第i列对整个总和的贡献

  1. 购入了N头牛,每头牛是更赛牛或荷斯坦牛
  2. 所有牛排成一排
  3. 枚举其中所有连续的不少于三头牛的区间,区间的数量是 O ( N 2 ) O(N^2) O(N2)
  4. 判断其中有多少个区间,里边有一种牛只有一头,有孤独的牛的话,就要扔掉
    统计一共有多少张照片是孤独的,统计多少个区间里边,某一个字符只出现一次
    N是50万,所以需要将时间复杂度控制在 O ( n log ⁡ 2 n ) O(n\log_{2}n) O(nlog2n)级别
暴力枚举

根据题目直接算的话,可以先去枚举所有区间,要枚举起点和终点,就是 O ( n 2 ) O(n^2) O(n2)级别
再统计区间内的每一个字符的出现次数 O ( n ) O(n) O(n)
过不去

换一种观察角度

在矩阵里边,如果每个区间是以行的话,牛如果是列的话,每一个区间里面如果相片是孤独的话,它一定对应一条唯一的孤独的牛,
所以每一个孤独的区间,跟一头牛是一一对应的
**切入点:**孤独区间一定会对应一头孤独的牛
但是一头牛不一定只对应一个区间

想统计孤独区间的数量的话,
如果暴力,先枚举区间,再去找孤独的牛
如果区间是行的话,有 O ( n 2 ) O(n^2) O(n2)级别个,在这 O ( n 2 ) O(n^2) O(n2)级别个中去找出所有孤独的区间的话:
如果第一个区间是孤独的区间,其中一定会存在一头孤独的牛,在孤独的牛这里标记为1,其余的牛都写成0
这样如果想统计孤独区间的数量,就可以换一种角度去统计,可以按列去统计,
统计一下第一头牛是多少个孤独区间的那一头孤独的牛,就是统计第一头牛对答案的贡献,

000100
100000
000010
100000
000100

如果第一头牛在两个区间里面是孤独的牛,就认为第一头牛对答案的贡献是2,第二头牛是0,第三头牛是0,第四头牛是2
这样子也可以把答案统计出来

时间复杂度可以做一些优化

假设改去枚举牛的话
一旦牛确定了,考虑一下一共有多少个区间是以这头牛为核心的孤独的区间
要考虑的区间肯定要包含这头牛,这个区间的左端点一定要在这头牛的左边,右端点应该在这头牛的右边,如果这头牛是孤独的牛的话,那么它的左右边一定是与它相对的那些牛

所有这样的区间要有多少个呢

这种统计次数是可以优化的,先统计一下左边有多少个连续的数量L,再统计一下右边连续的数量R,有了这个信息之后,如何去计算有多少个区间包含这头牛,且这头牛是孤独的且这头牛只出现一次

将所有的区间分成三大类
![[Pasted image 20240330162312.png]]

  1. 左右两边都各自至少有一个H,加上中间这个G的话,长度就大于等于3了
    可以发现,这样的话一定可以满足区间长度大于等于3,是合法的。这类区间的数量有多少个呢,左边相当于画挡板,左边有多少个H就可以画多少个挡板,右边有多少个H可以画多少种挡板,左右两边是独立的。因此这类区间的数量,就是左边H的数量乘以右边H的数量,也就是L*R,可以直接算
    ![[Pasted image 20240330162333.png]]

  2. 左边无H,右边至少有两个H,因为区间长度要大于等于3
    这类区间的数量,如果右边H的数量是R个的话,除了第一个H不能画分隔板之外,后面的每一个H都可以右边画一个分隔板,因此第二类区间的数量应该是R-1
    隔板就是指右端点
    ![[Pasted image 20240330162345.png]]

  3. 右边无H,左边至少有两个H,同理这类区间的数量是L-1

可以发现,枚举完孤独的牛之后,只需要能够快速的预处理出来左边连续的跟它不一样的牛的数量,以及每头牛右边连续的跟它不一样的牛的数量,就可以用 O ( 1 ) O(1) O(1)的时间计算出来这一列有多少个1,也就是计算出来有多少个包含这头牛且以这头牛为孤独的牛的区间的数量有多少个,这样时间复杂度 O ( n ) O(n) O(n),就可以过了

如何快速地预处理L和R,快速地计算一个字符左边有多少个连续的跟它不一样的字符

以预处理L为例,从前往后枚举,
在枚举的时候,比如孤独的牛是G的话,要看它左边连续的H的数量,如果是H的话,看它左边连续G的数量,在从前往后推的时候,只要记录一下到目前为止,连续的G的数量跟连续的H的数量就可以了,
可以动态更新

  • 如果孤独的牛是G的话,G左边连续的H的数量, S H S_{H} SH
  • 如果是H的话,左边连续G的数量就是 S G S_{G} SG
    在每次枚举的时候要动态更新一下 S H 和 S G S_{H}和S_{G} SHSG
  1. 如果枚举到H的话,表示 S H + + S_{H}++ SH++,因为这里是H,G没有,所以 S G = 0 S_{G}=0 SG=0
  2. 如果枚举到G的话, S G + + , S H = 0 S_{G}++,S_{H}=0 SG++,SH=0
    所以L是可以通过 O ( n ) O(n) O(n)的预处理算出来,
    R的话倒过来预处理就可以了,也是 O ( n ) O(n) O(n)的,这样整个算法的时间复杂度就是 O ( n ) O(n) O(n)

答案有可能爆int,因为是 N 2 N^2 N2级别

贡献法其实就是换一种枚举的角度,矩阵是为了方便理解
如果先枚举区间再枚举牛是 O ( n 2 ) O(n^2) O(n2)的,如果先枚举牛再枚举区间的话就变成 O ( n ) O(n) O(n)

代码
#include <iostream>
#include <cstring>
#include <algorithm>typedef long long LL;using namespace std;const int N = 500010;int n;
char str[N];
int l[N], r[N];int main()
{//先预处理Lscanf("%d%s", &n, str);//sh表示h的数量,sg表示g的数量for (int i = 0, sh = 0, sg = 0; i < n; i ++){//如果发现当前是G的话if (str[i] == 'G'){//左边H的数量就是shl[i] = sh;//因为这里是Gsg ++, sh = 0;}else{l[i] = sg;sh ++;sg = 0;}}//枚举R的话就从后往前枚举for (int i = n - 1, sh = 0, sg = 0; i >= 0; i --){if (str[i] == 'G'){r[i] = sh;sg ++;sh = 0;}else{r[i] = sg;sh ++;sg = 0;}}//定义一下答案LL res = 0;//枚举一下每一个牛作为一个孤独的牛,有多少个孤独区间以它为孤独的牛,res应该加上3中情况的总和for (int i = 0; i < n; i ++){//这里跟0去一个max,如果右边没有的话,不能少一个,不能越加越少res += (LL)l[i]*r[i] + max(r[i]-1, 0) +max(l[i]-1, 0);}printf("%lld\n", res);return 0;	
}

这篇关于【AcWing】蓝桥杯集训每日一题Day7|贡献法|4261.孤独的照片(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/862621

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

【C++高阶】C++类型转换全攻略:深入理解并高效应用

📝个人主页🌹:Eternity._ ⏩收录专栏⏪:C++ “ 登神长阶 ” 🤡往期回顾🤡:C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

c++的初始化列表与const成员

初始化列表与const成员 const成员 使用const修饰的类、结构、联合的成员变量,在类对象创建完成前一定要初始化。 不能在构造函数中初始化const成员,因为执行构造函数时,类对象已经创建完成,只有类对象创建完成才能调用成员函数,构造函数虽然特殊但也是成员函数。 在定义const成员时进行初始化,该语法只有在C11语法标准下才支持。 初始化列表 在构造函数小括号后面,主要用于给

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(