P3234 [HNOI2014]抄卡组

    • 167通过
    • 436提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 前缀和 哈希,HASH 字符串 2014 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    一天闲着无聊的小L找来了当前正火爆的游戏《炉石传说》来玩,但是怎么打怎么输,于是他大喊一声”我要抄卡组!“就找来了游戏传说组第一名的游戏高手小H的直播来看。

    但是小L家的网络技术还停留在拨号,看着直播画面又是卡顿又是花屏,他不给力的网络让他完全无法记录小H展示的给力的卡组。小L周围都是学霸没有人玩游戏想去帮他这个忙,但是学霸们热衷于讨论各种信息学问题。

    于是他想到了一个方法:由于每次花屏的屏幕位置不一样,于是小H每次总能记录下卡组的一些部分,如果这样记录多次,不就有可能还原出小L想要的一个卡组么?

    但是存在的一个问题是,小H每次展示的卡组有可能不一样,所以他想知道他每次看直播抄下来几次的卡组碎片是否一致。

    这样一来小H将他遇到的游戏问题抽象成这样一个学术问题让学霸(你)解决:'*'可以匹配任意长度个的字符 (包含0个),问所有字符串是否两两匹配。

    输入输出格式

    输入格式:

    第一行包含一个正整数T,表示了数据组数。 接下来包含T组数据: 每组数据的第一行是一个正整数N,表示该组数据酌字符串个数。 接下来N行,每行一个字符串,字符串仅包含小写字母、数字、通配符术。注意:数据为UNIX格式,中间包含空行,你可以采用逐字符读入的方式

    输出格式:

    输出包含T行,每行一个字母Y或者N,Y表示这组数据中所有字符串两两匹配,N表示这组数据中至少有一对字符串不匹配。

    输入输出样例

    输入样例#1: 复制
    10
    2
    1234567890*1234567890
    1234567890a1234567890
    2
    1234567890*1234567890
    1234567890*1234567890
    2
    1234*67890a1234567890
    1234567890*1234567890
    2
    1234567890*1234567890
    1234567890a12345*7890
    2
    1234567890*1234567890
    *12345
    2
    12345*67890
    1234567890*1234567890
    2
    1234567890*1234567890
    12345*
    2
    1234567890*1234567890
    *67890
    2
    67890*
    1234567890*1234567890
    2
    1234567890*a*1234567890
    1234567890*1234567890
    输出样例#1: 复制
    Y
    Y
    Y
    Y
    N
    Y
    Y
    Y
    N
    Y

    说明

    对于100%的数据,满足N<= 100000,T= 10,输入文件不超过10M,N*最长字符串长度不超过2x10^8

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