当前位置:编程学习 > C/C++ >>

poj - 3630 - Phone List

题意:给出n个电话号码(仅由数字0-9组成),问是否存在一个号码是另一个号码的前缀(1 ≤ 测试组数t ≤ 40,1 ≤ n ≤ 10000)。
 
题目链接:http://poj.org/problem?id=3630
 
——>>做这题太无语啦。。。明明就只是一棵Trip,可直到比赛结束都是TLE,究其原因,太什么啦。。。指针写Trip。。。
 
此题应用静态数组写Trip。。。
 
#include <cstdio>  
#include <cstring>  
#include <queue>  
  
using namespace std;  
  
const int maxw = 10 + 5;  
const int maxc = 100000 + 10;  
char p[maxw];  
bool ok, isp[maxc];  
int ch[maxc][10];  
  
struct Trip{  
    int sz;  
  
    Trip(){  
        sz = 1;  
        memset(isp, 0, sizeof(isp));  
        memset(ch, 0, sizeof(ch));  
    }  
  
    int idx(char c){  
        return c - '0';  
    }  
  
    void insert(char *s){  
        int len = strlen(s), i;  
        int u = 0;  
        for(i = 0; i < len; i++){  
            int c = idx(s[i]);  
            if(!ch[u][c]) ch[u][c] = sz++;  
            else{  
                if(i == len-1){  
                    ok = 0;      //目前电话是另外电话的前缀  
                    break;  
                }  
                if(isp[ch[u][c]]){  
                    ok = 0;     //另外电话是目前电话的前缀  
                    break;  
                }  
            }  
            u = ch[u][c];  
        }  
        isp[u] = 1;  
    }  
  
    void solve(){  
        if(ok) puts("YES");  
        else puts("NO");  
    }  
};  
  
int main()  
{  
    int t, n;  
    scanf("%d", &t);  
    while(t--){  
        ok = 1;  
        scanf("%d", &n);  
        Trip trip;  
        for(int i = 0; i < n; i++){  
            scanf("%s", p);  
            if(ok) trip.insert(p);  
        }  
        trip.solve();  
    }  
    return 0;  
}  

 


补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,