Blocked websites CodeChef – WSITES01

前言

emmmm这题毒瘤啊,本来算法对的,因为输入问题调了半天还是WA。还多亏wuyiqi大神解围。

题意

Mike 是大学里的网管。他的一个主要任务就是建立一个有效的防火墙,阻止学生们访问特定
的网站。
防火墙可以访问N个网站,其中一些是需要被屏蔽的。网站的名字仅包含小写英文字母。
防火墙的屏蔽功能通过若干过滤器实现。一个过滤器是一个字符串,它可以屏蔽所有名字以
该字符串作为前缀的网站。你需要最小化过滤器的串长之和,使得防火墙可以屏蔽所有应当被屏
蔽的网站,但不会屏蔽掉不该被屏蔽的网站。

样例

Input:

4
– codeforces
+ codechef
– youtube
+ google

Output:

2
codef
y

约定

  • 1\leq N\leq 2\times 10^5
  • 输入中名字字符串的长度之和\leq 2\times 10^5
  • 任意两个网站的名字不同

分析

裸的字典树。
当然关于建树有很多说法,有些同学是建两棵的,有些同学则是只为被屏蔽的网站建一棵字典树。而我,是建一棵然后把所有网站都丢进去的。(天生与众不同造就的BUG多
这题还是很好做的,我们对于字典树的每一个节点维护三个信息:blocked(即被屏蔽)的网站个数、unblocked(即不被屏蔽)的网站个数,以及是否有被屏蔽的网站的字符串在这个节点结束。
那么我们每搜到一个节点,分为如下几种情况:

  • 当前节点没有unblocked的网站了,那么一定有blocked的网站,那么我们就把当前的前缀存入答案。
  • 当前节点有unblocked的网站,但没有blocked的网站,那么我们没有必要继续搜索这个点了,因为我们不需要过滤器。
  • 当前节点有unblocked的网站,但有blocked的网站在此结尾了。那么我们一定要把这个点的前缀作为过滤器,但是这样会造成unblocked的网站被屏蔽,问题无解。
  • 当前节点既有unblocked的网站也有blocked的网站,且没有blocked的网站在此结尾。我们还需要继续搜索下去。
    到这里解法就十分清楚了,但是还有一个问题。
    就是输入。

我已开始是把整行一起放在一个char[]里用fgets()读入的,但是我取’+’和’-‘的时候直接取了字符串第一个,这样可能会被行首的空格干扰。然后如果用getline先读入一个string,在把它放在stringstream里依次输给一个两个字符串时,因为数据并不合法,会存在不在同一行的情况,因此这样也会WA。所以就得用scanf(“%s”)依次读入两个字符串,这样最稳定。(因为scanf()忽略所有空格和换行符)。还是多亏了吴老师的讲解。以后尽量使用scanf()读入,切记,切记!

参考程序

// vjudge 244023 C
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
const int MAXN = 200100;
struct Node {
    int cnt_bl, cnt_unbl, id;
    bool bl_end_here;
    Node() { cnt_bl = cnt_unbl = 0; bl_end_here = false; }
    operator bool() const { return cnt_bl || cnt_unbl; }
};
// 吴老师建议以后尽量减少这样的封装,可能造成内存超限
class Tire {    // emmm这里把Trie打成Tire了...
private:
    Node T[MAXN][28];
    int sz;
public:
    Tire() { sz = 1; }
    void insert(const char st[], bool is_bl) {
//      插入一个串,is_bl标记是否为blocked的网站
        int i, v, rt = 0;
        for (i = 0; st[i]; i++) {
            v = st[i] - 'a';
            if (!T[rt][v]) T[rt][v].id = sz++;  // 动态开点
            if (is_bl) T[rt][v].cnt_bl++;
            else T[rt][v].cnt_unbl++;
            if (!st[i + 1] && is_bl) T[rt][v].bl_end_here = true;   // 标记是否一个blocked串在此结尾
            rt = T[rt][v].id;
        }
    }
    bool dfs(int rt, int dep);
} tr;

int N, tot_s = 0;
char que[MAXN], input[MAXN];
std::string Ans[MAXN];

int main() {
    using namespace std;
    scanf("%d", &N);
    int i, j;
    char ch;
    for (i = 0; i < N; i++) {
        scanf("%s", input);
        ch = input[0];
        scanf("%s", input);
        tr.insert(input, ch == '-');
    }
    if (tr.dfs(0, 0)) {
        cout << tot_s << endl;
        for (i = 0; i < tot_s; i++) cout << Ans[i] << endl;
    }
    else cout << "-1\n";
    return 0;
}

bool Tire::dfs(int rt, int dep) {
    bool vis = false, res = true;
//  vis标记是否为叶子节点,res表示是否有解
    for (int i = 0; i < 26; i++)
        if (T[rt][i]) {
            vis = true;
            que[dep] = 'a' + i; 
//          遍历分情况讨论
//          吴老师建议少写这样的else,即使可以提高效率,当然这里实际上没有问题
            if (!T[rt][i].cnt_unbl) Ans[tot_s++] = std::string(que, dep + 1);
            else if (T[rt][i].bl_end_here) return false;
            else if (T[rt][i].cnt_bl) res &= dfs(T[rt][i].id, dep + 1);
        }
    return vis ? res : vis;
}

总结

最近经常因为输入问题调试不出,但是积累了很多经验。以后特别在试场上还是要选择尽量稳定的读入方式。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注