二分+模拟,CF1461D - Divide and Summarize

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1461D - Codeforces


二、解题报告

1、思路分析

我们发现每次分裂操作结果都是固定的

我们从初始序列分裂出两个确定的子序列,两个确定的子序列又分裂出4个确定的子序列

那么也就是说我们最终能够分裂出的子序列的数目是O(n)的

我们预处理出所有的子序列就预处理出了所有可以得到的和(当然这个和要在分裂的过程中维护)

而分裂要求我们得到小于等于mid的部分和大于的部分

所以我们需要对原序列进行排序,模拟的过程通过二分来找到分裂的位置

同时预处理前缀和以便每次分裂前都记录一下当前得到的值

值得注意的是nums[l] = nums[r]的时候说明当前子序列是相同的,我们无法继续向下分裂

2、复杂度

时间复杂度: O(NlogN)空间复杂度:O(N)

3、代码详解

#include <bits/stdc++.h>
using PII = std::pair<int, int>;
using i64 = long long;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());const int P = [](int x) {auto isprime = [](int x) {if (x <= 1) return false;for (int i = 2; i <= x / i; i ++ )if (x % i == 0) return false;return true;};while (!isprime(x)) x ++;return x;
}(rnd() % 900000000 + 100000000);void solve() {/*  直接模拟    */int N, Q, s;std::cin >> N >> Q;std::vector<int> nums(N);std::vector<i64> pre(N + 1);for (int i = 0; i < N; i ++ ) std::cin >> nums[i];std::sort(nums.begin(), nums.end());for (int i = 0; i < N; i ++ ) pre[i + 1] += nums[i] + pre[i];std::vector<std::array<int, 2>> segs { { 0, N - 1 } };  segs.reserve(N);std::unordered_set<i64> st;while (segs.size()) {std::vector<std::array<int, 2>> nxt;for (auto& [l, r] : segs) {st.insert(pre[r + 1] - pre[l] + P);if (nums[l] != nums[r]) {int mid = std::upper_bound(nums.begin(), nums.end(), (nums[l] + nums[r]) >> 1) - nums.begin();nxt.insert(nxt.end(), { { l, mid - 1 }, { mid, r } });}}segs = std::move(nxt);}for (int i = 0, s; i < Q; i ++) {std::cin >> s;if (st.count(1LL * s + P))std::cout << "YES\n";elsestd::cout << "NO\n";}
}int main () {std::ios::sync_with_stdio(false);   std::cin.tie(0);  std::cout.tie(0);int _ = 1;std::cin >> _;while (_ --)solve();return 0;
}

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

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

相关文章

实验二、网络属性设置《计算机网络》

精神状态 be like&#xff1a;边写边崩溃&#xff0c;越写越得劲儿。 目录 一、实验目的&#xff1a; 二、实验内容 三、实验步骤&#xff1a; 四、实验小结 一、实验目的&#xff1a; 掌握 IP 地址、子网掩码等网络属性的设置。 二、实验内容 预备知识&#xff1a; 1、…

android集成百度文心一言实现对话功能,实战项目讲解,人人都能拥有一款ai应用

大家好&#xff0c;今天给大家讲解下如何实现一个基于百度文心一言的app功能&#xff0c;app内部同时集成了讯飞的语音识别。本文适用于有android基础的小伙伴阅读&#xff0c;文章末尾放上本项目用到的全部实例代码&#xff0c;在使用前请务必看完本文章。 先来给大家看看效果…

php质量工具系列之PHPCPD

PHPCPD 用于检测重复代码&#xff0c;直观的说就是复制粘贴再稍微改改 该工具作者已经 停止维护 安装 composer global require --dev sebastian/phpcpd执行 phpcpd --log-pmd phpcpd_result.xml ./app参数介绍 --log-pmd 将结果保存在phpcpd_result.xml 中 ./app 是phpcpd扫…

编译原理-词法分析(实验 C语言)

编译原理-词法分析 1. 实验目的 设计、编写并调试一个词法分析程序&#xff0c;加深对词法分析原理的理解 2. 实验要求 2.1 待分析的简单语言的词法 关键字&#xff1a;begin&#xff0c;if&#xff0c;then&#xff0c;while&#xff0c;do&#xff0c;end 所有关键字都是…

DevOps入门

DevOps: 让技术团队、运维、测试等团队实现一体式流程自动化 CICD: CI:持续集成 CD:持续交付持续集成:从编码、编译、测试、发布项目到仓库的自动化流程持续交付:包含持续集成&#xff0c;并且增加将项目部署到对应的环境的自动化流程 传统项目闭环流程: DevOps闭环流程…

基于非下采样小波包分析的滚动轴承故障诊断(MATLAB R2021B)

小波变换具有良好的时频局部化特性和多分辨率特性&#xff0c;可准确定位信号的突变点并可在不同尺度上描述信号的局部细节特征&#xff0c;被广泛应用于信号降噪。但标准正交小波变换不具有平移不变性&#xff0c;采用标准正交小波对信号消噪后&#xff0c;会在脉冲尖峰处产生…

VSCode调试揭秘:Live Server助力完美测试Cookie与Session,远超“Open in Browser“!

文章目录 一、项目场景&#xff1a;二、问题描述1. open in browser&#xff1a;2. open with live server 三、原因分析&#xff1a;先了解一下open in browser和open with live server的区别两者的优缺点open in browseropen with live server 四、解决方案&#xff1a;总结 …

Java开发-面试题-0005-==和String的equals()和String的intern()方法的区别

Java开发-面试题-0005-和String的equals()和String的intern()方法的区别 更多内容欢迎关注我&#xff08;持续更新中&#xff0c;欢迎Star✨&#xff09; Github&#xff1a;CodeZeng1998/Java-Developer-Work-Note 技术公众号&#xff1a;CodeZeng1998&#xff08;纯纯技术…

前端多人项目开发中,如何保证CSS样式不冲突?

在前端项目开发中&#xff0c;例如突然来了一个大项目&#xff0c;很可能就需要多人一起开发&#xff0c;领导说了&#xff0c;要快&#xff0c;要快&#xff0c;要快&#xff0c;你们给我快。然后下面大伙就一拥而上&#xff0c;干着干着发现&#xff0c;一更新代码&#xff0…

转型AI产品经理(5):“锚定效应”如何应用在Chatbot产品中

锚定效应是认知心理学中一个重要的概念&#xff0c;它描述了人们在进行判断或决策时&#xff0c;往往过于依赖最先接收到的信息或数字&#xff08;即“锚点”&#xff09;&#xff0c;即使后续信息与初始锚点无关甚至相反&#xff0c;这个初始信息也会显著地影响最终的判断结果…

【下篇】从 YOLOv1 到 YOLOv8 的 YOLO 物体检测模型历史

YOLO 型号之所以闻名遐迩,主要有两个原因:其速度和准确性令人印象深刻,而且能够快速、可靠地检测图像中的物体。上回我解释了YoloX, 今天从Yolov6开始。 YOLOv6:面向工业应用的单级物体检测框架 美团视觉人工智能事业部(Meituan Vision AI Department)于 2022 年 9 月在…

拯救者Legion Y9000X IRX9 2024(83FD)原装出厂Windows11系统镜像下载

lenovo联想2024款拯救者Y9000X IRX9 笔记本电脑【83FD】OEM预装Win11系统安装包&#xff0c;恢复开箱状态&#xff0c;自带恢复重置还原功能 链接&#xff1a;https://pan.baidu.com/s/1i_sVcnXF4qgsuj02rebe-Q?pwdyefp 提取码&#xff1a;yefp 联想原装WIN11系统自带所有…

Junit 单元测试 详解,包你掌握

Java单元测试----Junit详解 1 什么是 Junit JUnit 是一个广泛使用的 Java 单元测试框架。它用于编写和运行可重复的测试&#xff0c;以验证 Java 程序的行为是否符合预期 也许有人会好奇&#xff0c;之前学的 Selenium 和 Junit 有什么关系&#xff1f;答案就是没关系&#…

htb-linux-6-beep

nmap web渗透 目录扫描 漏洞关键词 shell py脚本执行 flag root 目前的权限 nmap root

《精通ChatGPT:从入门到大师的Prompt指南》第4章:避免常见错误

第4章&#xff1a;避免常见错误 在使用ChatGPT进行Prompt编写时&#xff0c;常见的错误可能会大大影响生成内容的质量和准确性。本章将详细讨论这些错误&#xff0c;并提供如何避免它们的建议。 4.1 不明确的指令 在使用ChatGPT时&#xff0c;一个常见的问题是指令不够明确。…

使用proteus仿真51单片机的流水灯实现

proteus介绍&#xff1a; proteus是一个十分便捷的用于电路仿真的软件&#xff0c;可以用于实现电路的设计、仿真、调试等。并且可以在对应的代码编辑区域&#xff0c;使用代码实现电路功能的仿真。 汇编语言介绍&#xff1a; 百度百科介绍如下&#xff1a; 汇编语言是培养…

Spring boot+vue前后端分离

目录 1、前端vue的搭建 2、后端项目的构建 pom文件中引入的jar包 yml文件用来配置连接数据库和端口的设置 application.property进行一些整合 service层 imp层 mapper 实体类 额外写一个类、解决跨域问题 3、测试 1、前端vue的搭建 建立项目的过程略 开启一个建立好…

JDK下载安装Java SDK

Android中国开发者官网 Android官网 (VPN翻墙) 通过brew命令 下载OracleJDK(推荐) 手动下载OracleJDK(不推荐) oracle OracleJDK下载页 查找硬件设备是否已存在JDK环境 oracle官网 备注&#xff1a; JetPack JavaDevelopmentKit Java开发的系统SDK OpenJDK 开源免费SDK …

unity3d:GameFramework+xLua+Protobuf+lua-protobuf,生成.cs,.pb工具流

概述 1.区分lua&#xff0c;cs用的proto 2.proto生成cs&#xff0c;使用protogen.exe&#xff0c;通过csharp.xslt修改生成cs样式 3.proto生成lua加载.pb二进制文件&#xff0c;并生成.pb列表文件&#xff0c;用于初始化加载 4.协议id生成cs&#xff0c;lua中枚举 区分cs&…

spring boot3登录开发-2(3邮件验证码接口实现)

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《spring boot实战》 目录 写在前面 上文衔接 接口设计与实现 1.接口分析 2.实现思路 3.代码实现 1.定义验证码短信HTML模板枚举类 2.定义验证码业务接口 3. 验证码业务接口实现 4.控制层代码 4.测试 写…