生活随笔
收集整理的这篇文章主要介绍了
C. Code a Trie（Trie+dfs+贪心）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
C. Code a Trie
大佬题解，代码基本就是抄的
对于每一个值计算所有串的LCA，也就是最长公共前缀，将该节点（Trie树的节点）标记，对于这些字符串在LCA下面的点一定不存在（如果存在他们不会返回相同的值）
每个Trie树中的节点只能被标记一次，并且从跟到LCA路径上的变必须存在
dfs贪心计算每个子树中最少的节点
插入时统计cnt[u]表示它的子树中被标记为LCA的点的数量
- 如果cnt[u]>1，这个点必选，如果说该节点没被标记为LCA，那么它可以替代它一个儿子称为那个值的LCA，如果被标记为LCA，它的儿子被标记那就必须选。
- 如果cnt[u]=1，贪心选择该点，儿子不选
- 如果cnt[u]=0，贪心不选
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<random>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std
;
typedef long long ll
;
typedef pair
<ll
,int> pli
;
typedef pair
<int,int> pii
;
const int N
=500010;
int n
,a
[N
],b
[N
],cnt
[N
],ans
;
string s
[N
];
vector
<string
> g
[N
];
int tree
[N
][30],idx
;
bool lca
[N
];
void init()
{cin
>>n
;int m
=0;for(int i
=1;i
<=n
;i
++){cin
>>s
[i
]>>a
[i
];m
+=s
[i
].size();g
[i
].clear();}idx
=0;for(int i
=0;i
<=m
;i
++)memset(tree
[i
],0,sizeof tree
[i
]);for(int i
=0;i
<=m
;i
++) lca
[i
]=0,cnt
[i
]=0;
}
bool cmp(string x
,string y
)
{return x
.size()<y
.size();
}
bool check(vector
<string
> &v
)
{sort(v
.begin(),v
.end(),cmp
);int len
=0;for(int i
=0;i
<v
[0].size();i
++){bool ok
=1;for(int j
=0;j
<v
.size()&&ok
;j
++)if(v
[j
][i
]!=v
[0][i
]) ok
=0;if(ok
) len
++;else break;}int p
=0;for(int i
=0;i
<len
;i
++){cnt
[p
]++;int c
=v
[0][i
]-'a';if(tree
[p
][c
]==-1) return 0; if(!tree
[p
][c
]) tree
[p
][c
]=++idx
;p
=tree
[p
][c
];}if(lca
[p
]) return 0;lca
[p
]=1;cnt
[p
]++;for(int i
=0;i
<v
.size();i
++){if(v
[i
].size()<=len
) continue; int c
=v
[i
][len
]-'a';if(tree
[p
][c
]>0) return 0;tree
[p
][c
]=-1;}return 1;
}
void dfs(int u
)
{if(cnt
[u
]>1) ans
++;bool fl
=lca
[u
]==0;for(int i
=0;i
<26;i
++){int son
=tree
[u
][i
];if(!son
||son
==-1) continue;if(cnt
[son
]==1){if(!fl
) ans
++;else fl
=0;}else dfs(son
);}
}
void work(int ca
)
{int m
=0;for(int i
=1;i
<=n
;i
++)b
[++m
]=a
[i
];sort(b
+1,b
+1+m
);m
=unique(b
+1,b
+1+m
)-b
-1;for(int i
=1;i
<=n
;i
++) a
[i
]=lower_bound(b
+1,b
+1+m
,a
[i
])-b
;for(int i
=1;i
<=n
;i
++)g
[a
[i
]].push_back(s
[i
]);for(int i
=1;i
<=m
;i
++)if(!check(g
[i
])){printf("Case #%d: -1\n",ca
);return;}ans
=0;cnt
[0]++;dfs(0);printf("Case #%d: %d\n",ca
,ans
);
}
int main()
{IO
;int T
=1;cin
>>T
;for(int ca
=1;ca
<=T
;ca
++){init();work(ca
);}return 0;
}
总结
以上是生活随笔为你收集整理的C. Code a Trie（Trie+dfs+贪心）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
