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

AcWing《蓝桥杯集训·每日一题》—— 1460 我在哪?

AcWing《蓝桥杯集训·每日一题》—— 1460. 我在哪?

文章目录

  • AcWing《蓝桥杯集训·每日一题》—— 1460. 我在哪?
  • 一、题目
  • 二、解题思路
  • 三、代码实现

本次博客我是通过Notion软件写的,转md文件可能不太美观,大家可以去我的博客中查看:北天的 BLOG,持续更新中,另外这是我创建的编程学习小组频道,想一起学习的朋友可以一起!!!

一、题目

沿路有一排共 NNN 个农场。

不幸的是农场并没有编号,这使得约翰难以分辨他在这条路上所处的位置。

然而,每个农场都沿路设有一个彩色的邮箱,所以约翰希望能够通过查看最近的几个邮箱的颜色来唯一确定他所在的位置。

每个邮箱的颜色用 A..ZA..ZA..Z 之间的一个字母来指定,所以沿着道路的 NNN 个邮箱的序列可以用一个长为 NNN 的由字母 A..ZA..ZA..Z 组成的字符串来表示。

某些邮箱可能会有相同的颜色。

约翰想要知道最小的 A..ZA..ZA..Z 的值,使得他查看任意连续 KKK 个邮箱序列,他都可以唯一确定这一序列在道路上的位置。

例如,假设沿路的邮箱序列为 ABCDABC 。

约翰不能令 K=3K = 3K=3,因为如果他看到了 ABC,则沿路有两个这一连续颜色序列可能所在的位置。

最小可行的 K 的值为 K=4K = 4K=4,因为如果他查看任意连续 4 个邮箱,那么可得到的连续颜色序列可以唯一确定他在道路上的位置。

输入格式

输入的第一行包含 NNN,第二行包含一个由 NNN 个字符组成的字符串,每个字符均在 A..ZA..ZA..Z 之内。

输出格式

输出一行,包含一个整数,为可以解决农夫约翰的问题的最小 KKK 值。

数据范围

1≤N≤1001≤ N ≤1001N100

输入样例:

7
ABCDABC

输出样例:

4

二、解题思路

1、暴力枚举法

对于暴力枚举法,我们可以使用两重循环,外层循环枚举K的长度,内层循环枚举所有的子串,并在后面的部分中查找该子串是否出现过。如果没有找到,则表示当前长度K可行,输出K并结束程序。如果内层循环结束后仍未找到合适的K,则需要继续外层循环进行下一轮枚举。

2、二分法

对于二分法,我们可以将判断一个长度K是否可行转化为判断以每个位置为起点的长度为K的子串是否互不相同。具体地,我们可以将所有以长度K的子串存入一个集合中,然后判断集合中的元素个数是否等于N-K+1。如果等于,则表示当前长度K可行,否则不可行。因为如果有重复的子串,那么集合中的元素个数会小于N-K+1,如果没有重复的子串,则集合中的元素个数会等于N-K+1。根据这个判断结果来缩小二分法的搜索范围,直到找到最小可行的K。

三、代码实现

n = int(input())         # 输入农场数
s = input().strip()      # 输入邮筒序列res = n                  # 初始化最小连续颜色长度res为nfor k in range(1, n+1):  # 外层循环枚举连续颜色长度k,从1到nseen = set()         # 定义一个集合seen,用于存储当前长度为k的所有子串unique = True        # 初始化unique为True# 内层循环枚举字符串s中长度为k的所有子串for i in range(n-k+1):sub = s[i:i+k]   # 取出从i开始长度为k的子串subif sub in seen:   # 如果sub已经在seen中出现过了,说明有重复子串,此时unique为Falseunique = Falsebreakelse:seen.add(sub) # 否则将sub加入seen集合中if unique:            # 如果unique为True,说明当前枚举的k值可以唯一确定任意连续k个邮箱序列在道路上的位置res = k           # 更新最小连续颜色长度resbreakprint(res)                # 输出最小的k值,即可以解决农夫约翰的问题的最小K值

该段代码的时间复杂度为 O(n2)O(n^2)O(n2),因为外层循环枚举了 kkk 个长度,内层循环每次需要枚举 n−k+1n-k+1nk+1 个长度为 kkk 的子串,并且使用了 set 进行查重。set 的查找时间复杂度为 O(1)O(1)O(1),所以内层循环的时间复杂度为 O((n−k+1)×1)=O(n−k+1)O((n-k+1) \times 1) = O(n-k+1)O((nk+1)×1)=O(nk+1)。因此,总的时间复杂度为:∑k=1n(n−k+1)=O(n2)\sum_{k=1}^{n} (n-k+1) = O(n^2)k=1n(nk+1)=O(n2)

其中,∑k=1n(n−k+1)\sum_{k=1}^{n} (n-k+1)k=1n(nk+1) 是等差数列求和公式的展开形式。

二分解法:

n = int(input())         # 输入农场数
s = input().strip()      # 输入邮筒序列def check(k):            # 定义check函数用来检查k的取值是否满足条件substrings = set()   # 用set存储s中所有长度为k的不同的子串for i in range(n-k+1):substrings.add(s[i:i+k])return len(substrings) == n-k+1  # 如果set中的元素个数为n-k+1则说明所有长度为k的子串均不相同left, right = 1, n              # 初始时,left=1,right=n
while left < right:             # 当left < right时,循环继续mid = (left+right)//2       # 计算中间值midif check(mid):       # 如果check(mid)返回True,则说明k=mid满足条件,应该继续往左找right = midelse:                # 如果check(mid)返回False,则说明k=mid不满足条件,应该往右找left = mid+1print(left)                 # 最终left就是满足条件的最小的k

该二分法代码的时间复杂度为O(nlogn)O(nlogn)O(nlogn)*,*其中nnn为字符串的长度。主要耗时的是check函数,时间复杂度为O(nk)O(nk)O(nk)kkk是检查的子串长度,当k=nk=nk=n时,时间复杂度最大为O(n2)O(n^2)O(n2)。而二分法中循环的次数最多为O(logn)O(logn)O(logn),因此总时间复杂度为O(n∗logn)O(n*logn)O(nlogn)

相关文章:

AcWing《蓝桥杯集训·每日一题》—— 1460 我在哪?

AcWing《蓝桥杯集训每日一题》—— 1460. 我在哪&#xff1f; 文章目录AcWing《蓝桥杯集训每日一题》—— 1460. 我在哪&#xff1f;一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的&#xff0c;转md文件可能不太美观&#xff0c;大家可以去我的博客中查看&am…...

AcWing《蓝桥杯集训·每日一题》—— 3729 改变数组元素

AcWing《蓝桥杯集训每日一题》—— 3729. 改变数组元素 文章目录AcWing《蓝桥杯集训每日一题》—— 3729. 改变数组元素一、题目二、解题思路三、代码实现本次博客我是通过Notion软件写的&#xff0c;转md文件可能不太美观&#xff0c;大家可以去我的博客中查看&#xff1a;北天…...

如何熟练掌握Python在气象水文中的数据处理及绘图【免费教程】

pythonPython由荷兰数学和计算机科学研究学会的吉多范罗苏姆于1990年代初设计&#xff0c;作为一门叫做ABC语言的替代品。Python提供了高效的高级数据结构&#xff0c;还能简单有效地面向对象编程。Python语法和动态类型&#xff0c;以及解释型语言的本质&#xff0c;使它成为多…...

Leetcode详解JAVA版

目录1. 两数之和14. 最长公共前缀15. 三数之和18. 四数之和19. 删除链表的倒数第 N 个结点21. 合并两个有序链表28. 找出字符串中第一个匹配项的下标36. 有效的数独42. 接雨水43. 字符串相乘45. 跳跃游戏 II53. 最大子数组和54. 螺旋矩阵55. 跳跃游戏62. 不同路径70. 爬楼梯73.…...

LeetCode 83. 删除排序链表中的重复元素

原题链接 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 给定一个已排序的链表的头 headheadhead &#xff0c; 删除所有重复的元素&#xff0c;使每个元素只出现一次 。返回 已排序的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,1,2] 输出&#xff1a;…...

RMI简易实现(基于maven)

参考其它rmi&#xff08;remote method invocation&#xff09;的代码后&#xff0c;加入了自己思考。整个工程基于maven构建&#xff0c;我觉得maven的模块化可比较直观地演示rmi 目录 项目结构图 模块解读 pom文件 rmi-impl rmi-common-interface rmi-server rmi-cli…...

‘excludeSwitches‘ 的 [‘enable-logging‘] 和[‘enable-automation‘]

selenium 使用 chrome 浏览器的 chromedriver 时&#xff0c;可以加参数&#xff0c; chrome_optionswebdriver.ChromeOptions() chrome_options.add_experimental_option(excludeSwitches,[enable-logging]) chrome_options.add_experimental_option(excludeSwitches,[enable…...

华为OD机试 - 最短木板长度(Python)| 真题+思路+考点+代码+岗位

最短木板长度 题目 小明有 n n n 块木板,第 i i i(1≤ i i...

第一个Python程序-HelloWorld与Python解释器

数据来源 01 第一个Python程序-HelloWorld 1&#xff09;打开cmd&#xff1a; windows R 打开运行窗口输入cmd 2&#xff09;进入Python编写页面 输入&#xff1a;python 3&#xff09;然后输入要写的Python代码然后回车 print("Hello World!!!") print() …...

C++数据类型

目录 一、基本的内置类型 二、typedef声明 三、枚举类型 一、基本的内置类型 C 为程序员提供了种类丰富的内置数据类型和用户自定义的数据类型。下表列出了七种基本的 C 数据类型&#xff1a; 类型关键字布尔型bool字符型char整型int浮点型float双浮点型double无类型void宽…...

华为OD机试 - 考古学家(Python)| 真题+思路+考点+代码+岗位

考古学家 题目 有一个考古学家发现一个石碑 但是很可惜 发现时其已经断成多段 原地发现 N 个断口整齐的石碑碎片 为了破解石碑内容 考古学家希望有程序能帮忙计算复原后的石碑文字组合数 ,你能帮忙吗 备注: 如果存在石碑碎片内容完全相同,则由于碎片间的顺序不影响复原后…...

常用调试golang的bug以及性能问题的实践方法

文章目录如何分析程序运行时间和CPU利用率情况1.shell内置time指令/usr/bin/time指令如何分析golang程序的内存使用情况&#xff1f;1.内存占用情况查看如何分析golang程序的CPU性能情况1.性能分析注意事项2.CPU性能分析A.Web界面查看B.使用pprof工具查看如何分析程序运行时间和…...

什么是溶血症?什么是ABO溶血?溶血检查些什么?

什么是溶血症&#xff0c;什么是ABO溶血&#xff1f;女人是O型血&#xff0c;男人是其他血型的夫妻配对&#xff0c;最担心的是胎儿溶血症。从理论上讲&#xff0c;只要夫妻双方血型不同&#xff0c;母亲一定缺乏胎儿从父亲那里遗传的抗原。当任何人接触到他们缺乏的抗原时&…...

NLP实践——知识图谱问答模型FiD

NLP实践——知识图谱问答模型FiD0. 简介1. 模型结构2. 召回3. 问答4. 结合知识的问答0. 简介 好久没有更新了&#xff0c;今天介绍一个知识图谱问答&#xff08;KBQA&#xff09;模型&#xff0c;在此之前我一直在用huggingface的Pipeline中提供的QA模型&#xff0c;非常方便但…...

MyBatis 多表关联查询

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

《NFL橄榄球》:克利夫兰布朗·橄榄1号位

克利夫兰布朗&#xff08;英语&#xff1a;Cleveland Browns&#xff09;是一支职业美式橄榄球球队&#xff0c;位于俄亥俄州克利夫兰。 布朗隶属于美国全国橄榄球联盟(NFL)的北区&#xff0c;主场位于第一能源体育场。球队在1946年与AAFC联盟一同成立&#xff0c;并在1946年到…...

InstructGPT笔记

一、InstructGPT是在GPT3上微调&#xff0c;ChatGPT是在GPT3.5上微调 二、该论文展示了怎么样对语言模型和人类意图之间进行匹配&#xff0c;方法是在人类的反馈上进行微调。 **三、方法简介&#xff1a;**收集很多问题&#xff0c;使用标注工具将问题的答案写出来&#xff0…...

【uniapp】getOpenerEventChannel().once 接收参数无效的解决方案

uniapp项目开发跨平台应用常会遇到接收参数无效的问题&#xff0c;无法判断是哪里出错了&#xff0c;这里是讲替代的方案&#xff0c;现有三种方案可选。 原因 一般我们是这样处理向另一个页面传参&#xff0c;代码是这样写的 //... let { title, type, rank } args; uni.n…...

ELK分布式日志收集快速入门-(二)kafka进阶-快速安装可视化管理界面-(单节点部署)

目录安装前准备安装中安装成功安装前准备 安装kafka-参考博客 (10条消息) ELK分布式日志收集快速入门-&#xff08;一&#xff09;-kafka单体篇_康世行的博客-CSDN博客 安装zk 参考博客 (10条消息) 快速搭建-分布式远程调用框架搭建-dubbozookperspringboot demo 演示_康世行的…...

线程的创建

1. 多线程常用函数 1.1 创建一条新线程pthread_create 对此函数使用注意以下几点&#xff1a; 线程例程指的是&#xff1a;如果线程创建成功&#xff0c;则该线程会立即执行的函数。POSIX线程库的所有API对返回值的处理原则一致&#xff1a;成功返回0&#xff0c;失败返回错误…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

轻量级Docker管理工具Docker Switchboard

简介 什么是 Docker Switchboard &#xff1f; Docker Switchboard 是一个轻量级的 Web 应用程序&#xff0c;用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器&#xff0c;使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...

PydanticAI快速入门示例

参考链接&#xff1a;https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...