SRM480 DIV1 250 分

发表于 分类于

好吧，我承认这题很简单 (不会 STL 的孩子把这句话无视)，看错题目导致成功挂零。。。无语死了。。。

今天的 250 不是很难，要点有：

  1. 对字符串的切割，手写切割函数比较保险，当然会用 STL 的字符串流的可以直接按照空格切割。
  2. 查找关键字，嗯，这里有个好技巧，用红黑树 (set) 来维护全部的危险关键字即可。
  3. 判断条件，只有当危险关键字超过定值的时候才是危险网站，否则不是。
  4. 当一个网站是危险网站的时候，他的全部关键字都是危险的，这时候，我们要把全部的关键字加入红黑树中管理。
  5. 由于 4 的原因，要扫描 NN 次 (类似贝尔曼福德算法)，加入的顺序就不是原来的顺序了，这里在最后对其 id 进行一次排序，可以用一个映射 map 来存储下标。

我的代码 (核心部分)：

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
set<string> st;
map<string, int> id;
bool use[60];

bool comp(const string& a, const string& b) { return id[a] < id[b]; }

bool check(const string& key, int num) {
  int len = key.length();
  string ret;
  vector<string> v;
  int cnt = 0, size = 0;
  for (int i = 0; i < len; i++) {
    ret = "";
    while (i < len && key[i] != ' ') {
      ret += key[i];
      i++;
    }
    v.push_back(ret);
  }
  size = v.size();
  for (int i = 0; i < size; i++)
    if (st.find(v[i]) != st.end()) {
      cnt++;
    }
  if (cnt >= num) {
    for (int i = 0; i < size; i++) st.insert(v[i]);
    return true;
  } else
    return false;
}

class InternetSecurity {
 public:
  vector<string> determineWebsite(vector<string> add, vector<string> key,
                                  vector<string> dang, int num) {
    int n = add.size();
    vector<string> v;
    memset(use, 0, sizeof(use));
    id.clear();
    st.clear();
    for (int i = 0; i < n; i++) id[add[i]] = i;
    int size = dang.size();
    for (int i = 0; i < size; i++) st.insert(dang[i]);
    for (int k = 0; k < n; k++)
      for (int i = 0; i < n; i++)
        if (!use[i] && check(key[i], num)) {
          use[i] = true;
          v.push_back(add[i]);
        }
    sort(v.begin(), v.end(), comp);
    return v;
  }
};

总结：看题仔细，不要因为题目难懂就囫囵吞枣，最近开始讨厌看题，这是不好的现象。