1022. Digital Library

原创
2013/09/09 15:51
阅读数 147

这个题目看似可以用简单的线性搜索做出来,但是线性搜索其实会超时。所以需要用到索引,按属性值来索引。只要想到了这一点,题目本身没有任何的trick。

N=int(raw_input())
indexs=[{},{},{},{},{}]  #索引表,分别对应5个属性
for i in range(0,N):
	id=raw_input()
	attrs=[raw_input(),raw_input(),raw_input(),raw_input(),raw_input()] #输入值
	for ii in range(0,5): #创建基于属性的索引,即倒排索引
		attr=attrs[ii]
		if ii==2:
			for key in attr.split():   #对关键字属性的处理
				if not indexs[ii].has_key(key):
					indexs[ii][key]=[]
				indexs[ii][key].append(id)
		if not indexs[ii].has_key(attrs[ii]): #其他属性的处理
			indexs[ii][attrs[ii]]=[]
		indexs[ii][attrs[ii]].append(id)
		
for index in indexs:
	for it in index:
		index[it].sort() #对所有的索引表进行排序
M=int(raw_input())
for i in range(0,M):
	line=raw_input()
	lines=line.split(":")
	num=int(lines[0])-1
	key=lines[1][1:]
	isFind=False
	print line
	if indexs[num].has_key(key): #基于索引表进行查找
		for it in indexs[num][key]:
			print it 
	else:
		print "Not Found"

展开阅读全文
打赏
0
0 收藏
分享
加载中
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部