#2286. 抄卡组
抄卡组
抄卡组
题目描述
2014‐05‐11 第2 页,共5 页 第1 题:抄卡组(hs),运行时限1s,内存上限512M 【问题描述】 一天闲着无聊的小L 找来了当前正火爆的游戏《炉石传说》来玩,但是怎么打怎么输,于 是他大喊一声“我要抄卡组!”就找来了游戏传说组第一名的游戏高手小H 的直播来看。 但是小L 家的网络技术还停留在拨号,看着直播画面又是卡顿又是花屏,他不给力的网络 让他完全无法记录小H 展示的给力的卡组。小L 周围都是学霸没有人玩游戏想去帮他这个忙, 但是学霸们热衷于讨论各种信息学问题。 于是他想到了一个方法:由于每次花屏的屏幕位置不一样,于是小H 每次总能记录下卡 组的一些部分,如果这样记录多次,不就有可能还原出小L 想要的一个卡组么?但是存在的一 个问题是,小H 每次展示的卡组有可能不一样,所以他想知道他每次看直播抄下来几次的卡 组碎片是否一致。 这样一来小H 将他遇到的游戏问题抽象成这样一个学术问题让学霸(你)解决: 给定N 个字符串,包含小写英文字母、数字、和通配符*,可以匹配任意长度个的字符 (包含0 个),问所有字符串是否两两匹配。 【输入格式】 输入文件为hs.in。 第一行包含一个正整数T,表示了数据组数。 接下来包含T 组数据: 每组数据的第一行是一个正整数N,表示该组数据的字符串个数。 接下来N 行,每行一个字符串,字符串仅包含小写字母、数字、通配符。 【输出格式】 输出文件为hs.out。 输出包含T 行,每行一个字母Y 或者N,Y 表示这组数据中所有字符串两两匹配,N 表示 这组数据中至少有一对字符串不匹配。 【输入输出样例】 hs.in hs.out 3 3 wellplayed thankyou pyroblast 2 aabc abca 2 a*abc a1234567890abc N N Y
【数据范围】
2014‐05‐11
对于10%的数据,满足N ≤ 2;
对于30%的数据,满足所有字符串长度不超过30;
对于50%的数据,满足N ≤ 8;
对于70%的数据,满足N ≤ 500;
对于100%的数据,满足N ≤ 100000,T = 10,输入文件不超过10M,N×最长字符串长度
不超过2×108。
【编译命令】
对于c++语言: g++ -o hs hs.cpp –lm 对于c语言: gcc -o hs hs.c –lm 对于pascal语言: fpc hs.pas
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
3
wellplayed
thankyou
pyroblast
2
a*abc
abc*a
2
a*abc
a1234567890abc
N
N
Y