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

第十四届蓝桥杯省赛C++B组E题【接龙数列】题解(AC)

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

需求分析

题目要求最少删掉多少个数后,使得数列变为接龙数列。

相当于题目要求求出数组中的最长接龙子序列。

题目分析

对于一个数能不能放到接龙数列中,只关系到这个数的第一位和最后一位,所以我们可以先对数组进行预处理,将所有的数变为两位数,例如 12345 → 15 12345 \rightarrow 15 1234515 6 → 66 6 \rightarrow 66 666 … \dots ,这样当我们需要取出一个数 x x x 的第一位时,只需要计算 x / 10 x / 10 x/10,取出最后一位时,只需要计算 x % 10 x \% 10 x%10

那么接下来考虑如何求接龙序列的最大值。

考虑动态规划, f ( i , j ) f(i, j) f(i,j) 表示在前 i i i 个数中,以 j j j 结尾的最大长度。

考虑状态转移,设第 i i i 个数为 a b ab ab

  • 若不选第 i i i 个数,则有 f ( i , j ) = f ( i − 1 , j ) f(i, j) = f(i - 1, j) f(i,j)=f(i1,j) 0 ≤ j ≤ 9 0 \leq j \leq 9 0j9)。
  • 若选第 i i i 个数,则 f ( i , b ) = max ⁡ ( f ( i − 1 , b ) , f ( i − 1 , a ) + 1 ) f(i, b) = \max(f(i - 1, b), f(i - 1, a) + 1) f(i,b)=max(f(i1,b),f(i1,a)+1)

那么接龙数列的最大长度为 max ⁡ ( { f ( n , i ) \max(\{f(n, i) max({f(n,i) 0 ≤ i ≤ 9 0 \leq i \leq 9 0i9 } ) \}) })

观察状态转移发现, f ( i , j ) f(i, j) f(i,j) 仅由 f ( i − 1 , x ) f(i - 1, x) f(i1,x) 计算得出,故可以使用滚动数组进行优化。

时间复杂度 O ( n ) O(n) O(n)

  • C++
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e5 + 10;int n;
int q[N];
int f[N][10];int main()
{cin >> n;for (int i = 1; i <= n; ++ i ){int x;cin >> x;int y = x % 10;while (x >= 10)x /= 10;q[i] = x * 10 + y;}for (int i = 1; i <= n; ++ i ){for (int j = 0; j < 10; ++ j )f[i][j] = f[i - 1][j];int a = q[i] / 10, b = q[i] % 10;f[i][b] = max(f[i][b], f[i - 1][a] + 1);}int res = 0;for (int i = 0; i < 10; ++ i )res = max(res, f[n][i]);cout << n - res << endl;return 0;
}
  • C++(空间优化)
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e5 + 10;int n;
int q[N];
int f[N];int main()
{cin >> n;for (int i = 0; i < n; ++ i ){int x;cin >> x;int y = x % 10;while (x >= 10)x /= 10;q[i] = x * 10 + y;}for (int i = 0; i < n; ++ i ){int a = q[i] / 10, b = q[i] % 10;f[b] = max(f[b], f[a] + 1);}cout << n - *max_element(f, f + 10) << endl;return 0;
}

【在线测评】

在这里插入图片描述

相关文章:

第十四届蓝桥杯省赛C++B组E题【接龙数列】题解(AC)

需求分析 题目要求最少删掉多少个数后&#xff0c;使得数列变为接龙数列。 相当于题目要求求出数组中的最长接龙子序列。 题目分析 对于一个数能不能放到接龙数列中&#xff0c;只关系到这个数的第一位和最后一位&#xff0c;所以我们可以先对数组进行预处理&#xff0c;将…...

Ubuntu 20.04.4 LTS 离线安装docker 与docker-compose

Ubuntu 20.04.4 LTS 离线安装docker 与docker-compose 要在Ubuntu 20.04.4 LTS上离线安装Docker和Docker Compose&#xff0c;你需要首先从有网络的环境下载Docker和Docker Compose的安装包&#xff0c;然后将它们传输到离线的服务器上进行安装。 在有网络的环境中&#xff1a…...

vue3+ts 写echarts 中国地图

需要引入二次封装的echarts和在ts文件写的option <template><div class"contentPage"><myEcharts :options"chartOptions" class"myEcharts" id"myEchartsMapId" ref"mapEcharts" /></di…...

【设计模式】【行为型模式】【责任链模式】

系列文章目录 可跳转到下面链接查看下表所有内容https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501文章浏览阅读2次。系列文章大全https://blog.csdn.net/handsomethefirst/article/details/138226266?spm1001.2014.3001.5501 目录…...

超越所有SOTA达11%!媲美全监督方法 | UC伯克利开源UnSAM

文章链接&#xff1a;https://arxiv.org/pdf/2406.20081 github链接&#xff1a;https://github.com/frank-xwang/UnSAM SAM 代表了计算机视觉领域&#xff0c;特别是图像分割领域的重大进步。对于需要详细分析和理解复杂视觉场景(如自动驾驶、医学成像和环境监控)的应用特别有…...

享元模式(设计模式)

享元模式&#xff08;Flyweight Pattern&#xff09;是一种结构型设计模式&#xff0c;它通过共享细粒度对象来减少内存使用&#xff0c;从而提高性能。在享元模式中&#xff0c;多个对象可以共享相同的状态以减少内存消耗&#xff0c;特别适合用于大量相似对象的场景。 享元模…...

【机器学习】大模型训练的深入探讨——Fine-tuning技术阐述与Dify平台介绍

目录 引言 Fine-tuning技术的原理阐 预训练模型 迁移学习 模型初始化 模型微调 超参数调整 任务设计 数学模型公式 Dify平台介绍 Dify部署 创建AI 接入大模型api 选择知识库 个人主页链接&#xff1a;东洛的克莱斯韦克-CSDN博客 引言 Fine-tuning技术允许用户根…...

【Linux从入门到放弃】探究进程如何退出以进程等待的前因后果

&#x1f9d1;‍&#x1f4bb;作者&#xff1a; 情话0.0 &#x1f4dd;专栏&#xff1a;《Linux从入门到放弃》 &#x1f466;个人简介&#xff1a;一名双非编程菜鸟&#xff0c;在这里分享自己的编程学习笔记&#xff0c;欢迎大家的指正与点赞&#xff0c;谢谢&#xff01; 进…...

QT5 static_cast实现显示类型转换

QT5 static_cast实现显示类型转换&#xff0c;解决信号重载情况...

【ES】--Elasticsearch的翻页详解

目录 一、前言二、from+size浅分页1、from+size导致深度分页问题三、scroll深分页1、scroll原理2、scroll可以返回总计数量四、search_after深分页1、search_after避免深度分页问题一、前言 ES的分页常见的主要有三种方式:from+size浅分页、scroll深分页、search_after分页。…...

3.js - 纹理的重复、偏移、修改中心点、旋转

你瞅啥 上字母 // ts-nocheck // 引入three.js import * as THREE from three // 导入轨道控制器 import { OrbitControls } from three/examples/jsm/controls/OrbitControls // 导入lil.gui import { GUI } from three/examples/jsm/libs/lil-gui.module.min.js // 导入twee…...

RS232隔离器的使用

RS232隔离器在通信系统中扮演着至关重要的角色&#xff0c;其主要作用可以归纳如下&#xff1a; 一、保护通信设备 电气隔离&#xff1a;RS232隔离器通过光电隔离技术&#xff0c;将RS-232接口两端的设备电气完全隔离&#xff0c;从而避免了地线回路电压、浪涌、感应雷击、静电…...

一切为了安全丨2024中国应急(消防)品牌巡展武汉站成功召开!

消防品牌巡展武汉站 6月28日&#xff0c;由中国安全产业协会指导&#xff0c;中国安全产业协会应急创新分会、应急救援产业网联合主办&#xff0c;湖北消防协会协办的“一切为了安全”2024年中国应急(消防)品牌巡展-武汉站成功举办。该巡展旨在展示中国应急&#xff08;消防&am…...

【面试系列】PHP 高频面试题

欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;欢迎订阅相关专栏&#xff1a; ⭐️ 全网最全IT互联网公司面试宝典&#xff1a;收集整理全网各大IT互联网公司技术、项目、HR面试真题. ⭐️ AIGC时代的创新与未来&#xff1a;详细讲解AIGC的概念、核心技术、…...

JAVA极简图书管理系统,初识springboot后端项目

前提条件&#xff1a; 具备基础的springboot 知识 Java基础 废话不多说&#xff01; 创建项目 配置所需环境 将application.properties>application.yml 配置以下环境 数据库连接MySQL 自己创建的数据库名称为book_test server:port: 8080 spring:datasource:url:…...

MySQL 重新初始化实例

1、关闭mysql服务 service mysqld stop 2、清理datadir(本例中指定的是/var/lib/mysql)指定的目录下的文件&#xff0c;将该目录下的所有文件删除或移动至其他位置 cd /var/lib/mysql mv * /opt/mysql_back/ 3、初始化实例 /usr/local/mysql/bin/mysqld --initialize --u…...

VCS编译bug汇总

‘typedef’ is not expected to be used in this contex 注册前少了分号。 Scope resolution error resolution : 声明指针时 不能与类名同名&#xff0c;即 不能声明为adapter. cannot find member "type_id" 忘记注册了 拼接运算符使用 关键要加上1b&#xff0…...

【2024LLM应用-数据预处理】之如何从PDF,PPT等非结构化数据提取有效信息(结构化数据JSON)?

&#x1f970;大家知道吗,之前在给AI大模型"喂数据"的时候,我们往往需要把非结构化数据(比如PDF、PPT、Excel等)自己手动转成结构化的格式,这可真是太累人儿了。&#x1f975; 幸好现在有了Unstructured这个神级库,它内置的数据提取函数可以帮我们快速高效地完成这个…...

冯雷老师:618大退货事件分析

近日冯雷老师受邀为某头部电商36名高管进行培训&#xff0c;其中聊到了今年618退货潮的问题。以下内容整理自冯雷老师的部分授课内容。 一、引言 随着电子商务的蓬勃发展&#xff0c;每年的618大促已成为消费者和商家共同关注的焦点。然而&#xff0c;在销售额不断攀升的同时…...

JAVA基础教程DAY0-基础知识

JAVA语言的特点 简单性、面向对象、安全性、跨平台性、支持多线程、分布性 面向对象编程&#xff08;Object-Oriented Programming&#xff0c;简称OOP&#xff09;是一种编程范式&#xff0c;它通过将数据和操作这些数据的方法封装在一起&#xff0c;以创建对象的形式来组织代…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...