总时间限制:1000ms 内存限制: 131072kB 描述 现在已经对一些文档求出了倒排索引，对于一些词得出了这些词在哪些文档中出现的列表。 要求对于倒排索引实现一些简单的查询，即查询某些词同时出现，或者有些词出现有些词不出现的文档有哪些。 输入 第一行包含一个数N，1 <= N <= 100，表示倒排索引表的数目。 接下来N行，每行第一个数ci，表示这个词出现在了多少个文档中。接下来跟着ci个数，表示出现在的文档编号，编号不一定有序。1 <= ci <= 1000，文档编号为32位整数。 接下来一行包含一个数M，1 <= M <= 100，表示查询的数目。 接下来M行每行N个数，每个数表示这个词要不要出现，1表示出现，-1表示不出现，0表示无所谓。数据保证每行至少出现一个1。 输出 共M行，每行对应一个查询。输出查询到的文档编号，按照编号升序输出。 如果查不到任何文档，输出”NOT FOUND”。 样例输入
3 3 1 2 3 1 2 1 3 3 1 1 1 1 -1 0 1 -1 -1样例输出
NOT FOUND 1 3 1思路 1 对应每个单词 维护一个文章set集合
n = int(input()) info = dict((i,set()) for i in range(n)) for wordId, articles in info.items(): articles.update(input().split()[1:]) m = int(input()) for _ in range(m): ans = None for wordId, v in enumerate(input().split()): if v == '1': ans = ans.intersection(info[wordId]) if ans is not None else info[wordId] elif v == '-1' and ans: ans = [articleIndex for articleIndex in ans if articleIndex not in info[wordId]] if not ans: print("NOT FOUND") else: ans = list(ans) ans.sort() print(" ".join(ans))思路二 借用bitmap思想 假定最多10000篇文章 对于第i个word 维护一个 10000个bit位Ai 表示8000篇文章 1–文章包含单词 0 –不包含
算法 查 包含 第i 个单词 和 第j 个单词的集合 A = Ai&Aj 查 包含 第i个单词 但 不包含第j 个单词的集合 A = Ai&（~Aj）
解决问题：
10000个bit 和 文章编号articleId 对应关系;
用int map[10000]来存储 map[i]=articleId ;
位图的存储；
char bit[N][10000/8]; // 第i个word的位图 用10000/8个字节表示 即bit[i];
位图操作； 1、第i个单词 出现在文档map[k]=articleId中, 对应位=1 *((int *)(bit[i])+k/INTBL) |= 1<<(k%INTBL); // eg k=32 32bit个一组 内存分布 00…00 00..01 00..00 2、&操作 以4个字节=1个int型为基本单位进行求&； for(k=0; k<10000/32; k++) ((int *)(bit[i])+k) & ((int *)(bit[j])+k)
代码如下 内存 1632kB 时间 51ms
#include <stdio.h> #include <stdlib.h> #define BYTEL (sizeof(byte)) #define INTL (sizeof(int)) #define INTBL (INTL*BYTEL) #define N 100 #define AN (INTBL*1000) // 文章数量 INTBL的倍数 方便后续处理 char bit[N][AN/BYTEL]; int map[AN]; // 存储文章编号－索引映射； 把文章编号映射为0-AN的索引编号 int ansOrd[AN]; // 有序答案 /* * 打印 地址p 长度为length*8 的内存中的 bit值 */ int pp(char *p, int length) { printf("%d ", p); int i,j, *q=(int *)p; for(i=0; i<length/INTL; i++, q++) { for(j=INTBL-1;j>=0;j--) { if( (*q) & (1<<j) ) printf("1"); else printf("0"); } printf(" "); } printf("\n"); } // 把文章编存放到map中 保证map的长度>=文章数 int getId(int n) { int i=0, begin=0; begin = n%AN; for(i=begin; map[i]!=-1 && map[i]!=n; ) { i = (i+1)%AN; if( i==begin ) return -1; } map[i] = n; return i; //返回对应的索引 } int test4193() { int i, j, k, v, u, n, m; int *p, *q; char ans[AN/BYTEL]; memset(map, -1, sizeof(map)); // 读数据 i = 0; scanf("%d", &n); while( i<n ) { scanf("%d", &c); while( c-- ) { scanf("%d", &k); k = getId(k); //找到文档对应的map索引 // 第i个单词 出现在文档索引k中 *((int *)(bit+i)+k/INTBL) |= 1<<(k%INTBL); } // pp(bit+i, AN/BYTEL); i++; } // 判断 scanf("%d", &m); while(m--) { memset(ans, -1, sizeof(ans)); //默认都符合条件 // 对每一个单词遍历 for(i=0; i<n; i++) { scanf("%d", &k); // 包含; 并操作 if(k==1) for(j=0; j<AN/INTBL; j++) { *((int *)ans+j) &= *((int *)(bit+i)+j); // ans &= bit[i] } // 不包含; 取反后 求并集 else if(k==-1) for(j=0; j<AN/INTBL; j++) { *((int *)ans+j) &= ~ *((int *)(bit+i)+j); // ans &= ~ bit[i] } } // 统计答案 u=-1; // pp((char*)ans, sizeof(ans)); //显示内存bit值 for(i=0, p=(int *)ans; i<AN/INTBL; i++, p++) { for(j=0;j<INTBL;j++) //对每一位遍历 { // bit=1时 把对应的文章编号有序插入ansOrd中 if( (*p) & (1<<j) ) { v=map[i*INTBL+j]; k=u; while( k>=0 && ansOrd[k] > v ) { ansOrd[k+1] = ansOrd[k]; k--; } ansOrd[k+1]=v; u++; } } } // 打印答案 if(u==-1) { printf("NOT FOUND\n"); } else { printf("%d", ansOrd[0]); for(k=1; k<=u; k++) printf(" %d", ansOrd[k]); printf("\n"); } } }