MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1597 - Searching the Web
AOAPC II

UVaOJ 1597 - Searching the Web

Chai
2021-11-24 0:00:00在线评测阅读 487

问题描述

p1597

原题链接:UVaOJ 1597 - Searching the Web

相关说明:本题为《算法竞赛入门经典(第2版)》习题 5-10

解法一:模拟 + 集合运算

比较繁琐的一题,尤其需要注意:

  • 对于每一行最好做些预处理:全部转小写,非字母字符转空格;
  • 对于不同类型的 query 分别实现,然后再去重构代码(尽管我懒得去重构了 = =);
  • “交集”表示文章中同时出现了两个关键字,但不要求在同一行;
  • “并集”表示文章中出现过两个关键字之一;
  • 使用 ---------- 划分 query 结果中不同的文档;
  • 使用 ========== 划分不同的 query case.

下面的参考题解写得比较啰嗦,但是所用的数据结构理解性和可读性会好一些,只需要理解 word_pos[word][document_id] 是用来存储和判断对于第 document_id 份文件中存在 word 的行号的集合(可能为空)就行。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int n; cin >> n; getchar();           // N documents provided.
  vector<vector<string>> documents(n);  // documents -> document -> line
  map<string, map<int, set<int>>> word_pos;  // pos[word][document_id] -> line_id set
 
  string line, converted_line, word;
  for (int i = 0; i < n; i++) {
    int line_num = 0;
    while (getline(cin, line) && line != "**********") {
      documents[i].push_back(line);
      converted_line = line;
      for_each(converted_line.begin(), converted_line.end(),
               [](char &ch) { ch = isalpha(ch) ? tolower(ch) : ' '; });
      stringstream words(converted_line);
      while (words >> word) word_pos[word][i].insert(line_num);
      line_num++;
    }
  }
 
  int m; cin >> m; getchar();  // M queries provided.
  string querry, keyword_a, keyword_b;
  while (m--) {
    bool find_something = false;
    getline(cin, querry);
 
    if (querry.find("NOT") != string::npos) {
      querry = querry.substr(4);
      for (int i = 0; i < documents.size(); i++) {
        if (word_pos[querry][i].size() == 0) {
          cout << (find_something ? "----------\n" : "");
          for (auto line : documents[i]) cout << line << endl;
          find_something = true;
        }
      }
    } else {  // AND, OR and just one keyword
      if (querry.find("AND") != string::npos) {
        keyword_a = querry.substr(0, querry.find("AND") - 1);
        keyword_b = querry.substr(querry.find("AND") + 4);
        for (int i = 0; i < documents.size(); i++) {
          if (word_pos[keyword_a][i].size() > 0 &&
              word_pos[keyword_b][i].size() > 0) {
            cout << (find_something ? "----------\n" : "");
            set<int> lines;
            set_union(
                word_pos[keyword_a][i].begin(), word_pos[keyword_a][i].end(),
                word_pos[keyword_b][i].begin(), word_pos[keyword_b][i].end(),
                inserter(lines, lines.begin()));
            for (auto line : lines) cout << documents[i][line] << endl;
            find_something = true;
          }
        }
      } else if (querry.find("OR") != string::npos) {
        keyword_a = querry.substr(0, querry.find("OR") - 1);
        keyword_b = querry.substr(querry.find("OR") + 3);
        for (int i = 0; i < documents.size(); i++) {
          if (word_pos[keyword_a][i].size() > 0 ||
              word_pos[keyword_b][i].size() > 0) {
            cout << (find_something ? "----------\n" : "");
            set<int> lines;
            set_union(
                word_pos[keyword_a][i].begin(), word_pos[keyword_a][i].end(),
                word_pos[keyword_b][i].begin(), word_pos[keyword_b][i].end(),
                inserter(lines, lines.begin()));
            for (auto line : lines) cout << documents[i][line] << endl;
            find_something = true;
          }
        }
      } else {  // querry is only one keyword
        for (int i = 0; i < documents.size(); i++)
          if (word_pos[querry][i].size() > 0) {
            cout << (find_something ? "----------\n" : "");
            for (auto line : word_pos[querry][i]) cout << documents[i][line] << endl;
            find_something = true;
          }
      }
    }
    if (!find_something) cout << "Sorry, I found nothing." << endl;
    cout << "==========" << endl;
  }
  return 0;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz