2018-03-11 刷题

1078 hashing ：简单 二次探查 质数

之前写过的题，这次很顺利就写完了。对比之前写的，这次写的要偷懒多了，也快多了。进步进步（拍手）。

几个细节：

• 虽然给的表长只有10000，但是你要找质数呀，得多开点才行。
• 做 Quadratic probing 的时候，如果找了 msize 次还没有找到位置，那就是找不到了。因为之后数的平方除以 msize 又和前面重复了。

1077 Kuchiguse 最长公共后缀 输入 简单

这次又要输入一个句子，其中可能有空格的了。找到了办法，**用scanf("%[^\n]", s[i]); **这样，就只会读除了 \n 之外的字符，包括空格符了。不过，在它的前后都需要把 \n 额外读走，否则下一次什么都读不到。

要找多个句子的最长公共后缀，我不知道两两会不会超时，就直接从最后一位开始全体对比了。结果全部 0 ms，这样的 case 多不够意思啊……

1076. Forwards on Weibo bfs，dfs不行

这道题之前做过，本来以为会很顺利，结果比第一遍做还卡。。。刚开始想用 dfs，后来发现这样是错的，这里只能用 bfs。遂修改，但是自己把命名弄得太乱了，老写错，后来才知道自己有多蠢。

这道题给了个有环的图，要从一个点出发，统计L层以内的点。

刚开始写的 dfs 对已经发现过的点不再重复看，就是第二行第二个条件：

void dfs(int id, int level) {
    if (level > L || forward[id]) return;
    forward[id] = true;
    for (int i = 1; i <= N; i++) {
        if (follow[i][id]) { //i followed me
            dfs(i, level + 1);
        }
    }
}

结果有些点走较长的路径标记过了，再遇到更短的路径的时候已经不要它了，致使它的有些孩子本来没到L层的，活生生得进不去了。 比如这个 5 和 6 的孩子，就没机会了。

后来写的bfs：

void bfs(int id) {
    int queue[1001], start = 0, end = 1;
    bool inq[1001] = { 0 };
    queue[0] = id;
    inq[id] = true;
    while (end > start) {
        id = queue[start++];
        if (level[id] > L) break;
        nforward++;
        for (int i = 1; i <= N; i++) {
            if (follow[i][id] && !inq[i]) { //i followed me
                level[i] = level[id] + 1;
                queue[end++] = i;
                inq[i] = true;
            }
        }
    }
}

最后又改了一下 dfs，去掉了第二个条件，这样即便访问过也能再次发现。能用是能用，就是重复太多有点耗时，有个 case 超时了。

void dfs(int id, int level) {
    if (level > L) return;
    forward[id] = true;
    for (int i = 1; i <= N; i++) {
        if (follow[i][id]) { //i followed me
            dfs(i, level + 1);
        }
    }
}