傳送門 - > \(POJ3630\)

題目描述

給定一個電話號碼列表，確定它是否一致，因為沒有號碼是另一個號碼的前綴。假設電話目錄列出了這些號碼：
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在這種情況下，不可能打電話給Bob，因為一旦您撥了Bob電話號碼的前三位數，中央就會將您的電話直接打到緊急線路。所以這個名單不一致。

輸入

第一行輸入給出一個整數，1≤t≤40，測試用例數。每個測試用例從n個電話號碼開始，在一個單獨的行上，1≤n≤10000。然后跟隨n行每條線上有一個唯一的電話號碼。電話號碼是一個最多十位數的序列。

輸出

對于每個測試用例，如果列表一致，輸出“是”，否則輸出“否”。

樣例輸入

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

樣例輸出

NO
YES

題解

trie樹裸題
在插入的時候標記一下當前單詞的結尾
在檢索的時候分兩種情況,設當前字符串長度為len,前len-1位如果有標記就代表有前綴,不合法
若第len位標記數量大于等于2,則代表有重復字符串,不合法

#include<cstdio> #include<cstring> #include<cmath> #define Min(a,b) (a)<(b)?(a):(b) #define Max(a,b) (a)>(b)?(a):(b) #define in(i) (i=read()) using namespace std; int read() {int ans=0,f=1; char i=getchar();while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}while(i>='0' && i<='9') {ans=(ans<<1)+(ans<<3)+i-'0'; i=getchar();}return ans*f; } int T,tot,flag; int trie[1000010][10],ed[1000010]; char s[10010][20]; void insert(char *str) {int len=strlen(str),p=0;for(int i=0;i<len;i++) {int c=str[i]-'0';if(!trie[p][c]) trie[p][c]=++tot;p=trie[p][c];} ed[p]++; } void find(char *str) {if(!flag) return;int len=strlen(str),p=0;for(int i=0;i<len;i++) {int c=str[i]-'0';if(ed[p]) {flag=0;return;}p=trie[p][c];}if(ed[p]>=2) flag=0; } int main() {in(T);while(T--) {int n; in(n);tot=0; flag=1;memset(ed,0,sizeof(ed));memset(trie,0,sizeof(trie));for(int i=1;i<=n;i++) {scanf("%s",s[i]);insert(s[i]);}for(int i=1;i<=n;i++) find(s[i]);puts(flag?"YES":"NO");} }

博主蒟蒻,隨意轉載.但必須附上原文鏈接

http://www.cnblogs.com/real-l/

轉載于:https://www.cnblogs.com/real-l/p/9472724.html

總結

以上是生活随笔為你收集整理的[POJ3630] Phone List的全部內容，希望文章能夠幫你解決所遇到的問題。

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