Phone List 字典樹 OR STL
Phone List
Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 140 Solved: 35
Description
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
- Emergency 911
- Alice 97 625 999
- Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.
Input
The first line of input gives a single integer, 1<=t<=40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1<=n<=10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
Output
For each test case, output “YES” if the list is consistent, or “NO” otherwise.
Sample Input
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
Sample Output
NO YES
題意：查詢n個字符串，是否存在一個字符串是其他字符串的前綴。
秒想到字典樹，擼模版AC了，然后和隊友交流，學長說我寫的太復雜了，直接用set寫就行了。我后面試這寫了一下，但是一直超時，各種優化實在出不來，問了下學長，了解了新操作，漲知識了了。
第一個是set寫的，下面這個是字典樹寫的，set這個很卡時間，數據再強一點也許就卡了。
然后再HDU上提交，HDU把內存卡30M了，所以普通的字典樹內存可能不夠，就改進寫成了樹狀數組(靜態字典樹)，內存就被壓縮到了6.7M，也能過了；
字典樹法：
#include "cstdio"
#include "cstring"
#include "iostream"
#include "algorithm"
#include "cmath"
using namespace std;
#define memset(x,y) memset(x,y,sizeof(x))
const int MX = 1e6 + 5;
struct Trie{
int v;
Trie *next[11];
}root;
void Build(char *s){
int len = strlen(s);
Trie *p=&root,*q;
for(int i=0;i<len;i++){
int num=s[i]-'0';
if(p->next[num]==NULL){
q=(Trie *)malloc(sizeof (root));
q->v=1;
for(int j=0;j<11;j++){
q->next[j]=NULL;
}
p->next[num]=q;
p=p->next[num];
}else {
p=p->next[num];
p->v++;
}
}
}
int Query(char *s){
int len = strlen(s);
Trie *p=&root;
for(int i=0;i<len;i++){
int num=s[i]-'0';
if(p->next[num]==NULL){
return 0;
}
else{
p=p->next[num];
}
}
int v=p->v;
return v;
}
char s[10005][20];
int n,T;
int main(){
cin>>T;
while(T--){
memset(s,0);
for(int i=0; i<11; i++)root.next[i]=NULL;
cin>>n;
int ans=0;
for(int i=0;i<n;i++){
cin>>s[i];
Build(s[i]);
}
for(int i=0;i<n;i++){
ans+=Query(s[i])-1;
}
if(ans>0)puts("NO");
else puts("YES");
}
return 0;
}
/**********************************************************************
Problem: 1886
User: HDmaxfun
Language: C++
Result: AC
Time:304 ms
Memory:114092 kb
**********************************************************************/
樹狀數組：
#include "cstdio"
#include "cstring"
#include "string"
#include "iostream"
#include "algorithm"
using namespace std;
#define memset(x,y) memset(x,y,sizeof(x))
struct Trie {
int v;
int next[11];
void init() {
memset(next,-1);
v=1;
}
} dir[100005];
int tot;
void Build(char s[]) {
int len = strlen(s);
int now=0;
for(int i=0; i<len; i++) {
int num=s[i]-'0';
if(dir[now].next[num]==-1) {
tot++;
dir[tot].init();
dir[now].next[num]=tot;
now=dir[now].next[num];
} else {
now=dir[now].next[num];
dir[now].v++;
}
}
}
int Query(char s[]) {
int len = strlen(s);
int now=0;
for(int i=0; i<len; i++) {
int num=s[i]-'0';
//cout <<num;
if(dir[now].next[num]==-1) return 0;
else now=dir[now].next[num];
}
return dir[now].v;
}
char s[10005][20];
int n,T;
int main() {
cin>>T;
while(T--) {
memset(s,0);
memset(dir,0);
tot=0;
dir[0].init();
cin>>n;
int ans=0;
for(int i=0; i<n; i++) {
cin>>s[i];
Build(s[i]);
}
for(int i=0; i<n; i++) {
ans+=Query(s[i])-1;
// puts("");
//cout <<s[i]<<" "<<ans<<endl;
}
if(ans>0)puts("NO");
else puts("YES");
}
return 0;
}
set：
#include "cstdio"
#include "string"
#include "cstring"
#include "iostream"
#include "algorithm"
#include "cmath"
#include "set"
using namespace std;
#define memset(x,y) memset(x,y,sizeof(x))
const int MX = 1e4 + 5;
string a[MX];
set <string> st;
int main() {
int T,n;
char s[15];
cin>>T;
while(T--) {
scanf("%d",&n);
st.clear();
int ans=true;
for(int i=0; i<n; i++)scanf("%s",s),a[i]=string(s);
sort(a,a+n);
for(int i=n-1; i>=0; i--) {
if(st.find(a[i])!=st.end()){
ans=false;
break;
}
string tem="";
int len=a[i].length();
for(int j=0;j<len;j++){
tem+=a[i][j]; //string 居然可以直接添加字符，漲知識了。網上查了一下，string是一種類對象，可以直接用 +"xxx"將xxx直接接在前一個對象尾部。
st.insert(tem);
}
}
puts(ans?"YES":"NO");
}
return 0;
}
//我一開始一直在一個個字符的添加成串，再轉到set里面，這種方法卡時間又卡這么厲害，之前沒過也是必然了。。
/**********************************************************************
Problem: 1886
User: HDmaxfun
Language: C++
Result: AC
Time:972 ms
Memory:7460 kb
**********************************************************************/
浙公網安備 33010602011771號