AcWing《蓝桥杯集训·每日一题》—— 3956.截断数组
AcWing《蓝桥杯集训·每日一题》—— 3956. 截断数组
文章目录
- AcWing《蓝桥杯集训·每日一题》—— 3956. 截断数组
- 一、题目
- 二、解题思路
- 三、代码实现
本次博客我是通过Notion软件写的,转md文件可能不太美观,大家可以去我的博客中查看:北天的 BLOG,持续更新中,另外这是我创建的编程学习小组频道,想一起学习的朋友可以一起!!!
一、题目
现在,要将该数组从中间截断,得到三个非空子数组。
要求,三个子数组内各元素之和都相等。
请问,共有多少种不同的截断方法?
输入格式
第一行包含整数n。
第二行包含n个整数a1, a2,… . , an。
输出格式
输出一个整数,表示截断方法数量。
数据范围
前六个测试点满足1≤n≤10。
所有测试点满足1≤<n≤10^5,-10000≤a_i≤10000。
输入样例1:
4
1 2 3 3
输出样例1:
1
输入样例2:
5
1 2 3 4 5
输出样例2:
0
输入样例3:
2
0 0
输出样例3:
0
二、解题思路
- 首先,需要确定数组的长度是否符合题目中的要求,也就是说,长度是否大于等于3。
- 如果数组的长度符合要求,您可以计算出数组的总和,并判断总和是否能够被3整除。
- 如果数组的总和可以被3整除,您可以计算出每个子数组的目标和。
- 接下来,您可以使用前缀和数组来预处理数组的前缀和。
- 然后,您可以遍历前缀和数组,如果当前前缀和等于目标和的两倍,则该点是可能的分割点。
- 最后,您可以从第一个可能的分割点开始,计算其他可能的分割点的数量,并将其加入答案。
通过使用前缀和,我们可以在O(n)的时间复杂度内解决此问题。
什么是前缀和?
前缀和是一种数学技巧,用于快速求出一个数组的前缀和。前缀和数组定义为:对于数组a中的每个元素a[i],前缀和数组prefix[i]表示a[0]到a[i]的和。
例如,对于数组a=[1, 2, 3, 4, 5],前缀和数组prefix为[1, 3, 6, 10, 15]。
使用前缀和数组可以在O(1)的时间复杂度内查询数组中某一段元素的和,而不需要重新遍历数组。这在很多题目中,如区间求和,有很多应用。
三、代码实现
def cut(n, nums):# 判断数组元素个数是否小于3,若是则不存在可行解,直接返回0if n < 3:return 0# 求数组元素和s = sum(nums)# 判断数组元素和是否为3的倍数,若不是则不存在可行解,直接返回0if s % 3 != 0:return 0# 将数组元素和除以3,得到每段的平均值avg = s // 3# 初始化cnt数组,用于存储每个前缀的符合要求的数量cnt = [0] * (n + 1)# 初始化presum数组,用于存储每个前缀的元素和presum = [0] * (n + 1)# 枚举每个前缀,计算元素和for i in range(1, n + 1):presum[i] = presum[i - 1] + nums[i - 1]# 枚举每个前缀,判断元素和是否为2倍的平均值for i in range(1, n):if presum[i] == avg * 2:cnt[i] = 1# 枚举每个前缀,累加符合要求的数量for i in range(1, n):cnt[i] += cnt[i - 1]# 初始化结果为0res = 0# 枚举每个前缀,判断元素和是否为平均值for i in range(n - 2):if presum[i + 1] == avg:res += cnt[n - 1] - cnt[i + 1]# 返回结果return resn = int(input().strip())
nums = list(map(int, input().strip().split()))
print(cut(n, nums))
相关文章:
AcWing《蓝桥杯集训·每日一题》—— 3956.截断数组
AcWing《蓝桥杯集训每日一题》—— 3956. 截断数组 文章目录AcWing《蓝桥杯集训每日一题》—— 3956. 截断数组一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的,转md文件可能不太美观,大家可以去我的博客中查看:北天的 BLOG…...
Docker的数据管理
一、管理docker容器中数据 管理Docker 容器中数据主要有两种方式:数据卷(Data Volumes)和数据卷容器( DataVolumes Containers) 。 1、 数据卷 数据卷是一个供容器使用的特殊目录,位于容器中。可将宿主机的目录挂载到数据卷上,对数据卷的修改操作立刻…...
RxJS处理异步数据流
什么是异步? 异步(Asynchronous)指的是不同步发生的事件或操作。通常,同步操作是指一系列代码按照顺序依次执行,直到当前代码块执行完毕后才继续执行下一个代码块;而异步操作则是指某些代码会被提交到后台执行&#…...
IP地址与用户行为
IP地址能够解决网络风险和提高网络安全的原因是:所有的网络请求都会带有IP信息,是访问者的独立标识,另外ip地址的分配和管理比较严格,难以造假。另外ip属于网络层,可以轻松的对其进行阻断。现有的各种网络安全、负载均…...
底层逻辑2
有些创业者,在3D打印⽕爆的时候做3D打印,在VR(虚拟现 实)蓬勃发展的时候转⾏做VR,在区块链成为热⻔话题的时候摇身⼀ 变成了区块链专家,⽽⼈⼯智能⽕了以后,他们⼜全身⼼投⼊⼈⼯智 能这⼀⾏。再…...
TCP报头详解及TCP十种核心机制(一)
目录 前言: TCP报头 TCP核心机制 一、确认应答 二、超时重传 小结: 前言: 这篇文章详细介绍了TCP报头中的一些核心数据,及两种TCP核心机制。其他的一些机制会在后面文章中详细介绍。 TCP报头 解释: 1ÿ…...
Linux用户的添加、修改和删除以及相关配置文件:useradd、passwd、usermod、userdel、相关配置文件
目录 账户的创建(useradd) 第一步:创建账号 第二步:创建密码 useradd参考文件 CROUP100 HOME/home INACTIVE-1 EXPIRE SHELL/bin/bash SKEL/etc/skel UID/GID密码参数参考:/etc/login.defs 密码参数显示命…...
进程地址空间
目录 回顾C/C语言的程序地址空间 感性认识虚拟地址空间 虚拟地址空间与物理空间如何建立映射关系 为什么要虚拟地址空间? 回顾C/C语言的程序地址空间 在学习C/C语言时我们知道了一个概念叫程序地址空间。通俗来说就是如下一张表,从中可以得知系统的几…...
数楼梯(加强版)
数楼梯(加强版) 题目背景: 小明一天放学回家,看到从1楼到2楼共有n个台阶,因为好奇,他想尝试一下总共有几种方案到二楼?他可以1步,2步,3步的跳,不能跳3步以上. 他试了很多次都没有解决这个问题,于是请求聪明的你帮忙解决这个问题. 题目描述: 1楼到2楼楼梯有n级台阶。小明每…...
MySQL-数据类型
数据类型简介数据表由多列字段构成,每一个字段指定了不同的数据类型,指定了数据类型之后,也就决定了向字段插入的数据内容。不同的数据类型也决定了 MySQL 在存储它们的时候使用的方式,以及在使用它们的时候选择什么运算符号进行运…...
剑指 Offer 32 - II. 从上到下打印二叉树 II(java解题)
剑指 Offer 32 - II. 从上到下打印二叉树 II(java解题)1. 题目2. 解题思路3. 数据类型功能函数总结4. java代码5. 踩坑记录1. 题目 从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。 例如: 给定二叉…...
C#网络爬虫开发
1前言爬虫一般都是用Python来写,生态丰富,动态语言开发速度快,调试也很方便但是我要说但是,动态语言也有其局限性,笔者作为老爬虫带师,几乎各种语言都搞过,现在这个任务并不复杂,用我…...
Fastjson 总结
0x00 前言 这一篇主要是针对已经完成的fastjson系列做一个知识点总结,一来是为了更加有条理的梳理已经存在的内容,二来是为了更好的复习和利用。 0x01 Fastjson基础知识点 1.常见问题: 问:fastjson的触发点是什么?…...
文件路径模块os.path
文件路径模块os.path 文章目录文件路径模块os.path1.概述2.解析路径2.1.拆分路径和文件名split2.2.获取文件名称basename2.3.返回路径第一部分dirname2.4.扩展名称解析路径splitext2.5.返回公共前缀路径commonprefix3.创建路径3.1.拼接路径join3.2.获取家目录3.3.规范化路径nor…...
Kerberos简单介绍及使用
Kerberos作用 简单来说安全相关一般涉及以下方面:用户认证(Kerberos的作用)、用户授权、用户管理.。而Kerberos功能是用户认证,通俗来说解决了证明A是A 的问题。 认证过程(时序图) 核心角色/概念 KDC&…...
DOM编程-全选、全不选和反选
<!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>全选、全不选和反选</title> </head> <body bgcolor"antiquewhite"> <script type"text/jav…...
C++11可变模板参数
C11可变模板参数一、简介二、语法三、可变模版参数函数3.1、递归函数方式展开参数包3.2、逗号表达式展开参数包一、简介 C11的新特性–可变模版参数(variadic templates)是C11新增的最强大的特性之一,它对参数进行了高度泛化,它能…...
Linux多线程
目录 一、认识线程 1.1 线程概念 1.2 页表 1.3 线程的优缺点 1.3.1 优点 1.3.2 缺点 1.4 线程异常 二、进程 VS 线程 三、Linux线程控制 3.1 POSIX线程库 3.1 线程创建 3.3 线程等待 3.4 线程终止 3.4.1 return退出 3.4.2 pthread_exit() 3.4.3 pthread_cancel…...
Webpack5 环境下 Openlayers 标注(Icon) require 引入图片问题
Webpack5 环境下 Openlayers 标注(Icon) require 引入图片问题环境版本Openlayers 使用 require 问题Webpack5 正确配置构建新环境的时候,偶然发现 Openlayers 使用 require 的方式加载图片(Icon)报错,开始…...
Zookeeper安装部署
文章目录Zookeeper安装部署Zookeeper安装部署 将Zookeeper安装包解压缩, [rootlocalhost opt]# ll 总用量 14032 -rw-r--r--. 1 root root 12392394 10月 13 11:44 apache-zookeeper-3.6.0-bin.tar.gz drwxrwxr-x. 6 root root 4096 10月 18 01:44 redis-5.0.4 …...
Cow Acrobats ( 临项交换贪心 )
题目大意: N 头牛 , 每头牛有一个重量(Weight)和一个力量(Strenth) , N头牛进行排列 , 第 i 头牛的风险值为其上所有牛总重减去自身力量 , 问如何排列可以使最大风险值最小 , 求出这个最小的最大风险值&am…...
MySQL:为什么说应该优先选择普通索引,尽量避免使用唯一索引
前言 在使用MySQL的过程中,随着表数据的逐渐增多,为了更快的查询我们需要的数据,我们会在表中建立不同类型的索引。 今天我们来聊一聊,普通索引和唯一索引的使用场景, 以及为什么说推荐大家优先使用普通索引…...
Spring Cloud alibaba之Feign
JAVA项目中如何实现接口调用?HttpclientHttpclient是Apache Jakarta Common下的子项目,用来提供高效的、最新的、功能丰富的支持Http协议的客户端编程工具包,并且它支持HTTP协议最新版本和建议。HttpClient相比传统JDK自带的URL Connection&a…...
零信任-Google谷歌零信任介绍(3)
谷歌零信任的介绍? "Zero Trust" 是一种网络安全模型,旨在通过降低网络中的信任级别来防止安全威胁。在零信任模型中,不论请求来自内部网络还是外部网络,系统都将对所有请求进行详细的验证和审核。这意味着每次请求都需…...
Numpy基础——人工智能基础
文章目录一、Numpy概述1.优势2.numpy历史3.Numpy的核心:多维数组4.numpy基础4.1 ndarray数组4.2 内存中的ndarray对象一、Numpy概述 1.优势 Numpy(Nummerical Python),补充了Python语言所欠缺的数值计算能力;Numpy是其它数据分析及机器学习库的底层库&…...
电商仓储与配送云仓是什么?
仓库是整个供给链的关键局部。它们是产品暂停和触摸的点,耗费空间和时间(工时)。空间和时间反过来也是费用。经过开发数学和计算机模型来微调仓库的规划和操作,经理能够显著降低与产品分销相关的劳动力本钱,进步仓库空间应用率,并…...
【零基础入门前端系列】—HTML介绍(一)
【零基础入门前端系列】—HTML介绍(一) 一、什么是HTML HTML是用来描述网页的一种语言HTML指的是超文本标记语言:HyperText Markup LanguageHTML不是一种编程语言,而是一种超文本标记语言,标记语言是一套标记标签(ma…...
Elasticsearch索引库和文档的相关操作
前言:最近一直在复习Elasticsearch相关的知识,公司搜索相关的技术用到了这个,用公司电脑配了环境,借鉴网上的课程进行了总结。希望能够加深自己的印象以及帮助到其他的小伙伴儿们😉😉。 如果文章有什么需要…...
使用Python,Opencv检测图像,视频中的猫
使用Python,Opencv检测图像,视频中的猫🐱 这篇博客将介绍如何使用Python,OpenCV库附带的默认Haar级联检测器来检测图像中的猫。同样的技术也可以应用于视频流。这些哈尔级联由约瑟夫豪斯(Joseph Howse)训练…...
浅谈域名和服务器集约化管理的误区
一个正常的网站通常由域名、网站程序、服务器三个部分组成,网站程序由单位开发设计,而域名和服务器则需要租用购买,那么域名和服务器之间的关系是什么?如何实现域名和服务器的有效管理呢? 服务器和域名的关系 服务器…...
商标名字大全/seo网站推广教程
1.Eclipse从svn导入Gradle项目 1.检出项目的时候不要选新项目,选“做为工作空间中的项目检出”,然后点Finish。 2.将项目转为Gradle项目,右键导入的项目->Configure->Add Gradle Natrue 3.完成 2.Gradle安装和命令介绍 转:…...
建设网站以后怎么让百度收录呢/天津网络关键词排名
修改手机app默认连接服务器地址 内容精选换一换TTL(Time-To-Live)指解析记录在本地DNS服务器中的缓存时间。本地DNS服务器指用户客户端(手机、电脑等)连接Internet网络使用的DNS,默认使用的DNS是宽带运营商自动分配的DNS服务器,用户也可以将该DNS修改为公…...
格泰网站建设/南宁seo
官网地址 首页:https://about.gitlab.com/ 安装说明:https://about.gitlab.com/installation/ 安装命令摘录 sudo yum install -y curl policycoreutils-python openssh-server cronie sudo lokkit -s http -s ssh sudo yum install postfix sudo s…...
乐山北京网站建设/seo手机端优化
移动、联通、电信版P6均可成功的EMUI3.0开发版/稳定版 ROOT... - P6/P6s 花粉俱乐部 http://cn.club.vmall.com/forum.php?modviewthread&tid1710032&extrapage%3D4%26filter%3Dauthor%26orderby%3Ddateline%26orderby%3Ddateline 华为 Ascend P6 联通版首个真正意义的…...
高大上网站建设公司/电商网站对比
YAF中文文档:http://www.laruence.com/manual/index.html 1 YAF框架是用C开发的,属于PHP的扩展框架; 2 YAF的性能相对于源生PHP,性能只降低不到10%; 下面直接切入正题,如何在windows下扩展yaf并生成yaf框架…...
天河建网站公司/磁力搜索
一、comm命令 comm命令可以用于两个文件之间的比较(必须是已经排序的两个文件,可以使用sort命令先进行排序),它有一些选项可以用来调整输出,以便执行交集、求差、以及差集操作。 交集:打印出两个文件所共有…...