[ AT_agc009_c]Division into Two

题目传送门

大家都知道集合吧,原谅我喜欢说废话

解法

先钦定 A > B A>B A>B,
先把数排好序得到数组 a a a,考虑先解决集合 X X X的问题,

设计状态:

明显只有一维( n < = 1 e 5 n<=1e5 n<=1e5),所以有:
f i : X 集合最后放的是第 i 个数,对于前 i 个数来说 X , Y 都合法的方案数 f_i:X集合最后放的是第i个数,对于前i个数来说X,Y都合法的方案数 fi:X集合最后放的是第i个数,对于前i个数来说X,Y都合法的方案数
发现后 ( n − i ) (n-i) ni个放在 Y Y Y的数我们未保证合法,但是我们之后特判一下就好了

状态转移

f i f_i fi f j f_j fj转移而来
考虑有哪些 j j j可以贡献:
1. i > j i>j i>j(废话)
2. a i − a j ≥ A a_i-a_j\ge A aiajA(差值大于 A A A)
3. max ⁡ { a k − a k − 1 } ≥ B , k ∈ ( j , i ) \max\{a_k-a_{k-1}\}\ge B,k\in(j,i) max{akak1}B,k(j,i)(满足 Y Y Y集合的要求)
则: f i = ∑ f j f_i=\sum f_j fi=fj

code:

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7,N=1e5+7;
int n,l,r;
int f[N],sum[N];
ll A,B;
ll a[N];
int main(){scanf("%d%lld%lld",&n,&A,&B);if(A<B) swap(A,B);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for (int i=1;i+2<=n;++i)if (a[i+2]-a[i]<B) return puts("0"),0;a[0]=0;f[0]=sum[0]=1;for(int i=1;i<=n;i++) {while(a[i]-a[r+1]>=A) r++;if(l<=r) {f[i]=(1ll*f[i]+1ll*sum[r])%mod;if(l) f[i]=(1ll*f[i]-1ll*sum[l-1]+mod)%mod;}sum[i]=(1ll*sum[i-1]+1ll*f[i])%mod;if(a[i]-a[i-1]<B) l=i-1;}int ans=0;for(int i=n;~i;i--){	ans=(1ll *ans+1ll*f[i])	%mod;if(i<n && a[i+1]-a[i] <B) break;}printf("%d\n",ans);
}

TXL

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

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

相关文章

说说CDN和负载均衡具体是怎么实现的

分析&回答 什么是 CDN CDN (全称 Content Delivery Network)&#xff0c;即内容分发网络。 构建在现有网络基础之上的智能虚拟网络&#xff0c;依靠部署在各地的边缘服务器&#xff0c;通过中心平台的负载均衡、内容分发、调度等功能模块&#xff0c;使用户就近获取所需…

stable diffusion实践操作-文生图

本文专门开一节写文生图相关的内容&#xff0c;在看之前&#xff0c;可以同步关注&#xff1a; stable diffusion实践操作 正文 1 liblib SD1.5底模 lora(baihuaniang_1.0) 详细信息&#xff1a; 底模&#xff1a;SD 1.5 Lora:baihuaniang_1.0 正向提示词&#xff1a; Best …

【Python】批量下载页面资源

【背景】 有一些非常不错的资源网站,比如一些MP3资源网站。资源很丰富,但是每一个资源都不大,一个一个下载费时费力,想用Python快速实现可复用的批量下载程序。 【思路】 获得包含资源链接的静态页面,用beautifulsoup分析页面,获得所有MP3资源的实际地址,然后下载。…

数学建模:灰色预测模型

&#x1f506; 文章首发于我的个人博客&#xff1a;欢迎大佬们来逛逛 数学建模&#xff1a;灰色预测模型 文章目录 数学建模&#xff1a;灰色预测模型灰色预测算法步骤代码实现 灰色预测 三个基本方法&#xff1a; 累加数列&#xff1a;计算一阶累加生成数列 x ( 1 ) ( k ) …

Win 教程 Win7实现隔空投送

一直觉得自己写的不是技术&#xff0c;而是情怀&#xff0c;一个个的教程是自己这一路走来的痕迹。靠专业技能的成功是最具可复制性的&#xff0c;希望我的这条路能让你们少走弯路&#xff0c;希望我能帮你们抹去知识的蒙尘&#xff0c;希望我能帮你们理清知识的脉络&#xff0…

桂理理工大题

#include <stdio.h> #include <stdlib.h>int getMax(int n); int getMin(int n); int range(int n); static int count1; //作为全局变量控制每次的序列号int main(){int num;int i,j;do{printf("输入黑洞数&#xff1a;\n");scanf("%d",&…

uniapp微信小程序用户隐私保护

使用wx.requirePrivacyAuthorize实现微信小程序用户隐私保护。 一、前言 微信小程序官方出了一个公告《关于小程序隐私保护指引设置的公告》。不整的话&#xff0c;后果很多授权无法使用&#xff0c;详见《小程序用户隐私保护指引内容介绍》 。 二、隐私相关设置 1、在 微信…

IntelliJ IDEA的远程开发(Remote Development)

DEA的远程开发功能&#xff0c;可以将本地的编译、构建、调试、运行等工作都放在远程服务器上执行&#xff0c;而本地仅运行客户端软件进行常规的开发操作即可&#xff0c;官方给出的逻辑图如下&#xff0c;可见通过本地的IDE和服务器上的IDE backend将本地电脑和服务器打通&am…

react轮播图

这里 我用的是组件&#xff1a; 网址&#xff1a;Collapse 折叠面板 - Ant Design Mobile 1.首先 先声明一个变量 2、把需要的数据存存进去 3、组件内容复制过来&#xff08;这里用到的是map循环&#xff09; 然后图片就出来了 就是这个简单 哈哈哈哈&#xff01;&#xff01…

浅析ARMv8体系结构:异常处理机制

文章目录 概述异常类型中断终止Abort复位Reset系统调用 异常处理流程异常入口异常返回异常返回地址 堆栈选择 异常向量表异常向量表的配置 同步异常解析相关参考 概述 异常处理指的是处理器在运行过程中发生了外部事件&#xff0c;导致处理器需要中断当前执行流程转而去处理异…

AI绘画:StableDiffusion实操教程-斗罗大陆2-江楠楠-常服(附高清图下载)

前段时间我分享了StableDiffusion的非常完整的教程&#xff1a;“AI绘画&#xff1a;Stable Diffusion 终极宝典&#xff1a;从入门到精通 ” 尽管如此&#xff0c;还有读者反馈说&#xff0c;尽管已经成功安装&#xff0c;但生成的图片与我展示的结果相去甚远。真实感和质感之…

中间件环境搭建配置过程解读

中间件环境搭建 目录 中间件环境搭建xampp 搭建环境Tomcat环境配置安装mysql连接mysql 问题解决 xampp 搭建环境 安装xampp服务集成环境工具 官网地址下载项目压缩包&#xff0c;将项目文件夹放在xampp安装目录的htdocs文件夹下初始化xampp&#xff1a;运行目录内的setup_xamp…

如何解决分库分表主键问题?

分析&回答 从问题角度出发&#xff1a;我们需要一个全局唯一的 id 来支持&#xff0c;排序问题等。这都是你实际生产环境中必须考虑的问题。可以先看下我们之前的文章分布式系统唯一ID如何生成&#xff1f; 雪花算法和雪花算法的变种是大家常用的 喵呜面试助手&#xff1…

企业架构LNMP学习笔记11

Nginx配置文件的介绍&#xff1a; #nginx子进程启动用户 #user nobody; #子进程数量 一般调整为cpu核数或者倍数 worker_processes 1; #错误日志定义 #error_log logs/error.log; #error_log logs/error.log notice; #error_log logs/error.log info;#进程pid 存储文件…

Solidity 小白教程:5. 变量数据存储和作用域 storage_memory_calldata

Solidity 小白教程&#xff1a;5. 变量数据存储和作用域 storage_memory_calldata Solidity 中的引用类型 引用类型(Reference Type)&#xff1a;包括数组&#xff08;array&#xff09;&#xff0c;结构体&#xff08;struct&#xff09;和映射&#xff08;mapping&#xff…

使用boost::geometry::union_ 合并边界(内、外):方案二

使用boost::geometry::union_ 合并边界&#xff08;内、外&#xff09;&#xff1a;方案二 typedef boost::geometry::model::d2::point_xy<double> boost_point; typedef boost::geometry::model::polygon<boost_point> boost_Polygon;struct Point {float x;floa…

牛客网刷题

牛客网刷题-C&C 2023年9月3日15:58:392023年9月3日16:37:01 2023年9月3日15:58:39 2023年9月3日16:37:01 整型常量和实型常量的区别

5G智能网关如何解决城市停车痛点难点

2023年上半年&#xff0c;我国汽车新注册登记1175万辆&#xff0c;同比增长5.8%&#xff0c;88个城市汽车保有量超过100万辆&#xff0c;北京、成都等24个城市超过300万辆。随着车辆保有量持续增加&#xff0c;停车难问题长期困扰城市居民&#xff0c;也导致城市路段违停普遍、…

vscode搭建springboot开发环境

前言 idea好用到但是收money&#xff0c;eclipse免费但是界面有点丑&#xff0c;所以尝试使用vscode开发springboot 提前准备 安装jdk&#xff0c;jdk需要大于11 安装vscode 安装maven 安装插件 主要是下面的插件 Extension Pack for JavaSpring Boot Extension PackDepe…

Node爬虫项目精简版 wallhaven网站实操 2023.8.29

练习地址&#xff1a; https://wallhaven.cc/toplist const express require(express); const axios require(axios); const cheerio require(cheerio); const schedule require(node-schedule); const fs require(fs);async function downloadImage(url) {const response…