当前位置: 首页 > news >正文

Sequence 2023牛客暑期多校训练营6 E

登录—专业IT笔试面试备考平台_牛客网

题目大意:有一长度为n的数组a,有q次询问,每次要求将[l,r]的区间分成k个连续区间,满足每个区间和都是偶数,能满足要求就输出YES

1<=n,q<=1e5;0<=ai<=1e10;1<=l<=r<n;1<=k<=1e5

思路:要想和为偶数,那么奇数的数量必须是偶数个,所以我们把数组中的数都变成%2后的结果,也就是整个数组只有0和1构成,每个0可以作为一个合法的区间,而每个1必须要和其相邻的一个1组合才能构成一个最小的合法区间,而如果一个1和其相邻的一个1组成一个区间,那这两个1中间的0都不能作为合法的区间。

所以我们要分两种情况讨论,一种是数组中从左往右第二个1和第一个1组合,另一种是第二个和第三个1组合,然后分别对合法区间数求前缀和,每个0的贡献都是1,每个含有两个1的区间,整个区间贡献是1,例如对于0 0 1 0 0 1 0 0 1 0 0 1 0这个数组,第一个前缀和数组sum1求出来的是1 2 3 3 3 3 4 5 6 6 6 6 7,第二个数组sum2是0 0 0 1 2 3 3 3 3 4 5 6 6,另外,还要特判一下每个区间内1的数量是否是偶数,如果是奇数就可以直接输出no了。

对于其他情况,我们要看每个询问的区间适用于哪个数组,如果a[r]是1,那么哪个数组的sum[r]=sum[r-1],说明哪个数组是合法的,如果a[r]是0,那么就看哪个sum[r]!=sum[r-1],不等的那个数组提供贡献

#include<bits/stdc++.h>
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll MOD = 998244353;
ll a[N];
ll sum[N];
ll sum2[N];
ll sum3[N];
void solve()
{int n, q;cin >> n >> q;for (int i = 1; i <= n; i++){cin >> a[i];a[i] %= 2;//将数组按奇偶转换成1和0sum[i] = sum[i - 1] + a[i];//统计区间奇偶性sum2[i] = sum3[i] = 0;}int flag = 0;for (int i = 1; i <= n; i++){if (!a[i]){if(!flag)sum2[i] = 1;//在两个1中间以外的0贡献为1}else{if (!flag){flag = i;//记录上一个1的位置}else{sum2[flag]++;//上一个1到这一个1之间总共贡献1flag = 0;}}	}if (flag)//末尾没有匹配的1要+1贡献与前面的0区分开sum2[flag]++;flag = 0;int fi=0;for (int i = 1; i <= n; i++){if (!a[i]){if(!fi)//在遇到第一个1之前不记录贡献continue;if (!flag)sum3[i] = 1;}else{if(!fi){fi=i;//遇到第一个1之后,后面的统计与上一个数组相同continue;}if (!flag){flag = i;}else{sum3[flag]++;flag = 0;}}}if (flag)sum3[flag]++;for (int i = 2; i <= n; i++){//求前缀和得到区间内的合法区间数sum2[i] = sum2[i - 1] + sum2[i];sum3[i] = sum3[i - 1] + sum3[i];}for (int i = 1; i <= q; i++){int l, r, k;cin >> l >> r >> k;if ((sum[r] - sum[l - 1]) % 2!=0){cout << "NO" << endl;continue;}ll ans3 = sum3[r] - sum3[l - 1];ll ans2 = sum2[r] - sum2[l - 1];if (a[r] == 1){//右端点是1,哪个数组r=r-1就说明哪个合法if (sum2[r] == sum2[r - 1]){cout << (ans2 >= k ? "YES" : "NO") << endl;}else{cout << (ans3 >= k ? "YES" : "NO") << endl;}}else{//右端点是0,哪个数组r!=r-1就说明哪个合法if (sum2[r] != sum2[r - 1]){cout << (ans2 >= k ? "YES" : "NO") << endl;}else{cout << (ans3 >= k ? "YES" : "NO") << endl;}}}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){solve();}return 0;
}

相关文章:

Sequence 2023牛客暑期多校训练营6 E

登录—专业IT笔试面试备考平台_牛客网 题目大意&#xff1a;有一长度为n的数组a&#xff0c;有q次询问&#xff0c;每次要求将[l,r]的区间分成k个连续区间&#xff0c;满足每个区间和都是偶数&#xff0c;能满足要求就输出YES 1<n,q<1e5;0<ai<1e10;1<l<r&l…...

【ASP.NET MVC】使用动软(二)(10)

一、添加动软生成工程 按前文添加动态到工程 双击动软 完成新建数据库服务器后 &#xff0c;需要关闭重新打开 选择简单三层&#xff0c;注意保存位置 注意切换数据库&#xff1a; 生成后拷贝五个文件夹到工程目录 注意目录结构&#xff1a; 添加四个项目到原来的工程&…...

STM32入门学习之独立看门狗(IWDG)

1.STM32的独立看门狗是一个具有独立时钟的片上外设。通常&#xff0c;为了防止程序卡死&#xff0c;可以设置看门狗定时复位。当看看门狗被使能之后&#xff0c;会按初始化时设置的计数值进行计数。当根据计数值计数的倒数时间为0时&#xff0c;便会自动复位程序&#xff0c;即…...

抖音seo矩阵系统源码搭建开发详解

抖音SEO矩阵系统是一个用于提高抖音视频在搜索引擎排名的工具。如果你想开发自己的抖音SEO矩阵系统&#xff0c;以下是详细的步骤&#xff1a; 开发步骤详解&#xff1a; 确定你需要的功能和算法 抖音SEO矩阵系统包含很多功能&#xff0c;比如关键词研究、内容优化、链接建设、…...

2685. 统计完全连通分量的数量;2718. 查询后矩阵的和;1600. 王位继承顺序

2685. 统计完全连通分量的数量 核心思想&#xff1a;枚举所有的连通分量&#xff0c;然后判断这些连通分量是不是完全连通分量&#xff0c;完全连通分量满足边数2e 点数v(v-1)。 2718. 查询后矩阵的和 核心思想&#xff1a;后面的改变更重要&#xff0c;所以我们直接逆向思维…...

SpringBoot统一功能处理(AOP思想实现)(统一用户登录权限验证 / 异常处理 / 数据格式返回)

主要是三个处理&#xff1a; 1、统一用户登录权限验证&#xff1b; 2、统一异常处理&#xff1b; 3、统一数据格式返回。 目录 一、用户登录权限校验 &#x1f345; 1、使用拦截器 &#x1f388; 1.1自定义拦截器 &#x1f388; 1.2 设置自定义拦截器 &#x1f388;创建cont…...

git stash 用法

起始 今天在看一个bug&#xff0c;之前一个分支的版本是正常的&#xff0c;在新的分支上上加了很多日志没找到原因&#xff0c;希望回溯到之前的版本&#xff0c;确定下从哪个提交引入的问题&#xff0c;但是还不想把现在的修改提交&#xff0c;也不希望在Git上看到当前修改的…...

生鲜蔬果小程序的完整教程

随着互联网的发展&#xff0c;线上商城成为了人们购物的重要渠道。其中&#xff0c;小程序商城在近年来的发展中&#xff0c;备受关注和青睐。本文将介绍如何使用乔拓云网后台搭建生鲜果蔬配送小程序&#xff0c;并快速上线。 首先&#xff0c;登录乔拓云网后台&#xff0c;进入…...

De Bruijin序列与魔术(二)——魔术《De Bruijin序列》

早点关注我&#xff0c;精彩不错过&#xff01; 上一篇我们介绍了De Bruijin序列的基本数学内容以及其如何应用在魔术上的一些基本内容&#xff0c;今天我们就来学习一下这个经典的《De Bruijin序列》魔术。 De bruijin序列魔术 先看视频。 视频1 De Bruijin序列的魔术 魔术来源…...

ARCGIS地理配准出现的问题

第一种。已有省级行政区矢量数据&#xff0c;在网上随便找一个相同省级行政区图片&#xff0c;利用地理配准工具给图片添加坐标信息。 依次添加省级行政区选择矢量数据、浙江省图片。 此时&#xff0c;图层默认的坐标系与第一个加载进来的省级行政区选择矢量数据的坐标系一致…...

redis原理 6:小道消息 —— PubSub

前面我们讲了 Redis 消息队列的使用方法&#xff0c;但是没有提到 Redis 消息队列的不足之处&#xff0c;那就是它不支持消息的多播机制。 img 消息多播 消息多播允许生产者生产一次消息&#xff0c;中间件负责将消息复制到多个消息队列&#xff0c;每个消息队列由相应的消费组…...

Android Studio 的Gradle版本修改

使用Android Studio构建项目时&#xff0c;需要配置Gradle&#xff0c;与Gradle插件。 Gradle是一个构建工具&#xff0c;用于管理和自动化Android项目的构建过程。它使用Groovy或Kotlin作为脚本语言&#xff0c;并提供了强大的配置能力来定义项目的依赖关系、编译选项、打包方…...

Redis的部分面试题

1.Redis是什么?简述它的优缺点? Redis的字符串类型是通过简单动态字符串SDS来实现的。简单动态字符串是Redis自己实现的一种字符串表示方式&#xff0c;相比于C语言中的传统字符串&#xff0c;它具有以下几个特点&#xff1a; 1. 动态调整大小&#xff1a;简单动态字符串可…...

单通道 6GSPS 16位采样DAC子卡模块--【资料下载】

FMC147是一款单通道6.4GSPS&#xff08;或者配置成2通道3.2GSPS&#xff09;采样率的12位AD采集、单通道6GSPS&#xff08;或配置成2通道3GSPS&#xff09;采样率16位DA输出子卡模块&#xff0c;该板卡为FMC标准&#xff0c;符合VITA57.4规范&#xff0c;该模块可以作为一个理想…...

Python 文件操作详解

概要 Python进行文件操作&#xff0c;在日常编程中是很常用的。为了方便大家&#xff0c;这里对各种文件操作的知识进行汇总。一文在手&#xff0c;无须它求&#xff01;来一起学习吧。 一、文件的打开和关闭 open()函数 f1 open(rd:\测试文件.txt, moder, encodingutf-8) c…...

【Rust 基础篇】Rust Never类型:表示不会返回的类型

导言 Rust是一种以安全性和高效性著称的系统级编程语言&#xff0c;其设计哲学是在不损失性能的前提下&#xff0c;保障代码的内存安全和线程安全。在Rust中&#xff0c;Never类型是一种特殊的类型&#xff0c;它表示一个函数永远不会返回。Never类型在Rust中有着重要的应用场…...

error “Component name “*****“ should always be multi-word”解决方案

问题 在 vue-cli 创建的项目中&#xff0c;创建文件并命名后&#xff0c;会报 “Component name "*****" should always be multi-word” 报错&#xff1b; Component name "index" should always be multi-word.eslintvue/multi-word-component-names原…...

前后端开发的区别是什么?

VUE的开发方式为什么和后端的MVC开发方式不一样呢&#xff1f; 实际上&#xff0c;Vue 和后端开发的 MVC&#xff08;Model-View-Controller&#xff09;方式是不同的&#xff0c;因为它们面对的问题和场景也不同。 前端与后端的职责不同&#xff1a; 前端和后端的职责和任务不…...

小白电脑装机(自用)

几个月前买了配件想自己装电脑&#xff0c;结果最后无法成功点亮&#xff0c;出现的问题是主板上的DebugLED黄灯常亮&#xff0c;即DRAM灯亮。对于微星主板的Debug灯&#xff0c;其含义这篇博文中有说明。 根据另一篇博文&#xff0c;有两种可能。 我这边曾将内存条和主板一块…...

Quic协议 0-RTT

目录 1、Quic协议 2、Quic直接通过TLS握手进行建立链接&#xff0c;TLS是1.3版本 3.1、通过缓存服务器公钥实现0-RTT&#xff0c;服务器 通过kdf密钥派生机制&#xff0c;来产生会话加密key&#xff0c;保证数据向前安全性 3.2、通过PKN来实现数据重传保证数据完整性&…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

起重机起升机构的安全装置有哪些?

起重机起升机构的安全装置是保障吊装作业安全的关键部件&#xff0c;主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理&#xff1a; 一、超载保护装置&#xff08;核心安全装置&#xff09; 1. 起重量限制器 功能&#xff1a;实时监测起升载荷&a…...