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

《蓝桥杯每日一题》 前缀和·Acwing 3956. 截断数组

1.题目

https://www.acwing.com/problem/content/3959/

给定一个长度为 n 的数组a1,a2,…,an。

现在,要将该数组从中间截断,得到三个非空子数组。

要求,三个子数组内各元素之和都相等。

请问,共有多少种不同的截断方法?

输入格式

第一行包含整数 n

第二行包含 n 个整数a1,a2,…,an。

输出格式

输出一个整数,表示截断方法数量。

数据范围

前六个测试点满足 1≤n≤10

所有测试点满足 1≤n≤10的五次方−10000≤ai≤10000

输入样例1:

4
1 2 3 3

输出样例1:

1

输入样例2:

5
1 2 3 4 5

输出样例2:

0

输入样例3:

2
0 0

输出样例3:

0

2.思路分析

既然要分配三个非空子数组,且值相同,那么不存在元素个数小于3,不存在原数组总和%3!=0的情况

pres[]为前缀和数组,perSum=原数组总和/3

那么我们只需要找到一个位置 pres[i]==perSum*2

此时res+=(pres[1~i-1]==averge)即可

因为第i位 满足2*perSum,pres[i+1~n]==perSum

所以只需要加上能使前i位的数组 分为 两个值为averge的位置 的数量即可

3.Ac代码


import java.io.*;public class Main {static int N=100010;public static void main(String[] args) throws IOException {int n;BufferedReader br=new BufferedReader(new InputStreamReader(System.in));n=Integer.parseInt(br.readLine());String []s=br.readLine().split(" ");int []arr=new int[N];//初始化初始数组for (int i = 1; i <=n; i++)   arr[i]=Integer.parseInt(s[i-1]);int []pres=new int[N];//求前缀和数组for (int i = 1; i <=n; i++)   pres[i]=pres[i-1]+arr[i];//如果个数小于3,或者前缀和不是3的倍数,那么无法截断if(n<3 ||pres[n]%3!=0){System.out.println("0");return;}long perSum=pres[n]/3,res=0,fir = 0,t=0;//要给最后一个元素留下了,给第三个截断用for (int i = 1; i <n; i++) {t=pres[i];if(t==perSum*2)  res+=fir;if(t==perSum)  fir++;//不能调换这两个if判断的原因是,如果当前t等于perSum和perSum*2时(比如0特判等),就会出现在同一位自加//一旦出现自加,那么可以理解为中间那个截断元素个数为0,这是不可能的}System.out.println(res);}
}
感谢你能看完, 如有错误欢迎评论指正,有好的思路可以交流一波,如果对你有帮助的话,点个赞支持下

相关文章:

《蓝桥杯每日一题》 前缀和·Acwing 3956. 截断数组

1.题目https://www.acwing.com/problem/content/3959/给定一个长度为 n 的数组a1,a2,…,an。现在&#xff0c;要将该数组从中间截断&#xff0c;得到三个非空子数组。要求&#xff0c;三个子数组内各元素之和都相等。请问&#xff0c;共有多少种不同的截断方法&#xff1f;输入…...

促进关键软件高层次人才培养:平凯星辰与华东师范大学签订联合博士培养合作协议

2022 年年初&#xff0c;平凯星辰入选首批工信部教育部支持联合培养国家关键软件高层次人才计划。该计划旨在探索关键软件产教融合育人模式&#xff0c;超常规加快培养一批急需高层次人才&#xff0c;以及探索关键软件联合技术攻关新模式。2022 年年底&#xff0c;在该计划下 平…...

Java程序员的日常——经验贴

关于文件的解压和压缩 如果你的系统不支持tar -z命令 前往讨论 如果是古老的Unix系统&#xff0c;可能并不认识tar -z命令&#xff0c;因此如果你想要压缩或者解压tar.gz的文件&#xff0c;就需要使用gzip或者gunzip以及tar命令了。 关于tar.gz可以这么理解&#xff0c;tar结…...

电商API社区,商品数据,关键词搜索等

1. 需要做的事情 l 商品详情页实现 1、商品查询服务事项 2、商品详情展示 3、添加缓存 2. 实现商品详情页功能 2.1. 功能分析 1、Taotao-portal接收页面请求&#xff0c;接收到商品id。 2、调用taotao-rest提供的商品详情的服务&#xff0c;把商品id作为参数传递给服务。接…...

LEADTOOLS 22.0.6 UPDATE-Crack

OCR SDK 库 许多 OCR 增强功能 LEAD 行业领先的人工智能 OCR SDK 在以下方面获得了显着的识别优化&#xff1a;斜体、大写和小写字母、文本行组装和单词构建、列检测、基线检测和文本行分割。 LEADTOOLS为.NET 6、. NET Framework、Xamarin、UWP、C#、VB、C/C、Java、Objective…...

什么是OJ? 东方博宜题库部分题解

什么是OJ ? Online Judge 比如这样的:Home - 一本通OJ Q:这个在线裁判系统使用什么样的编译器和编译选项? A:系统运行于Debian/Ubuntu Linux. 使用GNU GCC/G++ 作为C/C++编译器, C: gcc Main.c -o Main -fno-asm -O2 -Wall -lm --static -std=c99 -DONLINE_JUDGE C++: g++ …...

企业工程项目管理系统源码的各模块及其功能点清单

工程项目各模块及其功能点清单 一、系统管理 1、数据字典&#xff1a;实现对数据字典标签的增删改查操作 2、编码管理&#xff1a;实现对系统编码的增删改查操作 3、用户管理&#xff1a;管理和查看用户角色 4、菜单管理&#xff1a;实现对系统菜单的增删改查操…...

【电商开发手册】订单-下单

下单需求 所谓下单&#xff0c;本质上就是买卖双方通过确认一系列信息并且签订电子合同的过程 在电商平台的下单过程中&#xff0c;也需要确定买卖双方的一系列信息&#xff1a; 买方&#xff1a;用户确认收货地址、支付方式、配送方式等等 卖方&#xff1a;卖方需要进行供…...

数据结构 - 优先级队列(堆)

文章目录前言1.介绍优先级队列2. 认识堆3. 实现优先级队列3.1 了解优先级队列的构造方法&#xff1a;3.2 使用优先级队列解决问题&#xff1a;总结前言 本篇PriorityQueue优先级队列的介绍其底层是堆&#xff0c;关于堆的认识&#xff0c;使用优先级队列能解决的一些问题&…...

PDF内容提取器:ByteScout PDF Extractor SDK Crack

ByteScout PDF Extractor SDK – 用于 PDF 到 JSON、PDF 到 Excel、CSV、XML、从 .NET 和 ASP.NET 从 PDF 中提取文本的 PDF 提取器库 ByteScout PDF Extractor SDK – 用于 PDF 到 JSON、PDF 到 Excel、CSV、XML、从 .NET 和 ASP.NET 从 PDF 中提取文本的 PDF 提取器库​ ​ ​…...

字母板上的路径[提取公共代码,提高复用率]

提取公共代码前言一、字母版上的路径二、贪心1、idea2、go3、代码不断拆分复用的过程总结参考文献前言 写代码&#xff0c;在提高效率的同时&#xff0c;要方便人看&#xff0c;这个人包括自己。大函数要拆分成一些小函数&#xff0c;让每个函数的宏观目的和步骤都显得清晰&am…...

c# winform错误大全

c# winform 错误大全为了实现安装包安装完成后&#xff0c;启动程序。System.BadImageFormatException: 未能加载文件或程序集“file:///C:\xxxxxxxxx\xxxxxxx.exe”或它的某一个依赖项。生成此程序集的运行时比当前加载的运行时新&#xff0c;无法加载此程The version of the …...

AI_News周刊:第一期

2023.02.06—2023.02.12 关于ChatGPT的前言&#xff1a; 在去年年末&#xff0c;OpenAI的ChatGPT在技术圈已经火了一次&#xff0c;随着上周它的二次出圈&#xff0c;ChatGPT算得上是人工智能领域的一颗明星&#xff0c;它在聊天机器人领域有着不可忽视的影响力。其准确、快速…...

搭建mysql主从复制

前言&#xff1a; &#x1f44f; 作者简介&#xff1a;我是笑霸final&#xff0c;一名热爱技术的在校学生。 &#x1f4dd; 个人主页&#xff1a;个人主页1 || 笑霸final的主页2 &#x1f4d5; 系列专栏&#xff1a;数据库 &#x1f4e7; 如果文章知识点有错误的地方&#xff0…...

内存溢出、内存泄露的概述及常见情形

内存溢出&#xff08;OutofMemoryError&#xff09; 简述 java doc 中对 Out Of Memory Error 的解释是&#xff0c;没有空闲内存&#xff0c;并且垃圾收集器也无法提供更多内存。 JVM 提供的内存管理机制和自动垃圾回收极大的解放了用户对于内存的管理&#xff0c;由于 GC&…...

Linux 中断实验

目录 一、Linux 中断简介 上半部与下半部 二、添加设备树 三、编写驱动 1、定义宏 2、编写一个key结构体 3、imx6uirq设备添加成员 ​编辑4、按键中断处理函数 5、按键初始化 6、在驱动入口添加初始化 7、 驱动出口函数 代码如下 四、利用定时器进行消抖处理 1、添…...

【c++】指针

文章目录指针的定义和使用指针所占的内存空间空指针野指针const修饰指针指针和数组指针和函数指针、数组、函数案例&#xff1a;冒泡排序指针的定义和使用 指针定义的语法&#xff1a;数据类型 * 指针变量名 使用指针&#xff1a; 可以通过解引用的方式来找到指针指向的内存&…...

别具一格的婚礼,VR全景+婚礼的优势展现在哪里?

随着90后、95后逐渐步入结婚的主力军中&#xff0c;如何策划一场别具一格的婚礼是许多年轻人所头疼的&#xff0c;那么今年我们就可以玩点新潮的&#xff0c;VR婚礼或许是个不错的选择。 VR全景婚礼就是通过全景摄像机对婚礼进行记录&#xff0c;不但可以帮助新人捕捉婚礼的精彩…...

【GD32F427开发板试用】5. SPI驱动TFTLCD屏幕

本篇文章来自极术社区与兆易创新组织的GD32F427开发板评测活动&#xff0c;更多开发板试用活动请关注极术社区网站。作者&#xff1a;hehung 之前发帖 【GD32F427开发板试用】1. 串口实现scanf输入控制LED 【GD32F427开发板试用】2. RT-Thread标准版移植 【GD32F427开发板试用…...

测试2年还拿实习生的薪资打发我,你后悔去吧····

20年7月大学毕业&#xff0c;学的计算机科学专业。因为考研之后&#xff0c;秋招结束了。没什么更多的岗位选择&#xff0c;就想找个工作先干着&#xff0c;然后亲戚在一家大厂公司上班说要招测试&#xff0c;所以就来做测试了。 虽然都是属于计算机大类&#xff0c;但自己专业…...

AWPortrait-Z人像美化效果展示:科哥版WebUI实测,让普通人像变专业级

AWPortrait-Z人像美化效果展示&#xff1a;科哥版WebUI实测&#xff0c;让普通人像变专业级 1. 效果总览&#xff1a;从普通到专业的蜕变 1.1 什么是真正的人像美化&#xff1f; 传统美颜软件往往采用"一刀切"的处理方式&#xff1a;过度磨皮、夸张大眼、强行瘦脸…...

Unity3D毕业设计新手入门:从零构建可交付的2D游戏项目

最近在帮学弟学妹们看Unity毕业设计项目&#xff0c;发现一个挺普遍的现象&#xff1a;很多同学虽然能实现各种炫酷的功能&#xff0c;但项目内部却像一锅“意大利面”——脚本相互引用、资源乱放、场景一打开就卡顿&#xff0c;答辩演示时还容易出各种意外。这其实不是技术问题…...

Java PPT自动化:从数据到演示文稿的智能生成

1. 为什么需要Java PPT自动化&#xff1f; 想象一下这样的场景&#xff1a;每周五下午&#xff0c;市场部的同事都会准时发来一封邮件&#xff0c;要求你根据本周的销售数据生成一份PPT报告。数据来自CRM系统&#xff0c;包含几十个SKU的销售额、增长率、区域分布等信息。你需要…...

Qwen3-0.6B-FP8辅助计算机组成原理教学:概念解释与习题辅导

Qwen3-0.6B-FP8辅助计算机组成原理教学&#xff1a;概念解释与习题辅导 计算机组成原理这门课&#xff0c;很多同学一听到就有点头疼。流水线、缓存一致性、指令周期……这些概念听起来就抽象&#xff0c;课本上的解释又常常是长篇大论&#xff0c;看几遍还是云里雾里。自己做…...

Gigasoft ProEssentials 使AI助手能够通过实时访问API图表配置并提供支持答案

利用人工智能访问改进图表开发Gigasoft ProEssentials 使 AI 助手能够通过实时访问 API 生成精确的图表配置并提供支持答案。Gigasoft ProEssentials 是一款功能强大的 Windows 开发图表库&#xff0c;提供丰富的 2D 和 3D 图表类型。该产品提供了一套用途广泛的组件&#xff0…...

GBase 8c数据库权限管理场景实践 分享

环境要求项目参数目标数据库turboex数据库端口15400测试用户turboserver / turbolog测试模式test_privileges环境准备-- 清理旧环境gsql -r -d postgres -p 15400clean connection to all force for database turboex;drop database if exists turboex;drop user if exists tur…...

python沉浸式戏曲文化体验系统vue3

目录 系统架构设计前端实现方案后端Python服务沉浸式体验关键技术开发里程碑计划测试策略部署方案 项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作 系统架构设计 采用前后端分离架构&#xff0c;前端使用Vue3TypeScriptPinia构…...

如何用3个智能体协作,让你的工作效率提升10倍?

如何用3个智能体协作&#xff0c;让你的工作效率提升10倍&#xff1f; 【免费下载链接】eigent Eigent: The Worlds First Multi-agent Workforce to Unlock Your Exceptional Productivity. 项目地址: https://gitcode.com/GitHub_Trending/ei/eigent 你是否曾经有过这…...

无人机像果蝇一样思考:上交大『可微分物理』避障原理通俗解读

无人机避障的仿生智慧&#xff1a;从果蝇视觉到可微分物理的工程突破 当一只果蝇以每秒10次的频率在枝叶间穿梭时&#xff0c;它那仅由800个复眼组成的视觉系统&#xff0c;却能处理比最先进无人机更复杂的动态避障任务。这种自然界的高效解决方案&#xff0c;正在重塑机器人感…...

SDMatte前端面试题实战:如何实现一个高性能的图片上传与预览组件

SDMatte前端面试题实战&#xff1a;如何实现一个高性能的图片上传与预览组件 1. 场景需求与技术挑战 在电商、设计平台等实际业务中&#xff0c;图片上传与处理是高频核心功能。以SDMatte智能抠图工具为例&#xff0c;用户需要上传产品图片进行背景去除&#xff0c;但面临几个…...