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 …...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战
🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...

深入理解 C++ 左值右值、std::move 与函数重载中的参数传递
在 C 编程中,左值和右值的概念以及std::move的使用,常常让开发者感到困惑。特别是在函数重载场景下,如何合理利用这些特性来优化代码性能、确保语义正确,更是一个值得深入探讨的话题。 在开始之前,先提出几个问题&…...