LiuTianyou @ 2022-07-22 21:02:26
有大佬熟悉这种解法吗
这是我今天第三次求pb_ds的trie了。还是没人提供。
求你们了……………………
（由于要回宿舍了，明天见
参考资料：C++的pb_ds库在OI中的应用.pdf
by C_liar @ 2022-07-23 20:45:43
不熟悉。
#include<iostream>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> tr;
tr Trie;
string s;
int main(){
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--){
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++) cin>>s;
for(int i=1;i<=q;i++){
cin>>s;
int ans=0;
auto x=Trie.prefix_search(s);
for(auto i=x.first;i!=x.second;i++) ans++;
cout<<ans<<endl;
}
}
return 0;
}
链接：https://blog.csdn.net/qq_43906740/article/details/96474307
（顺带膜一下同机房大佬，%%%）
by LiuTianyou @ 2022-07-25 11:43:17
@C_liar 我在没看到你这个贴的情况下显然也是写出了这样的代码。。。。
很不幸的是，这样的代码明显TLE了.
我的想法是，重写节点更新器，并且使用遍历trie树的方式来处理.
目前我有一篇文章：https://www.luogu.com.cn/blog/liutianyou/CPP-Killer
里面大致介绍了trie的相关资料，但是我还不会用这些方法解这道题，希望大佬可以支持下