使用数学思想解决的一道题

简介: 使用数学思想解决的一道题

我感觉这道题还是挺妙的,所以就记录一下


题目的含义就是找有多少个类似于GHH  GHHH  HHG  HHGH……的字符串

(某个字母仅出现一次)

可以在纸上写一下,方便理解

image.png 代码

#include<iostream>
using namespace std;
typedef long long LL;
const int N = 500011;
int n,l[N],r[N];
char s[N];
int main()
{
    scanf("%d", &n);
    scanf("%s", s);
    for(int i=0,h=0,g=0;i<n;i++)//处理左边的
    {
        if(s[i]=='G') //如果当前位置是G
        {             //那么H的个数就要=0
            l[i]=h;
            h=0;
            g++;      //并且G的个数+1
        }
        else
        {
            l[i]=g;
            g=0;
            h++;
        }
    }
    for(int i=n-1,h=0,g=0;i>=0;i--)//处理右边的
    {
        if(s[i]=='G')
        {
            r[i]=h;
            h=0;
            g++;
        }
        else
        {
            r[i]=g;
            g=0;
            h++;
        }
    }
    LL res=0;
    for (int i = 0; i < n; i ++ )
    {
        res+=(LL)l[i]*r[i]+max(l[i]-1,0)+max(r[i]-1,0);//防止结果小于0
    }                                                  //case1:l[i]-1
    cout<<res;                                         //case2:r[i]-1
}                                                      //case3:l[i]*r[i]
//看上去在for里面,又有了max(l[i]-1,0)max(r[i]-1,0)
//但是实际上,l[0]l[1]......l[n-2]=0,只有l[n-1]!=0
//不信举个例子试试GHH
//不信举个例子试试GHH
//不信举个例子试试GHH

实在看不懂的话可以听听y总的视频讲解(文章开头有链接)

也不能一直扣一道题,休息一下再看说不定就会了

相关文章
|
算法 测试技术 C++
C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]
C++二分算法习题:判断是否是完全平方数[容易]和排列箱子[容易]
|
移动开发 小程序 前端开发
微信小程序自定义导航栏
微信小程序自定义导航栏
329 0
微信小程序自定义导航栏
|
7月前
|
移动开发 小程序 API
uniapp组件库Modal 模态框 的使用方法
uniapp组件库Modal 模态框 的使用方法
484 1
|
7月前
|
数据挖掘 定位技术
基于Amos路径分析的模型修正与调整
基于Amos路径分析的模型修正与调整
283 2
|
7月前
|
SQL 关系型数据库 MySQL
windows下安装mysql-8.0.18-winx64
windows下安装mysql-8.0.18-winx64
|
人工智能 自然语言处理 并行计算
彻底开源,免费商用,上海AI实验室把大模型门槛打下来
彻底开源,免费商用,上海AI实验室把大模型门槛打下来
220 0
|
Ubuntu 安全 Linux
Debian系Linux软件源配置详解与常用的国内软件源汇总
Debian系Linux软件源配置详解与常用的国内软件源汇总
13138 2
Debian系Linux软件源配置详解与常用的国内软件源汇总
|
存储 运维 分布式数据库
PolarDB-X集群运维1:升降配、扩缩容_与备份恢复(三)|学习笔记
快速学习PolarDB-X集群运维1:升降配、扩缩容_与备份恢复(三)
PolarDB-X集群运维1:升降配、扩缩容_与备份恢复(三)|学习笔记
|
定位技术 API 索引
项目实战---行政优先级分析
在现有地点中解析其地点优先级,最小到区县,当前区县可指定作业优先级,当绑定优先级数据后的数据应在选择时优先展示。
75 0
|
存储 程序员 开发工具
一文讲透 Git 底层数据结构和原理
本文将系统分享 Git 底层知识:对象生命周期变化,底层数据结构,数据包文件结构,数据包文件索引,以及详细分析对象查询流程和算法。(文末福利:程序员需要哪些软技能?)
2548 0
一文讲透 Git 底层数据结构和原理