Problem H: 图像匹配
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$28$ |
正确数量 |
$3$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
字符串 |
当前分类(单击移除)：
字符串
单击选择分类：
小x申请了一个创新项目，内容是进行相似图像匹配。他的实现方法是这样的：
1、 建立一个相当大的图像库，里面存放数以万计的图片，每张图片使用一个字符串命名（如A1000.bmp），字符串的长度小于或等于20字符（如A1000.bmp为9字符）。
2、 为每一张图片生成一个Hash值，这个Hash值由36位01字符串构成（如000011011101001001100001110000100111）。
3、 给出一张陌生的图片，计算它的Hash值。
4、 根据上步计算出的Hash值，比较查找图片库中与这张图片最相似的一张或几张图片。
现在小x需要你帮助他来完成第4步，即小x给出图片名和Hash值，由你在图片库中查找一张或几张最相似的图片，输出图片名、相似度。
相似度这样计算：36 - 两个Hash值的汉明距离，相似度越大，两张图片越接近。
汉明距离这样计算：两个等长字符创之间的汉明距离是两个字符串对应位置的字符不同的个数，如10000和01001之间的汉明距离是3，10000和10001之间的汉明距离是1。
第一行为一个整数N，表示图像库中的图片数目(0 < N <= 10000)
接下来N行，每行为图片名和对应的36位Hash值，图片名和Hash值之间由一个空格隔开。
第N+2行为一个整数Q，表示接下来要匹配的图片数目(0 < Q <= 100)
接下来Q行，每行为待匹配的图片名和对应的36位Hash值，图片名和Hash值之间由一个空格隔开。
对于每张待匹配的图片，第一行输出一个整数X，表示图片库中有X张图片与它最相似。
第二行输出一个整数，是图片的相似度。
接下来X行，每行输出一张图片的名称。
注意当有多张图片可以匹配时，按输入中图片给出的顺序排列。
5
Image1000.bmp 101110001011011101010000101010011010
Image1001.bmp 001011001010110110010100011010101000
Image1002.bmp 101001011100101011011100101010110110
Image1003.bmp 100011100001101101111101010010101000
Image1004.bmp 001001011100101011011100101010110111
2
Image1005.bmp 101011001010110110010100011010101000
Image1006.bmp 101001011100101011011100101010110111
1
35
Image1001.bmp
2
35
Image1002.bmp
Image1004.bmp
图片名称长度不相等！