【CodeForces】Codeforces Round 859 (Div. 4) D

嘿嘿嘿,CF虐我千百遍,我待CF如初见! (doge)

目录

题目含义:

前缀和:

代码 

🎆音乐分享(点击链接可以听哦)

A Hundred Miles(一百英里) - Meat Puppets - 单曲 - 网易云音乐 (163.com)


  

Problem - D - Codeforces

🏳️‍🌈🏳️‍🌈🏳️‍🌈

小吉是真的没有想到这道题可以用前缀和来写(学了前缀和,但是没有发挥用途,我真的会乌鱼呀,让我怎么荔枝呀(纯纯坤语言doge)) 

 🏳️‍🌈🏳️‍🌈🏳️‍🌈

这道题依然传承了cf的基本格式( t 个样例,然后进行讨论)

cf的题,都会给出样例,如果题目描述中有样例解释,一定要看,因为有时候题目看不懂(呜呜呜,因为是英语),但是看样例却可以看懂,甚至可以做对题

题目含义:

总个数 n  

题目中给出了 l r k 三个字母,其中,l 可以代表左边界的下标,r 可以代表右边界的下标,

(l - r + 1)代表需要替换的长度,这个长度中的每个数的大小是 k 

(比如 l=2 r=3 k=3,那么长度为2,为 [ 3 , 3] )

情况1:替换的长度(l - k + 1) = n

那么所有的数(n个数)的值都为k

情况2:替换的长度(l - k + 1) < n

由于替换的长度(l - k + 1) < n,那么就要用原数组的数来补全没有被替换掉的数

这个时候,我们应该如何在原数组里面对应被替换掉的数的位置和数组中剩下的数的位置和大小呢,这就要用到前缀和了 

前缀和:

什么是前缀和:
原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
前缀和 Si为数组的前 i项和
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]

求 [l, r]中的和, 即为 S[r] - S[l-1]

前缀和的作用:
快速求出元素组中某段区间的和

方法:

首先做一个预处理,定义一个sum[]数组,sum[i]代表a数组中前i个数的和

for(int i = 1; i <= n;i++)

    sum[i] = sum[i - 1] + a[i];   
}

这样,对于每个询问,只需要执行 sum[r]-sum[l-1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)。

注意:

下标最好从1开始(从0开始也可以,主要是根据个人习惯)

具体案例请参考下面的代码

代码 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll a[N],sum[N];
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,q;
		cin>>n>>q;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];//前缀和
		while(q--){
			int l,r,k;
			cin>>l>>r>>k;
			ll ans=sum[n]-(sum[r]-sum[l-1])+(r-l+1)*k;
			if(ans%2==0)cout<<"NO"<<endl;
			else cout<<"YES"<<endl;
		}
	}
}

Code over!

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

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

相关文章

JDBC——Java数据库连接

文章目录一、数据库工具类二、JDBC—— Java数据库连接三、执行DML语句四、执行DQL语句五、关联查询六、执行预编译SQL语句七、SELECT语句八、练习创建表:student1九、向student1表中插入100条数据十、删除名字为Test20---Test100的学生十一、将student1表中所有test学生的年龄…

基于深度学习的花卉检测与识别系统(YOLOv5清新界面版,Python代码)

摘要&#xff1a;基于深度学习的花卉检测与识别系统用于常见花卉识别计数&#xff0c;智能检测花卉种类并记录和保存结果&#xff0c;对各种花卉检测结果可视化&#xff0c;更加方便准确辨认花卉。本文详细介绍花卉检测与识别系统&#xff0c;在介绍算法原理的同时&#xff0c;…

在不丢失数据的情况下解锁锁定的 Android 手机的 4 种方法

尽管您可以使用指纹解锁手机&#xff0c;但大多数智能手机都需要 PIN 码、图案或字母数字代码作为主密码。如果您有一段时间没有输入手机密码&#xff0c;很容易忘记。正是由于这个原因&#xff0c;即使您打开了指纹解锁&#xff0c;大多数智能手机也会让您每天至少输入一次 PI…

Pandas的DataFrame的生产,DF数据查看

这篇文档介绍了 Pandas 的入门使用方法。Pandas 是 Python 的一个数据分析库&#xff0c;可以方便地操作数据和进行数据分析。 本节以下列方式导入 Pandas 与 NumPy&#xff1a; In [1]: import numpy as npIn [2]: import pandas as pd#生成对象 用值列表生成 Seriesopen in…

并发编程(五)-ExecutorService源码分析

一、ExecutorService是什么?ExecutorService 是 Java 中的一个接口&#xff0c;它扩展了 Executor 接口&#xff0c;并提供了更多的方法来处理多线程任务。它是 Java 中用于执行多线程任务的框架之一&#xff0c;可以创建一个线程池&#xff0c;将多个任务提交到线程池中执行。…

【C++进阶】十一、哈希的应用---布隆过滤器(二)

目录 一、布隆过滤器提出 二、布隆过滤器概念 三、布隆过滤器实现 3.1 布隆过滤器的插入 3.2 布隆过滤器的查找 3.3 布隆过滤器的删除 3.4 完整代码 四、布隆过滤器优点 五、布隆过滤器缺陷 一、布隆过滤器提出 在注册账号设置昵称的时候&#xff0c;有些软件要求每个…

元宇宙、区块链 通俗易懂

什么是区块链&#xff1f;比特币挖矿是什么&#xff1f;元宇宙是什么&#xff1f;Web(万维网)的三权化进化&#xff1a;基于此&#xff0c;介绍下“元宇宙”。1992年&#xff0c;美国作家史蒂芬森在《雪崩》一书中首次提出了“元宇宙(Metaverse)”的概念。元宇宙实际上就是一种…

【MIT 6.S081】Lab3: page tables

PgtblPrint a page tableA kernel page table per processSimplify copyin/copyinstr本Lab简单优化了系统的页表功能&#xff0c;使得程序在内核态时可以直接解析用户态的指针。笔者用时约8hPrint a page table 第一部分是为系统添加一个打印给定页表的函数vmprint&#xff0c…

C语言-程序环境和预处理(2)

文章目录预处理详解1.预定义符号2.#define2.1#define定义的标识符2.2#define定义宏2.3#define替换规则注意事项&#xff1a;2.4#和###的作用##的作用2.5带副作用的宏参数2.6宏和函数的对比宏的优势&#xff1a;宏的劣势&#xff1a;宏和函数的一个对比命名约定3.undef4.条件编译…

centos系统/dev/mapper/centos-root目录被占满的解决方式

最近在做虚拟机部署docker微服务时&#xff0c;发现磁盘内存占满&#xff0c;无法进行操作。open /var/lib/dpkg/info/libc6:amd64.templates: no space left on device接下来就写下我在备份虚拟机上如何解决根目录被占满的问题&#xff1a;1、查看虚拟机磁盘使用情况df -h可以…

D - 统计子矩阵 (双指针+前缀和+降维处理)

D - 统计子矩阵 &#xff08;双指针前缀和降维处理&#xff09; 1、问题 D - 统计子矩阵 2、分析 代码 &#xff08;1&#xff09;纯暴力做法&#xff1a; 这个做法就很简单了&#xff0c;我们直接枚举所有的子矩阵&#xff0c;然后在对每一个子矩阵内部的元素逐一累加起…

【计算机二级】综合题目

计算机二级python真题 文章目录计算机二级python真题一、《大学慕课 两问 》二、综合应用题——价值链三、基本操作题 ——信息输出一、《大学慕课 两问 》 附件中的文件data.txt 是教育部爱课程网中国大学MOOC平台的某个 HTML页面源文件,里面包含了我国参与MOOC建设的一批大学…

STM32之点亮一个LED小灯(轮询法)

目录 一、初始化GPIO口 二、按键点亮LED灯&#xff08;轮询法&#xff09; 一、初始化GPIO口 1、点亮LED小灯前&#xff0c;需要先初始化GPIO口 HAL_GPIO_Init(GPIO_TypeDef *GPIOx, GPIO_InitTypeDef *GPIO_Init) GPIO_TypeDef *GPIOx&#xff1a; //指初始化GPIO…

libvirt零知识学习5 —— libvirt源码编译安装(3)

接前一篇文章libvirt零知识学习4 —— libvirt源码编译安装&#xff08;2&#xff09; 在上篇文章及上上篇文章中构建libvirt的时候遇到了一个问题“ERROR: Problem encountered: YAJL 2 is required to build QEMU driver”。上篇文章讲到即使安装了相应的YAJL库仍然不能解决问…

HC小区管理系统window系统安装教程

实操视频 HC小区管理系统局域网window物理机部署教程_哔哩哔哩_bilibili 一、下载安装包 百度网盘&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1XAjxtpeBjHIQUZs4M7TsRg 提取码&#xff1a;hchc 或者 123盘 hc-window.zip官方版下载丨最新版下载丨绿色版下…

12个 Python 装饰器让代码cleaner

0 — 引言装饰器能在在不影响质量的情况下用更少的代码做更多的事情。Python 装饰器是强大的工具&#xff0c;可帮助你生成干净、可重用和可维护的代码。我等了很久才想了解这些抽象&#xff0c;现在我已经有了扎实的理解&#xff0c;本篇是为了帮助你也掌握这些对象背后的概念…

uni-app+uView如何轮播图滑动时改变背景颜色和导航栏颜色

今儿的创作欲很高涨哈 &#x1f604; 这也是在群里看到的&#xff0c;群友问如何在滑动&#xff08;或者自动滑动&#xff09;的时候背景颜色能跟着变 正好之前做过这个需求&#xff0c;也分享一下 首先&#xff0c;页面的组成分为三部分&#xff1a; 自定义navbar 页面背景轮…

JavaSE进阶之(十六)枚举

十六、枚举16.1 背景16.2 枚举类型16.3 EnumSet 和 EnumMap01、EnumSet02、EnumMap16.1 背景 在 Java 语言中还没有引入枚举类型之前&#xff0c;表示枚举类型的常用模式是声明一组 int 类型的常量&#xff0c;常常用的就是&#xff1a; public static final int SPRING 1; …

ElementUI学习笔记

目录 一、简单介绍 二、安装 1、下载 2、引入 三、布局 1、简介 2、使用 3、好处 四、布局容器 1、常见排布 2、调整样式 五、按钮 1、简单引用 2、改变样式 3、加载中效果 六、表格 1、简单使用 2、样式修改 七、对话框 1、简单使用 2、添加自定义内容 3、…

7个最受瞩目的 Python 库,提升你的开发效率

当今时代&#xff0c;数据分析和处理已经成为了各行各业中不可或缺的一环。Python作为一种非常流行的编程语言&#xff0c;为我们提供了许多强大的工具和库来处理不同类型的数据。 在这篇文章中&#xff0c;我将向您介绍七个非常有用的Python库&#xff0c;这些库各自有着独特…