【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++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法

深入解析C++ 中std::map内存管理

《深入解析C++中std::map内存管理》文章详解C++std::map内存管理,指出clear()仅删除元素可能不释放底层内存,建议用swap()与空map交换以彻底释放,针对指针类型需手动de... 目录1️、基本清空std::map2️、使用 swap 彻底释放内存3️、map 中存储指针类型的对象

C++ STL-string类底层实现过程

《C++STL-string类底层实现过程》本文实现了一个简易的string类,涵盖动态数组存储、深拷贝机制、迭代器支持、容量调整、字符串修改、运算符重载等功能,模拟标准string核心特性,重点强... 目录实现框架一、默认成员函数1.默认构造函数2.构造函数3.拷贝构造函数(重点)4.赋值运算符重载函数

C++ vector越界问题的完整解决方案

《C++vector越界问题的完整解决方案》在C++开发中,std::vector作为最常用的动态数组容器,其便捷性与性能优势使其成为处理可变长度数据的首选,然而,数组越界访问始终是威胁程序稳定性的... 目录引言一、vector越界的底层原理与危害1.1 越界访问的本质原因1.2 越界访问的实际危害二、基

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次,点赞9次,收藏44次。本文介绍Log4cplus,一种适用于C++的线程安全日志记录API,提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java,log4c

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,:本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式,需要用

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发;同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域