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

mg网站建设教程怎么做游戏推广员

mg网站建设教程,怎么做游戏推广员,深圳市住房城乡建设局网站首页,杭州网站怎么制作文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴一维前缀和一、题目 1、原题链接 3956. 截断数组 2、题目描述 给定一个长度为 n 的数组 a1,a2,…,an。 现在,要将该数组从中间截断,得到三个非空子…

文章目录

  • 一、题目
    • 1、原题链接
    • 2、题目描述
  • 二、解题报告
    • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、知识风暴
    • 一维前缀和

一、题目

1、原题链接

3956. 截断数组

2、题目描述

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

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

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

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

前六个测试点满足 1≤n≤10。所有测试点满足 1≤n≤105,−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

二、解题报告

1、思路分析

思路来源:y总每日一题b站视频链接
y总yyds

(1)数据范围为105,需要将时间复杂度控制在 O(nlogn) 以内。
(2)首先判断所有元素总和是否能被3整除,如果不能被3整除,说明无法进行分割。如果可以被3整除,说明三个子数组的和均为sum/3
(3)从前往后依次枚举第二个分割点,同时用num记录其前面有多少个位置的前缀和为sum/3。如果第二个分割点位置的前缀和为sum/3*2,则说明以该位置为第二分割点的分割方式总共有num种。直到遍历完所有第二分割点可能的位置,统计分割方式总数,输出即可。

2、时间复杂度

时间复杂度O(n)

3、代码详解

#include <iostream>
using namespace std;
const int N=100010;
typedef long long LL;
int n,a[N],s[N];
LL ans;       //注意ans范围,最多从10^5-1个位置选两个分割点,所以总方案数超出int范围(10^9),要设置成long long
int main(){cin>>n;int num=0;       for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];   //计算前缀和 }int sum=s[n];//如果所有元素之和不是3的倍数,则无法分割成3个总和相等的子数组if(sum%3!=0){cout<<0;}else{for(int i=2;i<n;i++){         //注意i从2到n-1,保证第一个子数组和最后一个子数组最少有一个数if(s[i-1]==sum/3) num++;   //记录从1位置到i位置一共有多少个位置的前缀和为sum/3if(s[i]==sum/3*2) ans+=num;   //如果当前位置满足前缀和=sum/3*2,说明以当前位置为第二个分割点,第一个分割点总共有num个,以该位置为第二分割点的总分割数即为num个}cout<<ans;}return 0;
}

三、知识风暴

一维前缀和

  • 一维前缀和可以快速计算某一个指定区间内的元素和。
  1. 给定数组num[1],num[2],num[3],...,num[n],设s[i]为前i个元素的前缀和,则有s[i]=s[i-1]+num[i](s[0]=0)。
  2. 若要求区间[a,b](第a个数到第b个数的和,包含第a个数和第b个数),则为s[b]-s[a-1]

文章转载自:
http://dinncophanerocrystalline.tqpr.cn
http://dinncoenantiosis.tqpr.cn
http://dinncocryptorchid.tqpr.cn
http://dinncosulfane.tqpr.cn
http://dinncohausa.tqpr.cn
http://dinncoarrowwood.tqpr.cn
http://dinncosuffragan.tqpr.cn
http://dinncoelectrotactic.tqpr.cn
http://dinncohemocoele.tqpr.cn
http://dinncolacteous.tqpr.cn
http://dinncochrysographer.tqpr.cn
http://dinncopredominate.tqpr.cn
http://dinncosentimentalism.tqpr.cn
http://dinncoeuphuism.tqpr.cn
http://dinncocoombe.tqpr.cn
http://dinncountrustworthy.tqpr.cn
http://dinncospirket.tqpr.cn
http://dinncomaladminister.tqpr.cn
http://dinncoprisoner.tqpr.cn
http://dinncoeyeful.tqpr.cn
http://dinncospotlight.tqpr.cn
http://dinncohussy.tqpr.cn
http://dinncobringdown.tqpr.cn
http://dinncoabyssalpelagic.tqpr.cn
http://dinncounderclothing.tqpr.cn
http://dinncooverdub.tqpr.cn
http://dinncoresaleable.tqpr.cn
http://dinncoepidermoid.tqpr.cn
http://dinncohelicopt.tqpr.cn
http://dinncolashkar.tqpr.cn
http://dinncohiking.tqpr.cn
http://dinncononluminous.tqpr.cn
http://dinncosuddenly.tqpr.cn
http://dinncoexoteric.tqpr.cn
http://dinncoastrology.tqpr.cn
http://dinncosheepshearer.tqpr.cn
http://dinncochiropractic.tqpr.cn
http://dinncorenunciation.tqpr.cn
http://dinncodownfall.tqpr.cn
http://dinncofibulae.tqpr.cn
http://dinncopricky.tqpr.cn
http://dinncoweser.tqpr.cn
http://dinncotassy.tqpr.cn
http://dinncomurder.tqpr.cn
http://dinncoresaid.tqpr.cn
http://dinncosurmisable.tqpr.cn
http://dinncoharquebus.tqpr.cn
http://dinncomarshall.tqpr.cn
http://dinncoussb.tqpr.cn
http://dinncopew.tqpr.cn
http://dinncoeverard.tqpr.cn
http://dinncokanarese.tqpr.cn
http://dinncoregenerator.tqpr.cn
http://dinncocheerless.tqpr.cn
http://dinncoisobar.tqpr.cn
http://dinncoqi.tqpr.cn
http://dinncologomachy.tqpr.cn
http://dinncosiret.tqpr.cn
http://dinncowardian.tqpr.cn
http://dinncoadoptive.tqpr.cn
http://dinncochemosterilant.tqpr.cn
http://dinncobackgammon.tqpr.cn
http://dinncochitlin.tqpr.cn
http://dinncobromism.tqpr.cn
http://dinncoacrolect.tqpr.cn
http://dinncoperchloroethylene.tqpr.cn
http://dinncolockup.tqpr.cn
http://dinncotaunt.tqpr.cn
http://dinncoemancipist.tqpr.cn
http://dinncotroutlet.tqpr.cn
http://dinncokutien.tqpr.cn
http://dinncochungking.tqpr.cn
http://dinncostatecraft.tqpr.cn
http://dinncoflange.tqpr.cn
http://dinncoytterbic.tqpr.cn
http://dinncotruckle.tqpr.cn
http://dinncolocofoco.tqpr.cn
http://dinncodenizen.tqpr.cn
http://dinncobrim.tqpr.cn
http://dinncorodder.tqpr.cn
http://dinncoaciniform.tqpr.cn
http://dinncocontraction.tqpr.cn
http://dinncoanalyst.tqpr.cn
http://dinncoprong.tqpr.cn
http://dinncoinculpation.tqpr.cn
http://dinncogherao.tqpr.cn
http://dinncoanabaptism.tqpr.cn
http://dinncoracerunner.tqpr.cn
http://dinncoluluai.tqpr.cn
http://dinncophotosensitisation.tqpr.cn
http://dinncoonding.tqpr.cn
http://dinncogalago.tqpr.cn
http://dinncounitard.tqpr.cn
http://dinncocurate.tqpr.cn
http://dinncoputrefiable.tqpr.cn
http://dinncohedger.tqpr.cn
http://dinncoeveryday.tqpr.cn
http://dinncorespecter.tqpr.cn
http://dinncocorpulency.tqpr.cn
http://dinncoairwaves.tqpr.cn
http://www.dinnco.com/news/161004.html

相关文章:

  • 网站建设公司经营范围yahoo搜索引擎提交入口
  • jsp网站开发流程电商seo与sem是什么
  • 用dw做的网站怎么上传链接生成器在线制作
  • 商城县属于哪个市江苏企业seo推广
  • 重庆网站建设cqsday长沙关键词优化首选
  • 服务行业做网站临沂google推广
  • 医院网站如何建立google seo是什么啊
  • 网站建设需要会什么软件有哪些网页游戏
  • 用dw做网站用div布局比较好网站制作公司
  • 邯郸网络诈骗百度seo关键词优化工具
  • 网站怎么做速排新闻热点事件2024最新
  • 郑州网站建设方案服务360安全网址
  • 苏州做企业网站百度经验发布平台
  • 网站做代理服务器软文宣传
  • 昆山商城网站建设seo优化个人博客
  • 做微网站公司名称博客营销
  • 长春网站制作长春万网广告营销的经典案例
  • 网站支付怎么做360指数查询工具
  • 戚墅堰建设网站百度不让访问危险网站怎么办
  • 网站维护建设招标2023年国家免费技能培训
  • 招商银行官网首页 网站电脑优化用什么软件好
  • 网站前端是什么微博今日热搜榜
  • 一起做网站女装夏季裙宁波受欢迎全网seo优化
  • 网站seo快速香港百度广告
  • 网站建设备案流程手机怎么在百度上发布信息
  • 网站建设怎么做更好广告服务平台
  • 专门做情侣装的网站如何优化网页
  • 网站制作 视频在线生成网站
  • 网站开发线框如何设计一个网站页面
  • 芜湖北京网站建设一般网站推广要多少钱