[心之碎片][0623] - P3065 [USACO12DEC] First! G
P30655 遍过
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;
int tot, n;
vector<string> s;
int Newnode(char c){
tot++;
t.ch = c;
return tot;
}
void Insert(int id){
int u = 0, temp;
bool f = 0;
for(auto i : s){
f = 0;
for(auto ed : t.child){
if(t.ch == i){
f = 1;
u = ed;
break;
}
}
if(!f){
temp = Newnode(i);
t.child.emplace_back(temp);
u = temp;
}
}
t.ed = 1;
}
bitset<30005> vis;
vector<int> e;
int v;
bool dfs(int u){
v = 1;
for(auto ed : e){
if(v == 1) return 1;
if(!v && dfs(ed)) return 1;
}
v = -1;
return 0;
}
void Query(int id){
int u = 0, nxt, lst = 0;
for(int i = 0; i < 26; i++){
e.clear();
v = 0;
}
for(auto i : s){
if(t.ed)
return ;
for(auto ed : t.child){
if(t.ch == i){
nxt = ed;
continue;
}
e.emplace_back(t.ch - 'a');
}
u = nxt;
}
for(int i = 0; i < 26; i++){
if(v) continue;
if(dfs(i)) return ;
}
vis = 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) ans++;
}
cout << ans << '\n';
for(int i = 0; i < n; i++){
if(vis) cout << s << '\n';
}
return 0;
}
哈哈，看得出这个问题有点挑战性，不过不用担心，我来帮你以轻松幽默的方式理解这个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;
int tot, n;
vector<string> s;
int Newnode(char c){
// 每调这个函数，tot都会增加，表示新增了一个节点
tot++;
t.ch = c;
return tot;
}
void Insert(int id){
int u = 0, temp;
bool f = 0;
for(auto i : s){
f = 0;
for(auto ed : t.child){
if(t.ch == i){
f = 1;
u = ed;
break;
}
}
if(!f){
temp = Newnode(i);
t.child.emplace_back(temp);
u = temp;
}
}
t.ed = 1;
}
bitset<30> vis;
vector<int> e;
int v;
bool f;
bool dfs(int u){
v = 1; // 标记正在访问
for(auto ed : e){
if(v == 1) return true; // 发现环
if(!v && dfs(ed)) return true;
}
v = 2; // 访问结束
return false;
}
bool Query(int id){
int u = 0, nxt, lst = 0;
for(int i = 0; i < 26; i++){
e.clear();
v = 0;
}
for(auto i : s){
// 如果碰到了结尾，而且不是自己一定有矛盾
if(t.ed){
return true;
}
for(auto ed : t.child){
if(t.ch == i){
nxt = ed;
continue;
}
e.ch - 'a'].emplace_back(t.ch - 'a');
}
u = nxt;
}
for(int i = 0; i < 26; i++){
if(v) 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;
Insert(i);
}
int ans = 0;
for(int i = 0; i < n; i++){
if(Query(i)) ans++;
}
cout << ans << endl;
return 0;
}
### 总结
通过构建字典树和使用DFS来检测环，是这个问题的核心操作。你可以想象一下，把所有的字符串像大象那样塞进字典树，然后拿起你的探险帽，进入图中寻找有没有循环的小路。
希望这些解释能让你乐在其中，轻松理解！如果还有其他问题或需要进一步解释的地方，请随时提问哦！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 有又学到了
页:
[1]