題目鏈接：點擊查看

題目大意：給出n個電話號碼，每個電話號碼都由9位數字組成，我們需要輸出每個電話號碼的最小關鍵詞，最小關鍵詞是指當輸入這個關鍵詞后，只能與當前的電話號碼的其中一段匹配，而不能和其他電話號碼的子字符串匹配

題目分析：這個題可以直接暴力做，但我一開始沒敢。。去網上搜了一下題解發現可以暴力于是才敢的，其實也沒什么大不了，自己計算一下，一個九位數的電話號碼的連續子串一共就只有9+8+7+6+5+4+3+2+1=45種，其長度之和也是等于45，所以一開始我們先用n*45的時間將n個電話號碼都存到字典樹中，然后依次枚舉每個電話號碼，操作的具體過程如下：

從字典樹中將其45個子字符串刪掉

從長度由小至大枚舉45個子字符串，若有滿足當前子字符串在字典樹中沒出現過，返回退出

將45個子字符串重新添加到字典樹中

按照這個過程暴力枚舉即可，這里需要提一下關于字典樹的數組大小，因為是個二維數組，我們可以描述為trie[節點數][字符數]，可以更進一步的描述為trie[字符串數*字符串長度][字符數]，這樣一來這個題目一共有n個字符串，每個字符串可以分成的子字符串的長度之和是45，所以開7e4*45*26就夠了，再大的話評測機不給過

還有就是一開始在糾結該如何記錄每個子串，用了一個布爾變量來記錄，結果發現每次刪除都會將其他電話號碼中的相同子串刪除掉，有點自閉，后來才想到，用一個sum數組記錄每個節點出現的次數即可，也就是儲存了每個子字符串出現的次數，每次刪除讓該子字符串對應的節點減一即可，恢復的話就是加一

然后這個題目因為都有減一和加一了，而且還是字符串，我們不難想到可以用映射來做這個題，給出的還是一個九位數的數字，我們可以選擇用map<int,int>來映射，也可以為了操作方便，用map<string,int>來映射，然后這是一個cf的題目，支持c++11，可以果斷上cin加速外掛和無序map來完成上述操作

最后總結一下吧，大概就是字典樹在這個題目中的貢獻有點像是用空間換時間，字典樹跑這個題用了400多ms，無序map亂搞的用了2000多ms，然后用了cin加速外掛的話，切記不能再用printf和scanf了，會莫名其妙的RE，TLE和WA

代碼：

字典樹：405ms，137.5MB

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=7e4+100;int trie[N*45][10];int sum[N*45];int cnt=0;string s[N];void insert(string s) {int pos=0;for(int i=0;i<s.size();i++){int to=s[i]-'0';if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];}sum[pos]++; }void del(string s) {int pos=0;for(int i=0;i<s.size();i++)pos=trie[pos][s[i]-'0'];sum[pos]--; }bool search(string s) {int pos=0;for(int i=0;i<s.size();i++)pos=trie[pos][s[i]-'0'];return !sum[pos]; }string solve(int pos) {for(int len=1;len<=9;len++)for(int i=0;i+len<=9;i++)del(s[pos].substr(i,len));for(int len=1;len<=9;len++)for(int i=0;i+len<=9;i++)if(search(s[pos].substr(i,len))){for(int len=1;len<=9;len++)for(int i=0;i+len<=9;i++)insert(s[pos].substr(i,len));return s[pos].substr(i,len);} }int main() { // freopen("input.txt","r",stdin);ios::sync_with_stdio(false);int n;cin>>n;for(int i=1;i<=n;i++){cin>>s[i];for(int len=1;len<=9;len++)for(int j=0;j+len<=9;j++)insert(s[i].substr(j,len));}for(int i=1;i<=n;i++)cout<<solve(i)<<endl;return 0; }

unordere_map：2666ms，42.3MB

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=7e4+100;string s[N];unordered_map<string,int>mp;string solve(int pos) {for(int len=1;len<=9;len++)for(int i=0;i+len<=9;i++)mp[s[pos].substr(i,len)]--;for(int len=1;len<=9;len++)for(int i=0;i+len<=9;i++)if(!mp[s[pos].substr(i,len)]){for(int len=1;len<=9;len++)for(int i=0;i+len<=9;i++)mp[s[pos].substr(i,len)]++;return s[pos].substr(i,len);} }int main() { // freopen("input.txt","r",stdin);ios::sync_with_stdio(false);int n;cin>>n;for(int i=1;i<=n;i++){cin>>s[i];for(int len=1;len<=9;len++)for(int j=0;j+len<=9;j++)mp[s[i].substr(j,len)]++;}for(int i=1;i<=n;i++)cout<<solve(i)<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 858D Polycarp's phone book(字典树/map)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。