#PQJ1639x7590. QOJ 1639_7590

    ID: 2670 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTSC 2014字符串哈希

QOJ 1639_7590

IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 企鹅QQ 企鹅QQ 【问题描述】 PenguinQQ 是中国最大、最具影响力的SNS(Social Networking Services) 网站,以实名制为基础,为用户提供日志、群、即时通讯、相册、集市等丰富强 大的互联网功能体验,满足用户对社交、资讯、娱乐、交易等多方面的需求。 小Q 是PenguinQQ 网站的管理员,他最近在进行一项有趣的研究——找出 哪些账户是同一个人注册的。经过长时间的分析,小Q 发现同一个人注册的账 户名称总是很相似的,例如Penguin1,Penguin2,Penguin3……于是小Q 决定先 对这种相似的情形进行统计。 小Q 定义,若两个账户名称是相似的,当且仅当这两个字符串等长且恰好 只有一位不同。例如“Penguin1”和“Penguin2”是相似的,但“Penguin1”和 “2Penguin”不是相似的。而小Q 想知道,在给定的𝑛个账户名称中,有多少对 是相似的。 为了简化你的工作,小Q 给你的𝑁个字符串长度均等于𝐿,且只包含大小写 字母、数字、下划线以及‘@’共64 种字符,而且不存在两个相同的账户名称。 【输入格式】 输入文件penguin.in 第一行包含三个正整数𝑁,𝐿,𝑆。其中𝑁表示账户名称 数量,𝐿表示账户名称长度,𝑆用来表示字符集规模大小,它的值只可能为2 或 64。 若𝑆等于2,账户名称中只包含字符‘0’和‘1’共2 种字符; 若𝑆等于64,账户名称中可能包含大小写字母、数字、下划线以及‘@’共 64 种字符。 随后𝑁行,每行一个长度为𝑙的字符串,用来描述一个账户名称。数据保证𝑁 个字符串是两两不同的。 【输出格式】 输出文件penguin.out 仅一行一个正整数,表示共有多少对相似的账户名称。 【样例输入1】 4 3 64 Fax fax max mac 【样例输出1】 4 第2 页 共9 页 IOI 2014 中国代表队选拔赛暨全国信息学精英赛 第一试 企鹅QQ 【样例1 说明】 4 对相似的字符串分别为:Fax 与fax,Fax 与max,fax 与max,max 与mac。 【样例输入输出2】 见选手目录下的penguin/penguin.in 与penguin/penguin.ans。 【数据规模和约定】 测试点编号 𝑁 𝐿 𝑆 1 50 10 64 2 500 100 64 3 3000 100 2 4 3000 100 64 5 30000 50 2 6 30000 50 64 7 30000 200 2 8 30000 200 64 9 30000 200 2 10 30000 200 64 第3 页 共9 页