Tag Archives: Trie

ZJU 2876 解题报告

Phone List

Time Limit: 5 Seconds Memory Limit: 32768 KB

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.


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.


For each test case, output "YES" if the list is consistent, or "NO" otherwise.

Read more »

ZJU 1109 解题报告

Language of FatMouse

Time Limit: 10 Seconds Memory Limit: 32768 KB

We all know that FatMouse doesn't speak English. But now he has to be prepared since our nation will join WTO soon. Thanks to Turing we have computers to help him.

Input Specification

Input consists of up to 100,005 dictionary entries, followed by a blank line, followed by a message of up to 100,005 words. Each dictionary entry is a line containing an English word, followed by a space and a FatMouse word. No FatMouse word appears more than once in the dictionary. The message is a sequence of words in the language of FatMouse, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.

Output Specification

Output is the message translated to English, one word per line. FatMouse words not in the dictionary should be translated as "eh".

Sample Input

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

Output for Sample Input



Read more »

HDU 1251 解题报告



Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)

Problem Description







Read more »

HDU 1247 解题报告


Hat’s Words

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Problem Description

A hat's word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat's words in a dictionary.


Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.

Only one case.


Your output should contain all the hat’s words, one per line, in alphabetical order.

Read more »