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

柿子饼同学

P3065
5 遍过
3 h


知识点
trie, 找环


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


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

代码

1. #include <bitsdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int N = 3e5 + 5;
   
5. 
   
6. struct Node{
   
7.     char ch;
   
8.     int ed;
   
9.     vector<int> child;
   
10. } t[N];
    
11. 
    
12. int tot, n;
    
13. vector<string> s;
    
14. 
    
15. int Newnode(char c){
    
16.     tot++;
    
17.     t[tot].ch = c;
    
18.     return tot;
    
19. }
    
20. 
    
21. void Insert(int id){
    
22.     int u = 0, temp;
    
23.     bool f = 0;
    
24. 
    
25.     for(auto i : s[id]){
    
26.         f = 0;
    
27.         for(auto ed : t[u].child){
    
28.             if(t[ed].ch == i){
    
29.                 f = 1;
    
30.                 u = ed;
    
31.                 break;
    
32.             }
    
33.         }
    
34.         if(!f){
    
35.             temp = Newnode(i);
    
36.             t[u].child.emplace_back(temp);
    
37.             u = temp;
    
38.         }   
    
39.     }
    
40.     t[u].ed = 1;
    
41. }
    
42. 
    
43. bitset<30005> vis;
    
44. vector<int> e[30];
    
45. int v[30];
    
46. 
    
47. bool dfs(int u){
    
48.     v[u] = 1;
    
49.     for(auto ed : e[u]){
    
50.         if(v[ed] == 1) return 1;
    
51.         if(!v[ed] && dfs(ed)) return 1;
    
52.     }
    
53.     v[u] = -1;
    
54.     return 0;
    
55. }
    
56. 
    
57. void Query(int id){
    
58.     int u = 0, nxt, lst = 0;
    
59. 
    
60.     for(int i = 0; i < 26; i++){
    
61.         e[i].clear();
    
62.         v[i] = 0;
    
63.     }
    
64. 
    
65.     for(auto i : s[id]){
    
66.         if(t[u].ed)
    
67.             return ;
    
68.         for(auto ed : t[u].child){
    
69.             if(t[ed].ch == i){
    
70.                 nxt = ed;
    
71.                 continue;
    
72.             }
    
73.             e[i - 'a'].emplace_back(t[ed].ch - 'a');
    
74.         }
    
75.         u = nxt;
    
76.     }
    
77. 
    
78.     for(int i = 0; i < 26; i++){
    
79.         if(v[i]) continue;
    
80.         if(dfs(i)) return ;
    
81.     }
    
82.     vis[id] = 1;
    
83. }
    
84. 
    
85. int main(){
    
86.     ios::sync_with_stdio(0);
    
87.     cin.tie(0);
    
88. 
    
89.     cin >> n;
    
90.     string str;
    
91.     for(int i = 0; i < n; i++){
    
92.         cin >> str;
    
93.         s.emplace_back(str);
    
94.         Insert(i);
    
95.     }
    
96. 
    
97.     int ans = 0;
    
98.     for(int i = 0; i < n; i++){
    
99.         Query(i);
    
100.         if(vis[i]) ans++;
     
101.     }
     
102. 
     
103.     cout << ans << '\n';
     
104.     for(int i = 0; i < n; i++){
     
105.         if(vis[i]) cout << s[i] << '\n';
     
106.     }
     
107. 
     
108.     return 0;
     
109. }

复制代码

FishC

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

### 问题解析：P3065

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

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

### 具体思路

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

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

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

### 代码讲解

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <bitset>
   
4. using namespace std;
   
5. 
   
6. const int N = 3e5 + 5;
   
7. 
   
8. struct Node{
   
9.     char ch;
   
10.     int ed;
    
11.     vector<int> child;
    
12. } t[N];
    
13. 
    
14. int tot, n;
    
15. vector<string> s;
    
16. 
    
17. int Newnode(char c){
    
18.     // 每调这个函数，tot都会增加，表示新增了一个节点
    
19.     tot++;
    
20.     t[tot].ch = c;
    
21.     return tot;
    
22. }
    
23. 
    
24. void Insert(int id){
    
25.     int u = 0, temp;
    
26.     bool f = 0;
    
27. 
    
28.     for(auto i : s[id]){
    
29.         f = 0;
    
30.         for(auto ed : t[u].child){
    
31.             if(t[ed].ch == i){
    
32.                 f = 1;
    
33.                 u = ed;
    
34.                 break;
    
35.             }
    
36.         }
    
37.         if(!f){
    
38.             temp = Newnode(i);
    
39.             t[u].child.emplace_back(temp);
    
40.             u = temp;
    
41.         }   
    
42.     }
    
43.     t[u].ed = 1;
    
44. }
    
45. 
    
46. bitset<30> vis;
    
47. vector<int> e[26];
    
48. int v[26];
    
49. bool f;
    
50. 
    
51. bool dfs(int u){
    
52.     v[u] = 1; // 标记正在访问
    
53.     for(auto ed : e[u]){
    
54.         if(v[ed] == 1) return true; // 发现环
    
55.         if(!v[ed] && dfs(ed)) return true;
    
56.     }
    
57.     v[u] = 2; // 访问结束
    
58.     return false;
    
59. }
    
60. 
    
61. bool Query(int id){
    
62.     int u = 0, nxt, lst = 0;
    
63. 
    
64.     for(int i = 0; i < 26; i++){
    
65.         e[i].clear();
    
66.         v[i] = 0;
    
67.     }
    
68. 
    
69.     for(auto i : s[id]){
    
70.         // 如果碰到了结尾，而且不是自己一定有矛盾
    
71.         if(t[u].ed){
    
72.             return true;
    
73.         }
    
74.         for(auto ed : t[u].child){
    
75.             if(t[ed].ch == i){
    
76.                 nxt = ed;
    
77.                 continue;
    
78.             }
    
79.             e[t[ed].ch - 'a'].emplace_back(t[u].ch - 'a');
    
80.         }
    
81.         u = nxt;
    
82.     }
    
83. 
    
84.     for(int i = 0; i < 26; i++){
    
85.         if(v[i]) continue;
    
86.         if(dfs(i)) return true;
    
87.     }
    
88.     return false;
    
89. }
    
90. 
    
91. int main(){
    
92.     ios::sync_with_stdio(0);
    
93.     cin.tie(0);
    
94. 
    
95.     cin >> n;
    
96.     s.resize(n);
    
97.     for(int i = 0; i < n; i++){
    
98.         cin >> s[i];
    
99.         Insert(i);
    
100.     }
     
101. 
     
102.     int ans = 0;
     
103.     for(int i = 0; i < n; i++){
     
104.         if(Query(i)) ans++;
     
105.     }
     
106. 
     
107.     cout << ans << endl;
     
108.     return 0;
     
109. }

复制代码

### 总结

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

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

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

小肥狼haoran

有又学到了