备战蓝桥杯---贡献法刷题

话不多说,直接看题:

什么是贡献法?这是一种数学思想,就是看每一个元素对总和的贡献。

1.

我们可以先枚举区间再统计次数,但这显然TLE。我们可以发现,每一个孤独的区间对应一个孤独的牛,因此我们考虑枚举每一个牛对答案的贡献。

我们只要统计一下它左边与右边连续的个数,相乘即可,若左无,那么就是右边的。

分别为L*R,L-1,R-1.

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500010;
int n;
char str[N];
int l[N],r[N];
int main(){
    scanf("%d%s",&n,str);
    for(int i=0,sh=0,sg=0;i<n;i++){
        if(str[i]=='G') l[i]=sh,sg++,sh=0;
        else l[i]=sg,sh++,sg=0;
    }
     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;
    for(int i=0;i<n;i++){
        res+=(LL)l[i]*r[i]+max(r[i]-1,0)+max(l[i]-1,0);
    }
    cout<<res;
}

2.

我们看一看t中的每一位对答案的贡献,每一轮都是它的字符在S中出现的次数,因此我们选S中出现最多的即可,答案就是x^n,其中x是最长长度的字符有几种,下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100010,mod=1e9+7;
char s[N];
int cnt[100];
int main(){
    int n;
    cin>>n;
    scanf("%s",s);
    int mx=0,ct=0;
    for(int i=0;i<n;i++){
        int t=++cnt[s[i]];
        if(t>mx) mx=t,ct=1;
        else if(t==mx) ct++;
    }
    long long res=1;
    for(int i=0;i<n;i++){
        res=(long long)res*ct%mod;
    }
    cout<<res;
}

3.

跟第一题差不多,我们只要统计出它左边倒数第二次出现的位置以及往右第一次出现的位置即可

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long LL;
int n;
char str[N];
int l[N],r[N],p[26];
int main(){
    scanf("%s",str+1);
    n=strlen(str+1);
    for(int i=1;i<=n;i++){
        int t=str[i]-'a';
        l[i]=p[t];
        p[t]=i;
    }
    for(int i=0;i<26;i++) p[i]=n+1;
    for(int i=n;i;i--){
        int t=str[i]-'a';
        r[i]=p[t];
        p[t]=i;
    }
    LL res=0;
    for(int i=1;i<=n;i++) res+=(LL)(i-l[i])*(r[i]-i);
    cout<<res;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519144.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

计组第三版书例题

基础知识过一下 存储器与CPU的连接主要通过数据总线、地址总线和控制总线实现。CPU首先向存储器发送地址信号&#xff0c;然后发出读写控制信号&#xff0c;最后在数据总线上进行数据的读写操作 。这种连接方式确保了CPU能够正确地访问和控制存储器中的数据。 https://blog.cs…

2024免费Mac电脑用户的系统清理和优化软件CleanMyMac

作为产品营销专家&#xff0c;对于各类产品的特性与优势有着深入的了解。CleanMyMac是一款针对Mac电脑用户的系统清理和优化软件&#xff0c;旨在帮助用户轻松管理、优化和保护Mac电脑。以下是关于CleanMyMac的详细介绍&#xff1a; CleanMyMac X2024全新版下载如下: https://…

蓝桥-时间显示

目录 题目链接 代码 题目链接 1.时间显示 - 蓝桥云课 (lanqiao.cn) 代码 #include <bits/stdc.h> using namespace std;int main() {long long x;cin>>x;int h,m,s;x x / 1000 % (3600*24); // 毫秒化秒&#xff0c;并且保留最后一天的时间h x / 3600; //求得…

使用pip install替代conda install将packet下载到anaconda虚拟环境

问题描述 使用conda install 下载 stable_baseline3出现问题 一番搜索下是Anaconda.org缺少源 解决方法 首先使用管理员权限打开 anaconda prompt 然后激活目标环境&#xff1a;conda activate env_name 接着使用&#xff1a;conda env list查看目标env的位置 如D:\anacon…

C语言进阶课程学习记录-第23课 - #error 和 #line 使用分析

C语言进阶课程学习记录-第23课 - #error 和 #line 使用分析 实验-#errer的使用演示cmd窗口实验-缺少#error实验-#line 1的使用实验-#line 1用于标记代码小结 本文学习自狄泰软件学院 唐佐林老师的 C语言进阶课程&#xff0c;图片全部来源于课程PPT&#xff0c;仅用于个人学习记…

MySQL介绍和安装

MySQL介绍和安装 文章目录 MySQL介绍和安装1.MySQL介绍2.MySQL安装2.1 主机初始化2.1.1 设置网卡名和ip地址2.1.2 配置镜像源2.1.3 关闭防火墙2.1.4 禁用SELinux2.1.5 设置时区 2.2 包安装2.2.1 Rocky和CentOS 安装 MySQL2.2.2 Ubuntu 安装 MySQL 2.3 二进制安装安装MySQL2.3.1…

基于SpringBoot+微信小程序的防诈骗平台

一、项目背景介绍&#xff1a; 社会背景随着互联网的高速发展&#xff0c;网络和手机的普及率也大大提高&#xff0c;这也衍生出一系列问题&#xff1a;用户信息泄露、不法分子电话诈骗等…现越来越多的老年人甚至年轻人经历过电信诈骗并被骗了大量金额。该产品正是基于这样的社…

CMOS漏极开路门

线与 通常CMOS门电路都有反相器作为输出缓冲电路。在实际工程中&#xff0c;为了方便常将两个门的输入端直接并联来实现与逻辑功能&#xff08;称为线与&#xff09;。如下图所示&#xff1a; 线与的弊端&#xff1a;当与电源VDD直接相连的PMOS管导通时&#xff0c;由于MOS管导…

arm开发板移植工具mkfs.ext4

文章目录 一、前言二、手动安装e2fsprogs1、下载源码包2、解压源码3、配置4、编译5、安装 三、移植四、验证五、总结 一、前言 在buildroot菜单中&#xff0c;可以通过勾选e2fsprogs工具来安装mkfs.ext4工具&#xff1a; Target packages -> Filesystem and flash utilit…

发布自己的github项目

git下载 git关网&#xff1a;https://git-scm.com/ 下载后是exe文件 git安装 除了选安装地址&#xff0c;其他都是下一步下一步傻瓜式安装 安装好之后随便一个地方右键多了两个东西 git gui here 和git bash here git测试配置及创建github项目 右键git bash here 测试…

C语言操作SQL数据库

1.打开/创建数据库的C语言接口 int sqlite3_open(const char *filename, sqlite3 **ppDb) 该例程打开一个指向 SQLite 数据库文件的连接&#xff0c;返回一个用于其他 SQLite 程序的数据库连接对象。 int sqlite3_close(sqlite3*) 该例程关闭之前调用 sqlite3_open() 打开的数据…

java(7)之跳转语句

1、break跳转语句 说到break其实也不是跳转&#xff0c;它更像是一个终结语句&#xff0c;常用于在循环语句需要停止出现例如 while&#xff08;&#xff09;{ if&#xff08;&#xff09;{ break&#xff1b; }} 这样的形式或者 switch&#xff08;&#xff09;{ case…

水离子雾化壁炉如何实现火焰的虚实变化?

水离子雾化壁炉通过调节水雾的密度和电子控制器的设置来实现火焰的虚实变化。具体实现方法如下&#xff1a; 调节水雾密度&#xff1a; 超声波振动器可以调节水分子的雾化效果&#xff0c;从而控制水雾的密度。增加水雾的密度会使火焰看起来更实&#xff0c;而减少水雾的密度则…

Pytoch安装记录

使用pycharm 1、CUDA的安装 官网&#xff1a;CUDA Toolkit Archive | NVIDIA Developer 选择对应的版本 选择对应的版本进行下载&#xff1a; 有3个多G cuda的安装需要注意&#xff0c;如果没有安装vs&#xff0c;则需要选择自定义安装&#xff0c;在自定义的安装中取消 安…

HTML常用标签-最基础的标签

从本篇开始&#xff0c;我们围绕HTML原生标签开始&#xff0c;围绕整个前端三剑客进行&#xff0c;将进行一个大致的介绍和案例展示&#xff0c;没有啥技术含量&#xff0c;只是把学习前端的时候&#xff0c;案例全部展示出来&#xff0c;作为一个实时记录&#xff0c;或者说回…

《QT实用小工具·十三》FlatUI辅助类之各种炫酷的控件集合

1、概述 源码放在文章末尾 FlatUI辅助类之各种炫酷的控件集合 按钮样式设置。文本框样式设置。进度条样式。滑块条样式。单选框样式。滚动条样式。可自由设置对象的高度宽度大小等。自带默认参数值。 下面是demo演示&#xff1a; 项目部分代码如下所示&#xff1a; #ifnd…

c/c++ | socket tcp client server

突然想着&#xff0c;花一个socket tcp 客户-服务通信 这应该是很经典的流程了吧 感觉还是要训练这种随手画图的能力&#xff0c;毕竟文字的描述还是不及图片强烈 参考01

c# wpf style 简单试验

1.概要 wpf style 用来控制控件的样式 2.代码 <Window x:Class"WpfApp2.Window5"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schemas.…

CKA 基础操作教程(二)

Kubernetes Deployment 理论学习 Kubernetes Deployment &#xff08;部署&#xff09;是一种 Kubernetes 资源对象&#xff0c;用于定义和管理容器化应用程序的部署和更新。Deployment 提供了一种声明性的方式来定义应用程序的期望状态&#xff0c;并负责确保所需数量的 Pod…

测开——Java、python、SQL、数据结构面试题整理

一、Java 1.Java中finally、final、finalize的区别 1.性质不同 &#xff08;1&#xff09;final为关键字; &#xff08;2&#xff09;finalize()为方法; &#xff08;3&#xff09;finally为为区块标志,用于try语句中; 2. 作用 &#xff08;1&#xff09;final为用于标识…