poj2630Phone List (정적 트 라이 트 리)
이 문 제 는 항 저 우 전기 1671 과 마찬가지 로 - > 자세 한 내용 은 여 기 를 찌 르 세 요 < -
그래서 1671 의 코드 로 한 통 을 제출 했 는데 결국 TLE 가 되 었 습 니 다.과감하게 정적 트 리 로 쓰 면 효율 적 인 죽순 이 올 라 갑 니 다. TLE 에서 125 ms 까지 바로 이렇게 빠 릅 니 다!
이 코드 는 항 저 우 전기 에 다시 제출 되 었 고 효율 도 많이 높 았 다.400 + ms 에서 93ms 까지 역시 정적 데이터 구조 효율 이 높다.이 문 제 는 1671 보다 조금 더 개선 되 었 다. 바로 정렬 을 없 애고 각 노드 에 변수 tag 를 추가 하여 특정한 경로 가 존재 한 다 는 것 을 나타 낸다. end 는 한 단어의 끝 을 표시 한다. 그러면 우 리 는 정렬 하지 않 아 도 두 단어 가 같은 접두사 가 있 는 지 판단 할 수 있다.무 비분 2 가지 상황:
1: 어떤 단어 가 끝 날 때 이 노드 의 tag 가 1 인 것 을 발견 하면 앞 에 삽 입 된 어떤 단어 가 이미 이 길 을 걸 었 음 을 나타 낸다. 즉, 이 단 어 는 이 단어의 접두사 이 고 부정 적 이다.
2: 어떤 단어 가 삽 입 된 경로 에서 특정한 노드 가 다른 단어의 끝 이라는 것 을 발견 하면 이 두 단 어 는 공 통 된 접두사 가 있 고 부정 적 이다.
쓸데없는 말 은 그만 하고 코드 를 올 려 라.
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int next[10];
int end,tag;
}lcm[1<<16];
int pos,n;
int flag;
char s[11];
void init(int i)
{
memset(lcm[i].next,0,sizeof(lcm[i].next));
lcm[i].end = lcm[i].tag = 0;
}
void build(int t,int id)
{
lcm[t].tag = 1;
if(lcm[t].end == 1)
flag = 1;
if(flag)
return;
if(lcm[t].next[s[id] - '0'] == 0)
{
lcm[t].next[s[id] - '0'] = pos;
init(pos);
pos ++;
}
if(s[id + 1] == '\0')
{
if(lcm[lcm[t].next[s[id] - '0']].tag == 1)
flag = 1;
lcm[lcm[t].next[s[id] - '0']].end = 1;
return;
}
else
build(lcm[t].next[s[id] - '0'],id + 1);
}
int main()
{
int i,t;
scanf("%d",&t);
while(t --)
{
scanf("%d",&n);
pos = 1;
init(0);
flag = 0;
//memset(lcm,0,sizeof(lcm));
for(i = 0;i < n;i ++)
{
scanf("%s",s);
s[strlen(s)] = '\0';
build(0,0);
}
if(flag)
printf("NO
");
else
printf("YES
");
}
return 0;
}
//2780K 125MS
/*
10
2
123
12
2
1
12
2
12
1
3
1
12
123
3
12
13
14
3
12
13
123
3
911
97625999
91125426
5
113
12340
123440
12345
98346
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
