首页 > 其他分享 >蓝桥杯2022年第十三届省赛真题-数组切分

蓝桥杯2022年第十三届省赛真题-数组切分

时间:2023-02-22 00:44:06浏览次数:47  
标签:2022 真题 int 自然数 蓝桥 切分 连续 数组 一段

已知一个长度为 N 的数组:A1, A2, A3, ...AN 恰好是 1 ∼ N 的一个排列。现在要求你将 A 数组切分成若干个 (最少一个,最多 N 个) 连续的子数组,并且每个子数组中包含的整数恰好可以组成一段连续的自然数。

例如对于 A = {1, 3, 2, 4}, 一共有 5 种切分方法:

{1}{3}{2}{4}:每个单独的数显然是 (长度为 1 的) 一段连续的自然数。

{1}{3, 2}{4}:{3, 2} 包含 2 到 3,是 一段连续的自然数,另外 {1} 和 {4} 显然也是。

{1}{3, 2, 4}:{3, 2, 4} 包含 2 到 4,是 一段连续的自然数,另外 {1} 显然也是。

{1, 3, 2}{4}:{1, 3, 2} 包含 1 到 3,是 一段连续的自然数,另外 {4} 显然也是。

{1, 3, 2, 4}:只有一个子数组,包含 1 到 4,是 一段连续的自然数。

 

先准备输入代码,n是数字数组长度,nums以1到n为索引方便辨认

int MOD = 1000000007;
// 输入数据
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n+1];
for (int i = 1; i <= n; i++) {
    nums[i] = sc.nextInt();
}    

使用动态规划定义数组f[n+1] f[0] = 1;

使用索引i表示以i结尾的区间的切分方式数

 

i是开始切分的left索引,j是right索引,如果区间长度等于区间内最大值和最小值得差,则说明连续,可以让以j结尾的方法数加上i-1的方法数

 

int[] f = new int[n+1];
f[0] = 1;
for(int i=1; i<=n;i++){
    int max = nums[i];
    int min = nums[i];
    for(int j=i;j<=n;j++){
        max = Math.max(max,nums[j]);
        min = Math.min(min,nums[j]);
        if(j - i + 1 == max - min + 1){
            f[j] = (f[j]+f[i-1])%MOD;
        }
    }
}

 

标签:2022,真题,int,自然数,蓝桥,切分,连续,数组,一段
From: https://www.cnblogs.com/zhexian233/p/17143018.html

相关文章

  • 中南大学CSU2022-2023级C语言期中考试机试答案
    卡在出线概率了。40%,没想到遍历时反了,我去。 1.时钟加法1#include<stdio.h>23#include<string.h>45#include<stdlib.h>67#include<math.h>8#d......
  • 2023 IDEA 2022.3.2 最新激活教程、亲测有效,永久激活
    更新时间2023-02-1016:40:51申明:本教程IntelliJIDEA激活补丁、激活码均收集于网络,请勿商用,仅供个人学习使用,如有侵权,请联系作者删除。若条件允许,希望大家购买正版!PS:......
  • 2023.2.21AcWing蓝桥杯集训·每日一题
    知识点为二分。AcWing113.特殊排序题目描述有\(N\)个元素,编号\(1,2..N\),每一对元素之间的大小关系是确定的,关系具有反对称性,但不具有传递性。注意:不存在两个元素大......
  • 2022年网络安全政策态势分析与2023年立法趋势
    近日,公安部第三研究所网络安全法律研究中心与360集团法务中心联合共同发布了《全球网络安全政策法律发展年度报告(2022)》。《报告》概览2022年全球网络安全形势与政策法律......
  • 2022年中国前10电商GMV总结
    我是卢松松,点点上面的头像,欢迎关注我哦!1,阿里8万亿;2,京东3万亿;3,拼多多3万亿;4,小程序私域电商3万亿;5,抖音电商1.4万亿。6,抖音本地生活服务电商600亿。7,美团1万亿;8,快手电商70......
  • React-Hooks怎样封装防抖和节流-面试真题
    Debouncedebounce原意消除抖动,对于事件触发频繁的场景,只有最后由程序控制的事件是有效的。防抖函数,我们需要做的是在一件事触发的时候设置一个定时器使事件延迟发生,在......
  • 2022-03-29 测试
    关于啊哈哈哈哈暂时没有关于23221.带{%u下划线%}的文本带{%emp着重号%}的文本带{%wavy波浪线%}的文本带{%del删除线%}的文本键盘样式的......
  • 第九届蓝桥杯题解
    第九届蓝桥杯题解A,第几天packagetrain;publicclasstest_27{publicstaticvoidmain(String[]args){System.out.println(31+29+31+30+4);}}......
  • 2022.2.20学习总结
    今天老师花了三节课多,也算得上是给我们打了一针鸡血,也明确的指明了我们下个阶段的学习目标,我是一个十分清楚自己想要得到什么,当下该做一些什么的人,我也找到了我下一个阶段......
  • P8292 [省选联考 2022] 卡牌
    我决定不整什么写过的题的集合了,写不过来。想到啥题好就写啥。这题是个很好的套路。考虑到值域不怎么大,想到根号分治。也就是小于根号的质数不超过\(14\)个,大于根号的......