AtCoder - arc058_d Iroha Loves Strings解答与注意事项
链接:Iroha Loves Strings - AtCoder arc058_d - Virtual Judge
利用bitset这一数据结构,定义bitset类型的变量dp[i]表示第i到n个字符串能拼成的字符串长度都有哪些,比如00100101,表示能拼成的长度有0,2,5,(注意:bitset中的元素从右往左看,下标从0开始),利用递推关系更新dp[i]如下
dp[i] = dp[i+1] | (dp[i+1] << s[i]的长度)
若dp[i][k] = 1,说明第i到第n个字符串可以拼成长度为k的字符串
之后模拟取数,i从1到k进行遍历,每次取当前能取的最小的字符,具体实现方式如下:(以下描述建议结合代码看)
定义候选对数组 pair<int,int> sel[i][j],i为0或1(用作开关变量),j是候选对象的编号,从1到cnt或ncnt,每个sel[i][j]中存的是
<候选字符所在的字符串的序号,候选字符在该字符串中的下标>
第一个字符的候选字符串i,要满足dp[i+1][k-s[i]的长度] = 1,也就是选了第i个字符串后,之后的字符串必须保证能拼成(k-s[i]的长度)的长度的字符串,将pair<i,0>加入sel
i从1到k遍历,每次在所有候选字符中选择字典序最小的那个字符作为答案,接着分情况讨论:
1.如果字符串还没用完,就继续将该字符串的下一个元素加入候选队列,如果有这样的字符串:
ab和ac,那么b和c都应该加入候选队列,
2.如果有一个字符串用完了,可能出现这样的情况:abc abc,这时应该先选前面的“abc”,因为选完编号为i的字符串后,新入选的字符串的下标从 i+1 开始,如果选了第二个或后面的,就会有字符串没法被用到,从而导致丢失解或错误解,新入选的字符串(编号为 j )要满足dp[ j+1 ][ k-i-新字符串的长度 ]等于1,这样选其能确保最终构成的字符串有可能长度为k,将pair<新字符串的编号,0>加入sel中
复杂度估计:nk
注意:
bitset和pair定义的先后会影响程序运行对错,正确的顺序是先定义bitset后定义pair,原因涉及到C++语言本身
#include<bits/stdc++.h>
using namespace std;const int maxn=2005,maxk=1e4+5;
char s[maxn][maxk];
int len[maxn];
int n,k;
bitset<maxk> dp[maxn];
pair<int,int> sel[2][maxn];//pair和bitset的先后问题int main()
{ios::sync_with_stdio(0);cin.tie(0);//freopen("D:\\in.txt","r",stdin);cin>>n>>k;for(int i=1;i<=n;i++){cin>>s[i];len[i]=strlen(s[i]);}dp[n+1][0]=1;for(int i=n;i>=1;i--){dp[i]=(dp[i+1] | (dp[i+1]<<len[i]));}int cnt=0;//挑出第一个字符的可选对象for(int i=1;i<=n;i++){if(dp[i+1][k-len[i]]){//printf("%d可选\n",i);sel[0][++cnt]={i,0};}}int t=1;for(int i=1;i<=k;i++){int ncnt=0;t^=1;char cur='z';for(int j=1;j<=cnt;j++){cur=min(cur,s[sel[t][j].first][sel[t][j].second]);}cout<<cur;//更新下一组候选对象int minid=n+1;for(int j=1;j<=cnt;j++){int id=sel[t][j].first,pos=sel[t][j].second;if(s[id][pos]!=cur) continue;if(pos<len[id]-1){sel[t^1][++ncnt]={id,pos+1};}else{minid=min(minid,id); //选序号最小的,这样后面的字符串还能用得上(不然会白白浪费字符串)}}for(int j=minid+1;j<=n;j++){if(k-i-len[j]>=0 && dp[j+1][k-i-len[j]]){sel[t^1][++ncnt]={j,0};}}cnt=ncnt;}return 0;
}
相关文章:
AtCoder - arc058_d Iroha Loves Strings解答与注意事项
链接:Iroha Loves Strings - AtCoder arc058_d - Virtual Judge 利用bitset这一数据结构,定义bitset类型的变量dp[i]表示第i到n个字符串能拼成的字符串长度都有哪些,比如00100101,表示能拼成的长度有0,2,5,࿰…...
企业使用统一终端管理(UEM)工具提高端点安全性
什么是统一终端管理(UEM) 统一终端管理(UEM)是一种从单个控制台管理和保护企业中所有端点的方法,包括智能手机、平板电脑、笔记本电脑、台式机和 IoT设备。UEM 解决方案为 IT 管理员提供了一个集中式平台,用于跨所有作系统和设备类型部署、配置、管理和…...
Leetcode 算法题 9 回文数
起因, 目的: 数学法。 % 求余数, 拆开组合,组合拆开。 这个题,翻来覆去,拆开组合, 组合拆开。构建的过程。 题目来源,9 回文数: https://leetcode.cn/problems/palindrome-number…...
设计模式Python版 命令模式(上)
文章目录 前言一、命令模式二、命令模式示例 前言 GOF设计模式分三大类: 创建型模式:关注对象的创建过程,包括单例模式、简单工厂模式、工厂方法模式、抽象工厂模式、原型模式和建造者模式。结构型模式:关注类和对象之间的组合&…...
C语言之循环结构:直到型循环
C语言 循环结构 直到型循环的实现 特点:先执行,后判断,不管条件是否满足,至少执行一次。典型代表:do…while,goto(已淘汰,不推荐使用) do…while 语法: d…...
细说STM32F407单片机RTC的备份寄存器原理及使用方法
目录 一、备份寄存器的功能 二、示例功能 三、项目设置 1、晶振、DEBUG、CodeGenerator、USART6 2、RTC 3、NVIC 4、GPIO 及KEYLED 四、软件设计 1、main.h 2、main.c 3、rtc.c 4、keyled.c、keyled.h 五、运行调试 本实例旨在介绍备份寄存器的作用。本实例继续使…...
MATLAB计算反映热需求和能源消耗的度数日指标(HDD+CDD)(全代码)
目录 度数日(Degree Days, DD)概述计算公式MATLAB计算代码调用函数1:计算单站点的 CDD参考度数日(Degree Days, DD)概述 度数日(Degree Days, DD)是用于衡量建筑、城市和地区的热需求和能源消耗模式的指标。它分为两部分: 加热度日(Heating Degree Days, HDD):当室…...
J6 X8B/X3C切换HDR各帧图像
1、OV手册上的切换命令 寄存器为Ox5074 各帧切换: 2、地平线control tool实现切换命令 默认HDR模式出图: HCG出图: LCG出图 SPD出图 VS出图...
09-轮转数组
给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。 方法一:使用额外数组 function rotate(nums: number[], k: number): void {const n nums.length;k k % n; // 处理 k 大于数组长度的情况const newNums new A…...
用vue3写一个好看的wiki前端页面
以下是一个使用 Vue 3 Element Plus 实现的 Wiki 风格前端页面示例,包含现代设计、响应式布局和常用功能: <template><div class"wiki-container"><!-- 头部导航 --><el-header class"wiki-header"><d…...
瑞芯微烧写工具
文章目录 前言一、安装驱动二、安装烧写工具1.直接解压压缩包2. 如何使用 三、MASKROM 裸机必备四、LOADER 烧写,前提是搞过第三步没问题五、Update.img包的烧录六、linux下烧写总结 前言 提示:这里可以添加本文要记录的大概内容: 项目需要…...
说下JVM中一次完整的GC流程?
大家好,我是锋哥。今天分享关于【说下JVM中一次完整的GC流程?】面试题。希望对大家有帮助; 说下JVM中一次完整的GC流程? 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 JVM中的一次完整的垃圾回收(GC)流程可以概括为…...
Open FPV VTX开源之OSD使用分类
Open FPV VTX开源之OSD使用分类 1. 源由2. 硬件2.1 【天空端】SigmaStar2.2 【天空端】Raspberry Pi2.3 【地面端】 3. 软件3.1 天空端软件3.2 地面端软件 4. 分类4.1 嵌入式OSD分类A1-嵌入式OSD:SigmaStar Android分类A2-嵌入式OSD:SigmaStar Hi3536分…...
智慧农业-虫害及生长预测
有害生物防控系统是一个综合性的管理体系,旨在预防和控制对人类生活、生产甚至生存产生危害的生物。这些生物可能包括昆虫、动物、植物、微生物乃至病毒等。 一、系统构成 1、监测预警系统:利用智能传感器、无人机、遥感技术等手段,实时监测…...
Python 识别图片和扫描PDF中的文字
目录 工具与设置 Python 识别图片中的文字 Python 识别图片中的文字及其坐标位置 Python 识别扫描PDF中的文字 注意事项 在处理扫描的PDF和图片时,文字信息往往无法直接编辑、搜索或复制,这给信息提取和分析带来了诸多不便。手动录入信息不仅耗时费…...
C语言如何知道当前系统中的编译器数据类型的大小是多少?
在 C 语言中,你可以使用sizeof运算符来确定当前系统中编译器数据类型的大小,该运算符返回一个size_t类型的值,表示所操作对象或数据类型占用的字节数。下面为你详细介绍使用方法: 1. 基本数据类型大小的获取 基本数据类型如char…...
gitlab Webhook 配置jenkins时“触发远程构建 (例如,使用脚本)”报错
报错信息: <html> <head> <meta http-equiv"Content-Type" content"text/html;charsetISO-8859-1"/> <title>Error 403 No valid crumb was included in the request</title> </head> <body><h2…...
Mysql中使用sql语句生成雪花算法Id
🍓 简介:java系列技术分享(👉持续更新中…🔥) 🍓 初衷:一起学习、一起进步、坚持不懈 🍓 如果文章内容有误与您的想法不一致,欢迎大家在评论区指正🙏 🍓 希望这篇文章对你有所帮助,欢…...
/etc/profile vs ~/.bashrc:如何正确使用?
在 Linux 或 WSL 环境中,我们经常需要配置环境变量、命令别名、路径等信息。然而,许多人在配置时会纠结:到底应该放在 /etc/profile 还是 ~/.bashrc?本文将全面解析它们的区别,并帮助你做出正确的选择。 1. 什么是 /et…...
SpringBoot实战:高效获取视频资源
文章目录 前言技术实现SpringBoot项目构建产品选取配置数据采集 号外号外 前言 在短视频行业高速发展的背景下,海量内容数据日益增长,每天都有新的视频、评论、点赞、分享等数据涌现。如何高效、精准地获取并处理这些庞大的数据,已成为各大平…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
