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++ ,