P2412 查单词

    • 272通过
    • 1.4K提交
  • 题目提供者 HansBug 站长团
  • 评测方式 云端评测
  • 标签 字符串 搜索 线段树 洛谷原创 高性能
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    滚粗了的HansBug在收拾旧英语书,然而他发现了什么奇妙的东西。

    题目描述

    udp2.T3如果遇到相同的字符串,输出后面的

    蒟蒻HansBug在一本英语书里面找到了一个单词表,包含N个单词(每个单词内包含大小写字母)。现在他想要找出某一段连续的单词内字典序最大的单词。

    输入输出格式

    输入格式:

    第一行包含两个正整数N、M,分别表示单词个数和询问个数。

    接下来N行每行包含一个字符串,仅包含大小写字母,长度不超过15,表示一个单词。

    再接下来M行每行包含两个整数x、y,表示求从第x到第y个单词中字典序最大的单词。

    输出格式:

    输出包含M行,每行为一个字符串,分别依次对应前面M个询问的结果。

    输入输出样例

    输入样例#1: 复制
    5 5
    absi
    hansbug
    lzn
    kkk
    yyy
    1 5
    1 1
    1 2
    2 3
    4 4
    输出样例#1: 复制
    yyy
    absi
    hansbug
    lzn
    kkk
    

    说明

    样例说明:

    第一次操作:在{absi,hansbug,lzn,kkk,yyy}中找出字典序最大的,故为yyy

    第二次操作:在{absi}中找出字典序最大的,故为absi

    第三次操作:在{absi,hansbug}中找出字典序最大的,故为hansbug

    第四次操作:在{hansbug,lzn}中找出字典序最大的,故为lzn

    第五次操作:在{kkk}中找出字典序最大的,故为kkk

    数据规模:

    注意事项:1.该题目单词字典序比对过程中大小写不敏感,但是输出必须输出原单词

    2.该题目时间限制为0.2s

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。