小埋的解密游戏的题解

目录

原题描述:

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

主要思路:

代码实现code:


原题描述:

题目描述

小埋最近在玩一个解密游戏,这个游戏的解密方法是这样的,这个游戏会给你提供 n 个数,让我们求出这 n 个数里面,有多少个连续的数的平均数大于某个给定的数 M 。这个数可能会很大,所以我们要输出这个数对 1e9+7的取模结果。现在小埋对于这个游戏的解法还是不太理解,现在请你帮助小埋解决这个问题。

输入格式

输入有两行。第一行为两个数 n和 M 。第二行为n 个数。

输出格式

输出的数占一行,即问题的解对 1e9+7 取模的结果。

样例 #1

样例输入 #1

4 3 
1 5 4 2

样例输出 #1

5

样例 #2

样例输入 #2

4 4 5 2 7 3

样例输出 #2

6

提示

1 \le n \le 2 * 10^5

1 \le M \le 3*10^3

所有的数均为正整数且不大于5000

主要思路:

这个题目。由于是平均数>m,所以我们可以将所有的数-m,求一遍前缀和,进行归并排序,求出所有的正序对(i<j,且a[i]<a[j])的数对。

代码实现code:

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int a[200010],b[200010];
long long ret=0;
int shu[200010];
void merge(int l,int r)
{if(l == r){return;}int mid=(l+r)/2;merge(l,mid);merge(mid+1,r);//归并排序分治int i=l,j=mid+1,tot=l;while(i<=mid&&j<=r){if(a[i]<a[j]){ret+=(mid-i+1)%mod;ret%=mod;b[tot++]=a[j++];	}else{b[tot++]=a[i++];}}while(i<=mid){b[tot++]=a[i++];	}while(j<=r){b[tot++]=a[j++];}//区间合并for(int i=l;i<=r;i++){a[i]=b[i];}
}
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>shu[i];shu[i]-=m;a[i] = a[i-1]+shu[i];}merge(0,n);cout<<ret;return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

秒杀相关问题解决

秒杀 超卖问题 如下,我们先来复现问题,抢购秒杀券的代码逻辑也是很简单, 先判断优惠券是否开始了,是的化,判断库存是否充足,如果是的化,扣减库存,最后创建订单 如下是代码 Override Transactional public Result seckillVoucher(Long voucherId) {//1.查询优惠券SeckillVo…

物联网数据隐私保护技术

在物联网&#xff08;IoT&#xff09;的世界中&#xff0c;无数的设备通过互联网连接在一起&#xff0c;不断地收集、传输和处理数据。这些数据有助于提高生产效率、优化用户体验并创造新的服务模式。然而&#xff0c;随着数据量的剧增&#xff0c;数据隐私保护成为了一个不能忽…

探索设计模式的魅力:外观模式简化术-隐藏复杂性,提供简洁接口的设计秘密

设计模式专栏&#xff1a;http://t.csdnimg.cn/U54zu 目录 引言&#xff1a;探索简化之路 一、起源和演变 二、场景案例分析 2.1 不用模式实现&#xff1a;用一坨坨代码实现 2.2 问题 2.3 外观模式重构代码 定义 界面 接口 利用外观模式解决问题步骤 外观模式结构和说明 重构…

GEE数据集——全球日光日照地图分布图数据

日光地图分布图数据 在社区和专业地图绘制者的支持下&#xff0c;Daylight 是全球开放地图数据的完整分发版。我们将 OpenStreetMap 等项目的全球贡献者的工作与 Daylight 地图合作伙伴的质量和一致性检查相结合&#xff0c;创建了一个免费、稳定和易于使用的街道尺度全球地图。…

【Larry】英语学习笔记语法篇——换一种方式理解词性

目录 一、换一种方式理解词性 1、名词、形容词、副词&#xff0c;这就是一切 2、词性之间的修饰关系 3、介词其实很简单 形容词属性的介词短语 副词属性的介词短语 ①修饰动词 ②修饰形容词 ③修饰其他副词 一、换一种方式理解词性 1、名词、形容词、副词&#xff0c…

【集合系列】TreeMap 集合

TreeMap 集合 1. 概述2. 方法3. 遍历方式4. 排序方式5. 代码示例16. 代码示例27. 代码示例38. 注意事项9. 源码分析 其他集合类 父类 Map 集合类的遍历方式 TreeSet 集合 具体信息请查看 API 帮助文档 1. 概述 TreeMap 是 Java 中的一个集合类&#xff0c;它实现了 SortedMap…

修改SpringBoot中默认依赖版本

例如SpringBoot2.7.2中ElasticSearch版本是7.17.4 我希望把它变成7.6.1

机器学习算法之支持向量机(SVM)

SVM恐怕大家即使不熟悉&#xff0c;也听说过这个大名吧&#xff0c;这一节我们就介绍这相爱相杀一段内容。 前言&#xff1a;在介绍一个新内容之SVM前&#xff0c;我们不觉映入眼帘的问题是为什么要引入SVM&#xff1f;吃的香&#xff0c;睡的着的情况下&#xff0c;肯定不会是…

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之Slider组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之Slider组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Slider组件 滑动条组件&#xff0c;通常用于快速调节设置值&#xff0c;如音量调…

揭开Markdown的秘籍:标题|文字样式|列表

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;Markdown指南、网络奇遇记 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. ⛳️Markdown 标题二. ⛳️Markdown 文字样式2.1 &#x1f514;斜体2.2 &…

谷歌发布AI新品Gemini及收费模式;宜家推出基于GPT的AI家装助手

&#x1f989; AI新闻 &#x1f680; 谷歌发布AI新品Gemini及收费模式 摘要&#xff1a;谷歌宣布将原有的AI产品Bard更名为Gemini&#xff0c;开启了谷歌的AI新篇章。同时推出了强化版的聊天机器人Gemini Advanced&#xff0c;支持更复杂的任务处理&#xff0c;提供了两个月的…

【Makefile语法 01】程序编译与执行

目录 一、编译原理概述 二、编译过程分析 三、编译动静态库 四、执行过程分析 一、编译原理概述 make&#xff1a; 一个GCC工具程序&#xff0c;它会读 makefile 脚本来确定程序中的哪个部分需要编译和连接&#xff0c;然后发布必要的命令。它读出的脚本&#xff08;叫做 …

JavaWeb02-MyBatis

目录 一、MyBatis 1.概述 2.JavaEE三层架构简单介绍 &#xff08;1&#xff09;表现层 &#xff08;2&#xff09;业务层 &#xff08;3&#xff09;持久层 3.框架 4.优势 &#xff08;1&#xff09;JDBC的劣势 &#xff08;2&#xff09;MyBatis优化 5.使用 &#…

Linux操作系统基础(六):Linux常见命令(一)

文章目录 Linux常见命令 一、命令结构 二、ls命令 三、cd命令 四、mkdir命令 五、touch命令 六、rm命令 七、cp命令 八、mv命令 九、cat命令 十、more命令 Linux常见命令 一、命令结构 command [-options] [parameter]说明: command : 命令名, 相应功能的英文单词…

2024.2.4 awd总结

学习一下awd的靶机信息 防御阶段 感觉打了几次awd&#xff0c;前面阶段还算比较熟练 1.ssh连接 靶机登录 修改密码 [root8 ~]# passwd Changing password for user root. New password: Retype new password: 2.xftp连接 备份网站源码 xftp可以直接拖过来 我觉得这步还…

106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)

题目描述 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 题目示例 输入&#xff1a;inorder [9,3,15,20,7], postorder [9,15,7,20,3] 输出&a…

【前沿技术杂谈:多模态文档基础模型】使用多模态文档基础模型彻底改变文档 AI

【前沿技术杂谈&#xff1a;多模态文档基础模型】使用多模态文档基础模型彻底改变文档 AI 从文本到多模态模型&#xff1a;文档 AI 逐渐发展新技能。行业领先的型号Document AI 的下一步&#xff1a;开发通用和统一框架 您是否曾经被包含不同信息&#xff08;如应付账款、日期、…

k8s-常用工作负载控制器(更高级管理Pod)

一、工作负载控制器是什么&#xff1f; 二、Deploymennt控制器&#xff1a;介绍与部署应用 部署 三、Deployment控制器&#xff1a;滚动升级、零停机 方式一&#xff1a; 通个加入健康检查可以&#xff0c;看到&#xff0c;nginx容器逐个被替代&#xff0c;最终每个都升级完成&…

【k8s系列】(202402) 证书apiserver_client_certificate_expiration_seconds

apiserver_client_certificate_expiration_second证书定义的位置&#xff1a;kubernetes/staging/src/k8s.io/apiserver/pkg/authentication/request/x509/x509.go at 244fbf94fd736e94071a77a8b7c91d81163249d4 kubernetes/kubernetes (github.com) apiserver_client_certi…

【51单片机】外部中断和定时器中断

目录 中断系统中断介绍中断概念 中断结构及相关寄存器中断结构中断相关寄存器 外部中断实验外部中断配置软件设计实验现象 定时器中断定时器介绍51 单片机定时器原理51 单片机定时/计数器结构51 单片机定时/计数器的工作方式 定时器配置硬件设计软件设计实验现象 中断系统 本章…