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

蓝桥杯真题2

[蓝桥杯 2013 省 B] 连号区间数

题目描述

小明这些天一直在思考这样一个奇怪而有趣的问题:

111 ~ NNN 的某个全排列中有多少个连号区间呢?这里所说的连号区间的定义是:

如果区间 [L,R][L, R][L,R] 里的所有元素(即此排列的第 LLL个到第 RRR 个元素)递增排序后能得到一个长度为 R−L+1R-L+1RL+1 的“连续”数列,则称这个区间连号区间。

NNN 很小的时候,小明可以很快地算出答案,但是当 NNN 变大的时候,问题就不是那么简单了,现在小明需要你的帮助。

输入格式

第一行是一个正整数 N(1≤N≤50000)N (1 \le N \le 50000)N(1N50000), 表示全排列的规模。

第二行是 NNN 个不同的数字 Pi(1≤Pi≤N)P_i(1 \le P_i \le N)Pi(1PiN), 表示这 NNN 个数字的某一全排列。

输出格式

输出一个整数,表示不同连号区间的数目。

样例 #1

样例输入 #1

4
3 2 4 1

样例输出 #1

7

样例 #2

样例输入 #2

5
3 4 2 5 1

样例输出 #2

9

提示

第一个用例中,有 777 个连号区间分别是:[1,1][1,1][1,1], [1,2][1,2][1,2], [1,3][1,3][1,3], [1,4][1,4][1,4], [2,2][2,2][2,2], [3,3][3,3][3,3], [4,4][4,4][4,4]

第二个用例中,有 999 个连号区间分别是:[1,1][1,1][1,1], [1,2][1,2][1,2], [1,3][1,3][1,3], [1,4][1,4][1,4], [1,5][1,5][1,5], [2,2][2,2][2,2], [3,3][3,3][3,3], [4,4][4,4][4,4], [5,5][5,5][5,5]

原题时限 5 秒, 64M。蓝桥杯 2013 年第四届省赛

分析

题目要求的是连续号区间数,因为这个题目的数据有个特点,就是数据不重复,所以如果说某个区间是连续的,那么这个区间的最大值-最小数必须等于下标差即(max-min==b-a)如果满足这个,则说明(a,b)为连续区间,将res++即可。那么如何求取每个区间的最大和最小值呢,我们不妨定下l,不断地去枚举r,这样我们只需要每次比较最大最小值和新加入元素的大小即可。

代码实现

import java.util.*;
public class Main{static int N = 10010;static int[] a = new int[N];public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();for(int i = 1; i <= n;i++) a[i]=scan.nextInt();int res = 0;for(int i = 1;i <= n;i++){int minv = Integer.MAX_VALUE;int maxv = Integer.MIN_VALUE;for(int j = i;j <= n;j++){minv = Math.min(minv, a[j]);maxv = Math.max(maxv, a[j]);if(maxv - minv == j - i) res ++;}}System.out.println(res);}
}

[蓝桥杯 2015 省 A] 饮料换购

题目描述

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C 型饮料,凭 333 个瓶盖可以再换一瓶 C 型饮料,并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下,如果小明不浪费瓶盖,尽量地参加活动,那么,对于他初始买入的 nnn 瓶饮料,最后他一共能喝到多少瓶饮料。

输入格式

一个整数 nnn,表示开始购买的饮料数量。(0<n<100000<n<100000<n<10000

输出格式

一个整数,表示实际得到的饮料数。

样例 #1

样例输入 #1

100

样例输出 #1

149

样例 #2

样例输入 #2

101

样例输出 #2

151

提示

2015 年蓝桥杯省赛 A 组 H 题。

分析

这道题主要是要求思路清晰,直接去算就可以,先喝完手中的饮料,res+=n,剩下n个瓶盖,三个饮料盖可以换一瓶饮料,那么我们就又可以喝n/3瓶饮料,每次我们喝过饮料后会剩下 n/3+n%3个瓶盖,我们只需要不断重复过程,直至n<3

代码实现

import java.util.*;
public class Main{public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();int res = n;while(n>=3){res+=n/3;n = n / 3 + n%3;}System.out.println(res);}
}

[蓝桥杯 2014 省 AB] 地宫取宝

题目描述

X 国王有一个地宫宝库。是 n×mn \times mn×m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角,出口在右下角。

小明被带到地宫的入口,国王要求他只能向右或向下行走。

走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。

当小明走到出口时,如果他手中的宝贝恰好是 kkk 件,则这些宝贝就可以送给小明。

请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 kkk 件宝贝。

输入格式

输入一行 333 个整数,用空格分开:nnnmmmk(1≤n,m≤50,1≤k≤12)k(1 \le n,m \le 50,1 \le k \le 12)k(1n,m50,1k12)

接下来有 nnn 行数据,每行有 mmm 个整数 Ci(0≤Ci≤12)C_i(0 \le C_i \le 12)Ci(0Ci12) 代表这个格子上的宝物的价值。

输出格式

要求输出一个整数,表示正好取 kkk 个宝贝的行动方案数。该数字可能很大,输出它对 1000000007(109+7)1000000007(10^9+7)1000000007(109+7) 取模的结果。

样例 #1

样例输入 #1

2 2 2
1 2
2 1

样例输出 #1

2

样例 #2

样例输入 #2

2 3 2
1 2 3
2 1 5

样例输出 #2

14

提示

时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛

分析

很明显的dp问题,我们将每个状态划分:

当走到某个格子上的时候:
(1)如果格子上宝贝的价值大于已有宝贝的最大值,那么可以选择拿或者不拿
(2)如果格子上宝贝的价值小于或者等于已有宝贝的最大值,那么只能选择不拿。
必须从左上角走到右下角,且只要到达右下角时物品个数满足条件即算一种方案。
只能选择向下或者向右走
不是必须到出口时,宝贝数量恰好满足条件,而是可以在任意位置就宝贝数量就可以满足条件,只需保证到达出口时宝贝数量仍然满足条件即可

import java.util.Scanner;public class Main {public static void main(String[] args) {int N = 55;int w[][] = new int[N][N];int f[][][][] = new int[N][N][13][14];//所有从起点走到(i, j),且已经取了k件物品,且最后一件物品的价值是C的合法方案的集合。int mod = 1000000007;Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int k = sc.nextInt();for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {w[i][j] = sc.nextInt();w[i][j]++;//为了初始化,因为最终统计的是方法数}}f[1][1][1][w[1][1]] = 1;f[1][1][0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if(i==1 && j==1) continue;for (int u = 0; u <= k; u++) {for (int v = 0; v <= 13; v++) {f[i][j][u][v] = (f[i][j][u][v]+f[i-1][j][u][v])%mod;//最后一步是从上往下走,并且不取这个宝贝f[i][j][u][v] = (f[i][j][u][v]+f[i][j-1][u][v])%mod;//最后一步是从左往右走,并且不取这个宝贝if(u>0 && v==w[i][j])当前的方案数量=上一步的所有价值的方案数量之和{for (int c = 0; c < v; c++) {f[i][j][u][v] = (f[i][j][u][v] + f[i-1][j][u-1][c])%mod;//最后一步是从上往下走,并且取这个宝贝f[i][j][u][v] = (f[i][j][u][v] + f[i][j-1][u-1][c])%mod;//最后一步是从左往右走,并且不取这个宝贝}}}}}}int res = 0;for (int i = 0; i <= 13; i++) {res = (res + f[n][m][k][i])%mod;}System.out.println(res);}
}

相关文章:

蓝桥杯真题2

[蓝桥杯 2013 省 B] 连号区间数 题目描述 小明这些天一直在思考这样一个奇怪而有趣的问题&#xff1a; 在 111 ~ NNN 的某个全排列中有多少个连号区间呢&#xff1f;这里所说的连号区间的定义是&#xff1a; 如果区间 [L,R][L, R][L,R] 里的所有元素&#xff08;即此排列的…...

PWM互补输出,以及死区时间计算

本文基于野火例程进行解说 实验内容 本次实验输出一对互补的pwm波&#xff0c;且进行死区时间的计算说明。 代码 互补输出对应的定时器初始化代码&#xff1a; bsp_advance_tim.c /********************************************************************************* fi…...

基于深度学习的海洋动物检测系统(Python+YOLOv5+清新界面)

摘要&#xff1a;基于深度学习的海洋动物检测系统使用深度学习技术检测常见海洋动物&#xff0c;识别图片、视频和实时视频中的海洋动物&#xff0c;方便记录、展示和保存结果。本文详细介绍海洋动物检测系统&#xff0c;在介绍算法原理的同时&#xff0c;给出Python的实现代码…...

C# 计算方差

50&#xff0c;100&#xff0c;100&#xff0c;60&#xff0c;50 计算他们的方差 为了计算这些数的方差&#xff0c;需要进行以下步骤&#xff1a; 1. 计算平均值&#xff0c;即将这些数相加&#xff0c;然后除以它们的数量。 平均值 (50 100 100 60 50) / 5 72 2. 计…...

HJZS电源监视继电器HJZS-E202 AC220V

系列型号&#xff1a; HJZS-E202断电延时继电器 HJZS-E002断电延时继电器 一 应用 HJZS-E202电源监视继电器用于直流或交流操作的各种保护和自动控制的装置中&#xff0c;用以增加触点数量。 二 安装结构 导轨安装9壳体结构&#xff0c;具体尺寸参阅外型尺寸图。 三 产品型号…...

dolphinscheduler 2.0.6 资源中心改造方案二:通过NFS挂载共享目录

目录调度资源中心存储概要安装NFS服务器客户端调度验证关闭SFTP开关&#xff08;可忽略&#xff09;重新上传资源文件worker执行任务验证服务器woker客户端worker其它nfs共享目录的配置文件/etc/exports说明调度资源中心存储概要 针对现有的单机存储可以做哪些扩展&#xff1f;…...

基于集成学习的用户流失预测并利用shap进行特征解释

基于集成学习的用户流失预测并利用shap进行特征解释 小P&#xff1a;小H&#xff0c;如果我只想尽可能的提高准确率&#xff0c;有什么好的办法吗&#xff1f; 小H&#xff1a;优化数据、调参侠、集成学习都可以啊 小P&#xff1a;什么是集成学习啊&#xff0c;听起来就很厉害的…...

【Java版oj 】 day17杨辉三角形的变形、计算某字符出现次数

目录 一、杨辉三角形的变形 &#xff08;1&#xff09;原题再现 &#xff08;2&#xff09;问题分析 &#xff08;3&#xff09;完整代码 二、计算某字符出现次数 &#xff08;1&#xff09;原题再现 &#xff08;2&#xff09;问题分析 &#xff08;3&#xff09;完整代…...

智能驾驶芯片赛道混战:如何看待5类玩家的竞争格局?

智能驾驶芯片赛道&#xff0c;一直是业内关注的焦点。 高工智能汽车注意到&#xff0c;针对L0-L2&#xff0c;业内基本采用智能前视一体机&#xff08;IFC&#xff09;方案&#xff1b;要实现高速NOA、城市NOA等更为高阶的智驾功能等&#xff0c;则基本采用域控制器方案。从IF…...

vue antd table表格的增删改查(三)input输入框根据关键字模糊查询【后台管理系统 使用filter与indexOf嵌套】

vue antd table表格的增删改查&#xff08;三&#xff09;input输入框根据关键字查询【后台管理系统filter与indexOf嵌套】知识回调场景复现利用filter和indexOf方法实现模糊查询1.查询对象为单层的数组元素2.查询对象为多层的数组元素&#xff08;两层为例&#xff09;3.查询对…...

【计组】性能指标——速度

衡量计算机性能的指标之一——速度&#xff0c;是指计算机执行完所有指令所耗费时间的长短。 一、概念&#xff1a; 引出了如下概念&#xff1a;机器字长&#xff1a;指计算机一次能处理的二进制位数&#xff0c;也就是我们通常说的32位64位计算机中的位。 机器字长决定了计算…...

【PC自动化测试-4】inspect.exe 详解

1&#xff0c;inspect.exe图解" 检查 "窗口有几个主要部分&#xff1a;● 标题栏。 显示" 检查 HWND (窗口句柄) 。● 菜单栏。 提供对 检查功能 的访问权限。● 工具 栏。 提供对 检查功能 的访问权限。● 树视图。 将 UI 元素的层次结构呈现为树视图控件&…...

比肩ChatGPT的国产AI:文心一言——有话说

&#x1f517; 运行环境&#xff1a;chatGPT&#xff0c;文心一言 &#x1f6a9; 撰写作者&#xff1a;左手の明天 &#x1f947; 精选专栏&#xff1a;《python》 &#x1f525; 推荐专栏&#xff1a;《算法研究》 #### 防伪水印——左手の明天 #### &#x1f497; 大家好&am…...

【第13届蓝桥杯】C/C++组B组省赛题目+详解

A.九进制转十进制 题目描述 九进制正整数(2022)9转换成十进制等于多少&#xff1f; 解&#xff1a; 2*9^02*9^12*9^321814581478; B.顺子日期 题目描述 小明特别喜欢顺子。顺子指的就是连续的三个数字&#xff1a;123、456等。顺子日期指的就是在日期的yyyymmdd表示法中&a…...

STM32 KEI 调试新手注意事项

记录一下解决问题的经过:1&#xff0c;用STM32 cubeMX 生成的MKD工程,默认的代码优化级别是level3 &#xff0c; 这个级别 会把一些代码给优化掉&#xff0c;造成一些意想不到的结果&#xff0c;最直观的就是 被优化的语句不能打断点调试&#xff0c;当你打了断点 &#xff0c;…...

Windows权限提升—令牌窃取、UAC提权、进程注入等提权

Windows权限提升—令牌窃取、UNC提权、进程注入等提权1. 前言2. at本地命令提权2.1. 适用范围2.2. 命令使用2.3. 操作步骤2.3.1. 模拟提权2.3.2. at配合msf提权2.3.2.1. 生成木马文件2.3.2.2. 设置监听2.3.2.3. 设置反弹2.3.2.4. 查看反弹效果3. sc本地命令提权3.1. 适用范围3.…...

不做孔乙己也不做骆驼祥子

对教书育人的探讨前言一、为什么要“育人”1.育人为先2.育人是快乐的二、怎么“育人”前言 借着本次师德师风建设的主题&#xff0c;跟各位老师谈一谈对于“育人”的一些观点&#xff0c;和教育的一些看法。本文仅代表自己的观点&#xff0c;有不到位的地方&#xff0c;大家可以…...

ChatGPT原理解析

文章目录Transformer模型结构构成组件整体流程GPT预训练微调模型GPT2GPT3局限性GPT4相关论文Transformer Transformer&#xff0c;这是一种仅依赖于注意力机制而不使用循环或卷积的简单模型&#xff0c;它简单而有效&#xff0c;并且在性能方面表现出色。 在时序模型中&#…...

常用算法实现【必会】:sort/bfs/dfs

文章目录常用排序算法实现&#xff08;Go版本&#xff09;BFS 广度优先遍历&#xff0c;利用queueDFS 深度优先遍历&#xff0c;利用stack前序遍历&#xff08;根 左 右&#xff09;中序遍历&#xff08;左根右&#xff09;后序遍历&#xff08;左 右 根&#xff09;BFS/DFS 总…...

瑟瑟发抖吧——用了这款软件,我的开发效率提升了50%

一、前言 开发中&#xff0c;一直听到有人讨论是否需要重复造轮子&#xff0c;我觉得有能力的人&#xff0c;轮子得造。但是往往开发周期短&#xff0c;用轮子所节省的时间去更好的理解业务&#xff0c;应用到业务中&#xff0c;也能清晰发现轮子的利弊&#xff0c;一定意义上…...

SEO优化对网站收录有什么作用

SEO优化对网站收录有什么作用 在当今互联网信息爆炸的时代&#xff0c;网站的收录问题显得尤为重要。SEO优化对于网站的收录有着至关重要的作用&#xff0c;无论是对于新开的网站还是已经运营一段时间的网站&#xff0c;优化都能为其带来更多的流量和潜在客户。SEO优化对网站收…...

揭秘冷轧精密带钢DC03-C340:3大核心特性如何赋能精密制造?

朋友们&#xff0c;今天咱们不聊虚的&#xff0c;就聊聊工厂车间里最实在的东西——材料。你是不是也遇到过这样的烦心事&#xff1a;花大价钱买回来的钢带&#xff0c;一上冲床就开裂&#xff0c;废品率居高不下&#xff1b;或者热处理后表面出现诡异的蓝线&#xff0c;抛光怎…...

IT行业的项目经理考不考PMP证书?我劝你看完这篇在决定!

作为在 IT 圈摸爬滚打 8 年&#xff0c;从后端开发一路转型项目经理、带过 10 大小项目的老学长&#xff0c;最近总被身边技术小伙伴追问&#xff1a;想转 PM&#xff0c;必须考 PMP 吗&#xff1f;没证书就做不好项目管理吗&#xff1f;今天就用过来人的经验&#xff0c;跟大…...

IBM Plex字体家族全攻略:企业级开源字体的应用与实践

IBM Plex字体家族全攻略&#xff1a;企业级开源字体的应用与实践 【免费下载链接】plex The package of IBM’s typeface, IBM Plex. 项目地址: https://gitcode.com/gh_mirrors/pl/plex 企业级字体解决方案的价值解析 在数字产品设计中&#xff0c;字体作为视觉传达的…...

StreamlabsArduinoAlerts:嵌入式设备接入Twitch直播事件

1. StreamlabsArduinoAlerts 库深度解析&#xff1a;嵌入式设备接入 Twitch 直播事件的完整实现方案 StreamlabsArduinoAlerts 是一个专为资源受限嵌入式平台设计的轻量级 C 库&#xff0c;其核心目标是让 Arduino、ESP8266、ESP32、Particle 及基于 ATmega/STM32 的 MCU 能够直…...

Modbus协议详解:从原理到工业应用实践

1. Modbus协议概述Modbus是一种应用层报文传输协议&#xff0c;由Modicon公司&#xff08;现为施耐德电气旗下品牌&#xff09;于1979年开发。作为工业自动化领域最广泛采用的通信协议之一&#xff0c;它定义了控制器设备之间交换信息的通用语言。关键特性&#xff1a;协议标准…...

【数字电路】从双稳态到触发器:时序逻辑的存储基石

1. 数字世界的记忆细胞&#xff1a;双稳态电路探秘 当你按下电脑电源键的瞬间&#xff0c;数十亿个微型存储单元开始工作&#xff0c;它们就像数字世界的记忆细胞&#xff0c;忠实地记录着每一个比特的信息。这一切的起点&#xff0c;正是我们今天要探讨的双稳态电路。想象一下…...

如何用滑模控制(SMC)解决机器人轨迹跟踪中的抖动问题?5个实战技巧分享

如何用滑模控制&#xff08;SMC&#xff09;解决机器人轨迹跟踪中的抖动问题&#xff1f;5个实战技巧分享 当机械臂在执行高精度焊接任务时&#xff0c;末端执行器突然出现5Hz的高频震颤——这种场景对工业机器人工程师而言绝不陌生。滑模控制&#xff08;SMC&#xff09;因其强…...

基于RK3506与LVGUI的CyberGear电机交互式控制台开发实践

1. 从零搭建CyberGear电机控制环境 第一次拿到RK3506开发板和小米CyberGear电机时&#xff0c;我花了整整两天时间才把基础环境搭好。这里分享几个关键步骤&#xff0c;帮你避开我踩过的坑。 硬件连接部分要注意XT30PB插头的防呆设计&#xff0c;插反了会烧毁接口。建议先用万用…...

避开这些坑!Mapbox图层管理实战:动态加载GeoJSON数据的正确姿势

Mapbox高级图层管理实战&#xff1a;GeoJSON动态加载与性能优化全解析 当处理省级以上GIS数据可视化时&#xff0c;Mapbox的图层管理能力直接决定了应用的流畅度和用户体验。许多开发者在使用GeoJSON数据源时&#xff0c;常遇到内存泄漏、渲染卡顿、交互延迟等问题。本文将深入…...