acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 资讯
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 应该是这样的

    给定基础串 s,每次操作令 s=s+s(长度翻倍,操作次数 + 1);求最少操作次数,使得 t 是当前字符串的子串;永远无法满足输出 −1。关键观察 1:无解前置判定若 t 中存在某个字符,s 里完全没有,直接输出 −1;例:s=abc,t=ac,字符都有,但仍无解,只能先筛掉字符缺失的情况。关键观察 2:循环串本质不断拼接 s 等价于无限循环串 ssssssss⋯;只要 t 能出现在无限循环串中,就一定能在两段拼接 s+s 里找到;但我们题目要求每次只能翻倍,所以需要逐步翻倍直到长度足够覆盖 t。关键观察 3:循环终止条件设 len t 为 t 长度。如果当前字符串长度 > 2×len t 仍未找到子串,说明永远不可能出现,直接返回 −1 原因:更长的翻倍字符串只是重复原有循环,不会产生新的连续字符组合。 算法步骤 字符校验:统计 s 出现过的字母,遍历 t,有不存在字母直接输出 −1 初始化:当前串 cur=s,操作次数 cnt=0。 循环判断:若 cur 包含 t,输出 cnt 结束; 若 cur.size()>2×t.size(),无解输出 −1; 否则翻倍 cur=cur+cur,次数 cnt+1

    userId_undefined
    剑
    维度操控者俄罗斯套娃大师造物者结构体学徒→封装者多键裁决者ASCII炼金师
    1阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页