蓝桥杯第1595题——和与乘积

2024-03-13 07:20
文章标签 蓝桥 乘积 1595

本文主要是介绍蓝桥杯第1595题——和与乘积,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

给定一个数列 A=(a1​,a2​,⋯,an​),问有多少个区间 [L,R] 满足区间内元素的乘积等于他们的和。

输入描述

输入第一行包含一个整数 n,表示数列的长度。

第二行包含 n 个整数,依次表示数列中的数 a1​,a2​,⋯,an​。

输出描述

输出仅一行,包含一个整数表示满足如上条件的区间的个数。

输入输出样例

示例

输入

4
1 3 2 2

输出

6

样例解释

符合条件的区间为 [1,1], [1,3], [2,2], [3,3], [3,4], [4,4]。

评测用例规模与约定

对于 20% 的评测用例,n ≤ 3000;

对于 50% 的评测用例,n ≤ 20000;

对于所有评测用例,1 ≤ n ≤ 200000,1 ≤ ai ​≤ 200000。

作者题解

通过题意可以知道,我们其实就是想要找到满足区间和等于区间积的区间个数,根据评测用例规模我们不难发现,如果暴力计算从任意一个数开始的任意长度的区间,一定会超时。

暴力计算除了超时,还有一个问题就是,乘积的变化是非常巨大的。虽然我们可以考虑到使用大数类,但不妨我们考虑一下,如果满足要求的结果是区间积等于区间和,那么如果从某个时刻起,区间积已经比理论区间和的最大值还要大了,是不是就可以停下来了,那么不难发现,理论区间和最大值就是2e5 * 2e5。

进一步思考,既然区间积的变化速度那么快,即便只有2,连续起来的增长速度也远超区间和的增长速度,而区间积的增长速度要想比区间和慢,使最终达到平衡,那就只有1这个值是满足要求的。

于是我们便可以从1这个数值开始考虑,我们不难发现,在新加入区间的数值里,如果加入1,会使得区间和变大,而区间积不变;如果加入其他数值,则不可控。这就给了我们启示,总结一下就是:

如果某个区间的区间和比区间积要小,那么只要在这个区间的左右两边填充足够数量的1,就可以使得区间和等于区间积。

由此我们便可以想到,什么样的区间可以在左右两边加1呢,我们只要收集所有不是1的数的下标,由此进行遍历查找,是不是就可以找到每个左右两边可以填充1的区间了。

区间和我们可以使用前缀和直接拿到,而只考虑非1的数还有一个好处,就是计算区间积的时候我们同样可以忽略1的存在,只对非1的数做乘法运算,因为乘1不会影响区间积。

编码思路

具体的,我们可以在读取数据的时候使用pre数组记录前缀和,便于我们计算区间和。

我们可以创建一个动态数组ArrayList记录所有不为1的数据下标;并且在其前面加上数值0,末尾加上数值n+1,其目的是为了方便计算整段数据首尾的1的个数。

ans的计算也尤为关键,假设我们查询的某个区间刚好区间和等于区间积,那么两侧加1都会导致区间和变大而区间积不变,此时两侧的1就是多余的,仅对ans做++运算即可。

假设此时我们区间和小于区间积,那么意味着可以通过两侧补1的方式实现相等,那么就要具体分析并分类讨论:

现在令左边有left个1,右边有right个1,而我们需要need个1。

如果左右两侧的1数量足够多,那么任意一侧都可以填充(0,1,2,...need)个1来满足要求,总共就是need+1个区间。

如果只有一侧的1数量足够多,那么1的数量较少的区间便成为了我们的限制,于是满足要求的区间数量就变成了min(left, right)+1个区间,原理跟上面的差不多。

那么如果两侧的1数量都不是足够多,但加起来又足以满足need,那么多出来的1的个数便成为了我们的限制;假设left+right刚好等于need,那么我们就只有一种区间选取方式,而不论任意一侧多余出来了一个1,我们可以选取的区间就有了左/右移动一个位置的可能性。

于是我们可以想到,在上述这种情况下,满足要求的区间数量为:left+right-need+1

具体代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;public class Main {public static void main(String[] args) throws Exception{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));String[] temp = in.readLine().split(" ");int n = Integer.parseInt(temp[0]);// data表示原始数据int[] data = new int[n + 1];// pre记录前缀和long[] pre = new long[n + 1];// list用于记录非1数据的下标ArrayList<Integer> list = new ArrayList<>();// 首部加0,尾部加n+1,是为了方便计算首尾1的个数list.add(0);temp = in.readLine().split(" ");for (int i = 1; i <= n; i++) {data[i] = Integer.parseInt(temp[i - 1]);pre[i] = pre[i - 1] + data[i];if (data[i] != 1) {list.add(i);}}list.add(n + 1);// 以下是具体算法部分long ans = 0;// 遍历list除了首尾部分的剩余内容,其指的是非1的数据下标for (int i = 1; i < list.size() - 1; i++) {// s表示的区间积// 每次遍历时,s都默认是i所在的位置值,并且先不考虑单个数构成的区间long s = data[list.get(i)];for (int j = i + 1; j < list.size() - 1; j++) {// 随着j每往后移动到一个新的不为1的位置,s需要进行更新s *= data[list.get(j)];// 如果s大于区间和理论最大值,就不必再计算了// 由于区间积的增长速度很快,所以这个优化很关键// 具体的说,可以使内层循环j的运行次数绝对低于log2(2e5 * 2e5),差不多是35左右if (s > 2e5 * 2e5) {break;}// sum记录当前考虑的不为1的数之间的区间和,注意细节不要写错long sum = pre[list.get(j)] - pre[list.get(i) - 1];if (sum <= s) {if (sum == s) { //如果sum刚好和区间积相等,满足要求的区间只会增加1个ans++;} else {    // 如果有多的,分类讨论// left记录左边1的个数,right记录右边1的个数,need表示需要1的个数int left = list.get(i) - list.get(i - 1) - 1;int right = list.get(j + 1) - list.get(j) - 1;long need = s - sum;if (left >= need && right >= need){         // 如果两侧的1都足够多,就有need+1种选取方式ans += need + 1;} else if (left >= need || right >= need) { // 如果只有一侧1足够多ans += Math.min(left, right) + 1;} else if (left + right >= need) {          // 如果两侧都不足够多,但加起来还是够用了ans += left + right - need + 1;}// 如果两侧加起来都不够need,那就直接忽略}}}}// 我们计算的时候忽略了所有单数据区间,而但数据区间一定满足要求,于是加上n进行输出System.out.println(ans + n);}
}

这篇关于蓝桥杯第1595题——和与乘积的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/804054

相关文章

C语言蓝桥杯

一、语言基础 竞赛常用库函数 最值查询 min_element和max_element在vector(迭代器的使用) nth_element函数的使用 例题lanqiao OJ 497成绩分析 第一种用min_element和max_element函数的写法 第二种用min和max的写法 二分查找 二分查找只能对数组操作 binary_s

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

Leetcode 152. 乘积最大子数组(Medium)

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续  子数组 (该子数组中至少包含一个数字),并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整数。 示例 1: 输入: nums = [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。 示例 2: 输入: nums = [-2,0,-1]输出: 0解释: 结果不能为 2,

找不同-第15届蓝桥省赛Scratch初级组真题第4题

[导读]:超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成,后续会不定期解读蓝桥杯真题,这是Scratch蓝桥杯真题解析第183讲。 如果想持续关注Scratch蓝桥真题解读,可以点击《Scratch蓝桥杯历年真题》并订阅合集,查阅教程更方便。 第15届蓝桥杯省赛已于2024年8月24日落下帷幕,编程题一共有5题,分别如下: 猪八戒落地 游乐场 画西瓜 找不同 消

【蓝桥杯嵌入式(一)程序框架和调度器】

蓝桥杯嵌入式(一)程序框架和调度器 序、代码命名规则零、STM32和8051⼀、软件及环境安装⼆、⼯程框架搭建1.时钟配置2、SYS配置3、⼯程配置4、NVIC配置5.、Keil配置 三、系统初始化四、任务调度器 链接: 视频出处 序、代码命名规则 以下是一些常见的举例 零、STM32和8051 链接: 8位和32位单片机最本质区别 ⼀、软件及环境安装

【蓝桥杯嵌入式(二)Led、Key、Lcd】

蓝桥杯嵌入式(二)Led、Key、Lcd 五、Led模块1.原理图配置2. 知识点3.底层代码 六、Key模块1.原理图配置2.知识点3.底层代码底层代码(四⾏代码版本)底层代码(状态机版本) 七、LCD模块1.原理图配置2.知识点底层代码 五、Led模块 1.原理图配置 2. 知识点 链接: 上拉电阻的通俗解释 链接: 单⽚机怎么输出⾼电平!推挽输出和开

张量乘积运算实例

a = torch.tensor([[1, 2, 2], [3, 4, 4]])b = torch.tensor([[1, 2, 2], [3, 4, 4], [5, 6, 6]]) 张量a的维度是2x3,张量b的维度是3x3。根据矩阵乘法的规则,a的列数(3)与b的行数(3)相等,所以这两个张量可以进行矩阵乘法运算。 矩阵乘法的结果c的维度将是a的行数乘以b的列数,即2x3矩阵乘以3x3

蓝桥杯:整数删除

// 蓝桥杯整数删除.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include<stdio.h>#define MAX 100void findmin(int a[],int n,int& pos){int min=a[0];pos=0;//pos=0我开始忘了,特别注意

第十五届蓝桥杯图形化省赛题目及解析

第十五届蓝桥杯图形化省赛题目及解析 一. 单选题 1. 运行以下程序,角色会说( )? A、29     B、31     C、33     D、35 正确答案:C 答案解析: 重复执行直到m>n不成立,即重复执行直到m<=n。所有当m小于或者 等于n时,循环结束。循环过程中变量m与变量n的变化如下表: 通过上述表格可知,循环到第五次循环结束。m的值为14,n的值为19

第八届蓝桥杯 最大公共子串(动态规划)

标题:最大公共子串 最大公共子串长度问题就是: 求两个串的所有子串中能够匹配上的最大长度是多少。 比如:"abcdkkk" 和 "baabcdadabc", 可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。 下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。 请分析该解法的思路,并补全划线部分缺失的代码。 #include <stdio.h