Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

1:倒排索引

描述

给定一些文档，要求求出某些单词的倒排表。

对于一个单词，它的倒排表的内容为出现这个单词的文档编号。

输入

第一行包含一个数N，1 <= N <= 1000，表示文档数。
接下来N行，每行第一个数c_i，表示第i个文档的单词数。接下来跟着c_i个用空格隔开的单词，表示第i个文档包含的单词。文档从1开始编号。1 <= c_i <= 100。
接下来一行包含一个数M，1 <= M <= 1000，表示查询数。
接下来M行，每行包含一个单词，表示需要输出倒排表的单词。
每个单词全部由小写字母组成，长度不会超过256个字符，大多数不会超过10个字符。

输出

对于每一个进行查询的单词，输出它的倒排表，文档编号按从小到大排序。
如果倒排表为空，输出"NOT FOUND"。

样例输入

3
2 hello world
4 the world is great
2 great news
4
hello
world
great
pku

样例输出

1
1 2
2 3
NOT FOUND

---

離線處理，將每個請求單詞都先讀進來，再掃描一次字典，將答案映射回去。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;
char s[1024], query[1024][260];
vector<string> doc[1024];
map<string, set<int> > Q;
set<int> R[1024];
int main() {
    int n, m;
    int i, j, k;
    scanf("%d", &n);
    for(i = 0; i < n; i++) {
        scanf("%d", &m);
        for(j = 0; j < m; j++) {
            scanf("%s", s);
            doc[i].push_back(s);
        }
    }
    scanf("%d", &m);
    for(i = 0; i < m; i++) {
        scanf("%s", query[i]);
        Q[query[i]].insert(i);
    }
    for(i = 0; i < n; i++) {
        for(j = 0; j < doc[i].size(); j++) {
            map<string, set<int> >::iterator it = Q.find(doc[i][j]);
            if(it != Q.end()) {
                for(set<int>::iterator jt = it->second.begin();
                    jt != it->second.end(); jt++) {
                    R[*jt].insert(i);
                }
            }
        }
    }
    for(i = 0; i < m; i++) {
        int flag = 0;
        for(set<int>::iterator it = R[i].begin();
            it != R[i].end(); it++) {
            if(flag)    putchar(' ');
            flag = 1;
            printf("%d", *it + 1);
        }
        if(R[i].size() == 0)
            printf("NOT FOUND");
        puts("");
    }
    return 0;
}

2:倒排索引查询

描述

现在已经对一些文档求出了倒排索引，对于一些词得出了这些词在哪些文档中出现。

要求对于倒排索引实现一些简单的查询，即查询某些词同时出现，或者有些词出现有些词不出现的文档有哪些。

输入

第一行包含一个数N，1 <= N <= 1000，表示倒排索引表的数目。
接下来N行，每行第一个数c_i，表示这个词出现在了多少个文档中。接下来跟着c_i个数，表示出现在的文档编号，编号不一定有序。1 <= c_i <= 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 個集合，開始對其集合著手替除的操作。

#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    int i, j, k, x;
    vector<int> keyword[1024];
    set<int> keywordII[1024];
    scanf("%d", &n);
    for(i = 0; i < n; i++) {
        scanf("%d", &m);
        while(m--) {
            scanf("%d", &x);
            keyword[i].push_back(x);
            keywordII[i].insert(x);
        }
    }
    scanf("%d", &m);
    int c[1024];
    while(m--) {
        for(i = 0; i < n; i++)
            scanf("%d", &c[i]);
        set<int> ret;
        for(i = 0; i < n; i++) {
            if(c[i] == 1) {
                for(j = 0; j < keyword[i].size(); j++)
                    ret.insert(keyword[i][j]);
                break;
            }
        }
        for(i = 0; i < n; i++) {
            if(c[i] == -1) {
                for(j = 0; j < keyword[i].size(); j++) {
                    ret.erase(keyword[i][j]);
                }
            }
            if(c[i] == 1) {
                for(set<int>::iterator it = ret.begin();
                    it != ret.end(); ) {
                    if(keywordII[i].find(*it) == keywordII[i].end())
                        ret.erase(it++);
                    else
                        ++it;
                }
            }
        }
        if(ret.size() == 0)
            puts("NOT FOUND");
        else {
            int f = 0;
            for(set<int>::iterator it = ret.begin();
                it != ret.end(); it++) {
                if(f)    putchar(' ');
                f = 1;
                printf("%d", *it);
            }
            puts("");
        }
    }
    return 0;
}