[心之碎片][0623] - P3065 [USACO12DEC] First! G

柿子饼同学

P3065
5 遍过
3 h


知识点
trie, 找环


思路
把所有 str 放进字典树, 如果有前缀就一定不是, 如果有公共前缀就不管它
对于每个分支, 用优先级连边 eg.  a > b : a --> b
判断: 如果这个图里面有环就自己矛盾, 不可能排在第一个


需要进步的地方
思路中的找环没想出来, 还是需要更普遍的东西, 而不是赋值这种可能会出错的
dfs 找环的流程, 分三个状态 : 0 未访问, 1 访问中, 2 访问后
dfs 中如果去到的节点也是 1 , 就有环

代码

#include <bitsdc++.h>
using namespace std;

const int N = 3e5 + 5;

struct Node{
    char ch;
    int ed;
    vector<int> child;
} t[N];

int tot, n;
vector<string> s;

int Newnode(char c){
    tot++;
    t[tot].ch = c;
    return tot;
}

void Insert(int id){
    int u = 0, temp;
    bool f = 0;

    for(auto i : s[id]){
        f = 0;
        for(auto ed : t[u].child){
            if(t[ed].ch == i){
                f = 1;
                u = ed;
                break;
            }
        }
        if(!f){
            temp = Newnode(i);
            t[u].child.emplace_back(temp);
            u = temp;
        }   
    }
    t[u].ed = 1;
}

bitset<30005> vis;
vector<int> e[30];
int v[30];

bool dfs(int u){
    v[u] = 1;
    for(auto ed : e[u]){
        if(v[ed] == 1) return 1;
        if(!v[ed] && dfs(ed)) return 1;
    }
    v[u] = -1;
    return 0;
}

void Query(int id){
    int u = 0, nxt, lst = 0;

    for(int i = 0; i < 26; i++){
        e[i].clear();
        v[i] = 0;
    }

    for(auto i : s[id]){
        if(t[u].ed)
            return ;
        for(auto ed : t[u].child){
            if(t[ed].ch == i){
                nxt = ed;
                continue;
            }
            e[i - 'a'].emplace_back(t[ed].ch - 'a');
        }
        u = nxt;
    }

    for(int i = 0; i < 26; i++){
        if(v[i]) continue;
        if(dfs(i)) return ;
    }
    vis[id] = 1;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    string str;
    for(int i = 0; i < n; i++){
        cin >> str;
        s.emplace_back(str);
        Insert(i);
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        Query(i);
        if(vis[i]) ans++;
    }

    cout << ans << '\n';
    for(int i = 0; i < n; i++){
        if(vis[i]) cout << s[i] << '\n';
    }

    return 0;
}

FishC

哈哈，看得出这个问题有点挑战性，不过不用担心，我来帮你以轻松幽默的方式理解这个P3065题目和它背后的算法吧！

### 问题解析：P3065

首先，我们需要理解这个问题想让我们解决什么。简单来说，它涉及到构建一个字典树（Trie）并判断在这个结构里是否有环存在。以下是问题的具体步骤：

1. **构建一个字典树（Trie）**：将所有的字符串插入字典树中。
2. **检测环（Cycle Detection）**：确定是否存在任何环。如果有环，表明存在自相矛盾的情况。

### 具体思路

1. **插入字典树**：
   - 对于每个新插入的字符串，检查其前缀是否已经存在于字典树中，如果有，不需要再插入新的节点。
   
2. **优先级连边**：
   - 根据字母顺序建立图的边，例如，对于 `a > b`，你可以创建 `a -> b` 的边。

3. **检测环**：
   - 使用深度优先搜索（DFS）来检测是否存在环。可以设置三个状态：0（未访问），1（访问中），2（已访问）。

如果在DFS过程中访问到一个正在访问中的节点（状态为1），那么就说明存在环。

### 代码讲解

来，咱们把代码逐步拆解并解释——通过幽默的方式让你记住：

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

const int N = 3e5 + 5;

struct Node{
    char ch;
    int ed;
    vector<int> child;
} t[N];

int tot, n;
vector<string> s;

int Newnode(char c){
    // 每调这个函数，tot都会增加，表示新增了一个节点
    tot++;
    t[tot].ch = c;
    return tot;
}

void Insert(int id){
    int u = 0, temp;
    bool f = 0;

    for(auto i : s[id]){
        f = 0;
        for(auto ed : t[u].child){
            if(t[ed].ch == i){
                f = 1;
                u = ed;
                break;
            }
        }
        if(!f){
            temp = Newnode(i);
            t[u].child.emplace_back(temp);
            u = temp;
        }   
    }
    t[u].ed = 1;
}

bitset<30> vis;
vector<int> e[26];
int v[26];
bool f;

bool dfs(int u){
    v[u] = 1; // 标记正在访问
    for(auto ed : e[u]){
        if(v[ed] == 1) return true; // 发现环
        if(!v[ed] && dfs(ed)) return true;
    }
    v[u] = 2; // 访问结束
    return false;
}

bool Query(int id){
    int u = 0, nxt, lst = 0;

    for(int i = 0; i < 26; i++){
        e[i].clear();
        v[i] = 0;
    }

    for(auto i : s[id]){
        // 如果碰到了结尾，而且不是自己一定有矛盾
        if(t[u].ed){
            return true;
        }
        for(auto ed : t[u].child){
            if(t[ed].ch == i){
                nxt = ed;
                continue;
            }
            e[t[ed].ch - 'a'].emplace_back(t[u].ch - 'a');
        }
        u = nxt;
    }

    for(int i = 0; i < 26; i++){
        if(v[i]) continue;
        if(dfs(i)) return true;
    }
    return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    s.resize(n);
    for(int i = 0; i < n; i++){
        cin >> s[i];
        Insert(i);
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        if(Query(i)) ans++;
    }

    cout << ans << endl;
    return 0;
}

### 总结

通过构建字典树和使用DFS来检测环，是这个问题的核心操作。你可以想象一下，把所有的字符串像大象那样塞进字典树，然后拿起你的探险帽，进入图中寻找有没有循环的小路。

希望这些解释能让你乐在其中，轻松理解！如果还有其他问题或需要进一步解释的地方，请随时提问哦！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

小肥狼haoran

有又学到了