Udebug过了,但TLE了
查看原帖
Udebug过了,但TLE了
565669
Marrelia楼主2024/7/7 07:10

rt,有无大佬帮忙看一下

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>

// Words存储每个词的位置
std::map<std::string, std::vector<std::pair<int, int>>> Words;
std::vector<std::string> doc[110];
std::string TEMP;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  int n;
  std::cin >> n;
  std::getline(std::cin, TEMP);
  for (int i = 1; i <= n; ++i) {
    std::string s;
    s.clear();
    std::getline(std::cin, s);
    while (s[0] != '*') {
      doc[i].push_back(s);
      std::string preWord;
      preWord.clear();
      s += ' ';
      for (auto item : s) {
        if (tolower(item) <= 'z' && tolower(item) >= 'a') {
          preWord += tolower(item);
        } else if (!preWord.empty()) {
          if (!Words.count(preWord))
            Words[preWord] = std::vector<std::pair<int, int>>();
          Words[preWord].push_back({i, doc[i].size() - 1});
          // std::cout << preWord << " ";
          preWord.clear();
        }
      }
      // std::cout << std::endl;

      std::getline(std::cin, s);
    }
    // std::cout << std::endl;
  }

  /*  for (int i = 1; i <= n; ++i) {
      for (int j = 0; j < doc[i].size(); ++j) {
        std::cout << doc[i][j] << std::endl;
      }
      std::cout << "--------\n";
    }
    std::cout << "\n\n";*/

  int m;
  std::cin >> m;

  std::getline(std::cin, TEMP);
  while (m--) {
    std::string s;
    std::getline(std::cin, s);
    s += ' ';
    std::string opt[3];
    int cnt = 0;
    for (auto item : s) {
      if (tolower(item) <= 'z' && tolower(item) >= 'a') {
        opt[cnt] += item;
      } else if (!opt[cnt].empty()) {
        ++cnt;
      }
    }
    // cnt = 1表示是第一种询问
    // cnt = 2表示是第四种
    // cnt = 3表示是第二,三种
    std::vector<std::pair<int, int>> A = Words[cnt != 2 ? opt[0] : opt[1]], B;
    if (cnt == 3) B = Words[opt[2]];
    if (cnt != 2) {
      std::set<std::pair<int, int>> ans, tmp;
      ans.insert(A.begin(), A.end());
      // 并集
      if (opt[1][0] == 'O') {
        ans.insert(B.begin(), B.end());
      }
      // 交集
      if (opt[1][0] == 'A') {
        std::map<int, std::vector<std::pair<int, int>>> P;
        std::map<int, bool> P2;
        for (const auto& item : A) P[item.first].push_back(item);
        ans.clear();
        for (const auto& item : B) {
          if (P.count(item.first)) {
            if (!P2[item.first]) {
              P2[item.first] = true;
              ans.insert(P[item.first].begin(), P[item.first].end());
            }
            ans.insert(item);
          }
        }
      }
      if (ans.empty())
        std::cout << "Sorry, I found nothing.\n";
      else {
        int preIdx = (*ans.begin()).first;
        for (auto itr = ans.begin(); itr != ans.end(); ++itr) {
          int idx = (*itr).first, line = (*itr).second;
          if (idx != preIdx) std::cout << "----------\n";
          std::cout << doc[idx][line] << '\n';
          preIdx = idx;
        }
      }
    } else {
      // 先把全部序号添进来,再删除包含A的
      std::set<int> ans;
      for (int i = 1; i <= n; ++i) ans.insert(i);
      for (const auto& item : A) ans.erase(item.first);
      if (ans.empty())
        std::cout << "Sorry, I found nothing.\n";
      else {
        for (auto itr = ans.begin(); itr != ans.end(); ++itr) {
          if (itr != ans.begin()) {
            std::cout << "----------\n";
          }
          int idx = *itr;
          for (const auto& str : doc[idx]) std::cout << str << '\n';
        }
      }
    }
    std::cout << "==========";
    if (m >= 1) std::cout << std::endl;
  }
  return 0;
}
2024/7/7 07:10
加载中...