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

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

二、解题思路

  1. 首先,需要确定数组的长度是否符合题目中的要求,也就是说,长度是否大于等于3。
  2. 如果数组的长度符合要求,您可以计算出数组的总和,并判断总和是否能够被3整除。
  3. 如果数组的总和可以被3整除,您可以计算出每个子数组的目标和。
  4. 接下来,您可以使用前缀和数组来预处理数组的前缀和。
  5. 然后,您可以遍历前缀和数组,如果当前前缀和等于目标和的两倍,则该点是可能的分割点。
  6. 最后,您可以从第一个可能的分割点开始,计算其他可能的分割点的数量,并将其加入答案。

通过使用前缀和,我们可以在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软件写的&#xff0c;转md文件可能不太美观&#xff0c;大家可以去我的博客中查看&#xff1a;北天的 BLOG…...

Docker的数据管理

一、管理docker容器中数据 管理Docker 容器中数据主要有两种方式:数据卷(Data Volumes)和数据卷容器( DataVolumes Containers) 。 1、 数据卷 数据卷是一个供容器使用的特殊目录&#xff0c;位于容器中。可将宿主机的目录挂载到数据卷上&#xff0c;对数据卷的修改操作立刻…...

RxJS处理异步数据流

什么是异步? 异步&#xff08;Asynchronous&#xff09;指的是不同步发生的事件或操作。通常&#xff0c;同步操作是指一系列代码按照顺序依次执行&#xff0c;直到当前代码块执行完毕后才继续执行下一个代码块&#xff1b;而异步操作则是指某些代码会被提交到后台执行&#…...

IP地址与用户行为

IP地址能够解决网络风险和提高网络安全的原因是&#xff1a;所有的网络请求都会带有IP信息&#xff0c;是访问者的独立标识&#xff0c;另外ip地址的分配和管理比较严格&#xff0c;难以造假。另外ip属于网络层&#xff0c;可以轻松的对其进行阻断。现有的各种网络安全、负载均…...

底层逻辑2

有些创业者&#xff0c;在3D打印⽕爆的时候做3D打印&#xff0c;在VR&#xff08;虚拟现 实&#xff09;蓬勃发展的时候转⾏做VR&#xff0c;在区块链成为热⻔话题的时候摇身⼀ 变成了区块链专家&#xff0c;⽽⼈⼯智能⽕了以后&#xff0c;他们⼜全身⼼投⼊⼈⼯智 能这⼀⾏。再…...

TCP报头详解及TCP十种核心机制(一)

目录 前言&#xff1a; TCP报头 TCP核心机制 一、确认应答 二、超时重传 小结&#xff1a; 前言&#xff1a; 这篇文章详细介绍了TCP报头中的一些核心数据&#xff0c;及两种TCP核心机制。其他的一些机制会在后面文章中详细介绍。 TCP报头 解释&#xff1a; 1&#xff…...

Linux用户的添加、修改和删除以及相关配置文件:useradd、passwd、usermod、userdel、相关配置文件

目录 账户的创建&#xff08;useradd&#xff09; 第一步&#xff1a;创建账号 第二步&#xff1a;创建密码 useradd参考文件 CROUP100 HOME/home INACTIVE-1 EXPIRE SHELL/bin/bash SKEL/etc/skel UID/GID密码参数参考&#xff1a;/etc/login.defs 密码参数显示命…...

进程地址空间

目录 回顾C/C语言的程序地址空间 感性认识虚拟地址空间 虚拟地址空间与物理空间如何建立映射关系 为什么要虚拟地址空间&#xff1f; 回顾C/C语言的程序地址空间 在学习C/C语言时我们知道了一个概念叫程序地址空间。通俗来说就是如下一张表&#xff0c;从中可以得知系统的几…...

数楼梯(加强版)

数楼梯(加强版) 题目背景: 小明一天放学回家,看到从1楼到2楼共有n个台阶,因为好奇,他想尝试一下总共有几种方案到二楼?他可以1步,2步,3步的跳,不能跳3步以上. 他试了很多次都没有解决这个问题,于是请求聪明的你帮忙解决这个问题. 题目描述: 1楼到2楼楼梯有n级台阶。小明每…...

MySQL-数据类型

数据类型简介数据表由多列字段构成&#xff0c;每一个字段指定了不同的数据类型&#xff0c;指定了数据类型之后&#xff0c;也就决定了向字段插入的数据内容。不同的数据类型也决定了 MySQL 在存储它们的时候使用的方式&#xff0c;以及在使用它们的时候选择什么运算符号进行运…...

剑指 Offer 32 - II. 从上到下打印二叉树 II(java解题)

剑指 Offer 32 - II. 从上到下打印二叉树 II&#xff08;java解题&#xff09;1. 题目2. 解题思路3. 数据类型功能函数总结4. java代码5. 踩坑记录1. 题目 从上到下按层打印二叉树&#xff0c;同一层的节点按从左到右的顺序打印&#xff0c;每一层打印到一行。 例如: 给定二叉…...

C#网络爬虫开发

1前言爬虫一般都是用Python来写&#xff0c;生态丰富&#xff0c;动态语言开发速度快&#xff0c;调试也很方便但是我要说但是&#xff0c;动态语言也有其局限性&#xff0c;笔者作为老爬虫带师&#xff0c;几乎各种语言都搞过&#xff0c;现在这个任务并不复杂&#xff0c;用我…...

Fastjson 总结

0x00 前言 这一篇主要是针对已经完成的fastjson系列做一个知识点总结&#xff0c;一来是为了更加有条理的梳理已经存在的内容&#xff0c;二来是为了更好的复习和利用。 0x01 Fastjson基础知识点 1.常见问题&#xff1a; 问&#xff1a;fastjson的触发点是什么&#xff1f;…...

文件路径模块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作用 简单来说安全相关一般涉及以下方面&#xff1a;用户认证&#xff08;Kerberos的作用&#xff09;、用户授权、用户管理.。而Kerberos功能是用户认证&#xff0c;通俗来说解决了证明A是A 的问题。 认证过程&#xff08;时序图&#xff09; 核心角色/概念 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的新特性–可变模版参数&#xff08;variadic templates&#xff09;是C11新增的最强大的特性之一&#xff0c;它对参数进行了高度泛化&#xff0c;它能…...

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 标注&#xff08;Icon&#xff09; require 引入图片问题环境版本Openlayers 使用 require 问题Webpack5 正确配置构建新环境的时候&#xff0c;偶然发现 Openlayers 使用 require 的方式加载图片&#xff08;Icon&#xff09;报错&#xff0c;开始…...

Zookeeper安装部署

文章目录Zookeeper安装部署Zookeeper安装部署 将Zookeeper安装包解压缩&#xff0c; [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 …...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版

1.题目描述 2.思路 当前的元素可以重复使用。 &#xff08;1&#xff09;确定回溯算法函数的参数和返回值&#xff08;一般是void类型&#xff09; &#xff08;2&#xff09;因为是用递归实现的&#xff0c;所以我们要确定终止条件 &#xff08;3&#xff09;单层搜索逻辑 二…...