Cellphone Typing
64-bit integer IO format: %lld Java class name: Main
However, this is not fast enough. The team is going to put together a dictionary of the common words that a user may type. The goal is to reduce the average number of keystrokes needed to type words that are in the dictionary. During the typing of a word, whenever the following letter is uniquely determined, the cellphone system will input it automatically, without the need for a keystroke. To be more precise, the behavior of the cellphone system will be determined by the following rules:
- The system never guesses the first letter of a word, so the first letter always has to be input manually by pressing the corresponding key.
- If a non-empty succession of letters c1c2...cn has been input, and there is a letter c such that every word in the dictionary which starts with c1c2...cn also starts with c1c2...cnc, then the system inputs c automatically, without the need of a keystroke. Otherwise, the system waits for the user.
For instance, if the dictionary is composed of the words `hello', `hell', `heaven' and `goodbye', and the user presses `h', the system will input `e' automatically, because every word which starts with `h' also starts with `he'. However, since there are words that start with `hel' and with `hea', the system now needs to wait for the user. If the user then presses `l', obtaining the partial word `hel', the system will input a second `l' automatically. When it has `hell' as input, the system cannot guess, because it is possible that the word is over, or it is also possible that the user may want to press `o' to get `hello'. In this fashion, to type the word `hello' the user needs three keystrokes, `hell' requires two, and `heaven' also requires two, because when the current input is `hea' the system can automatically input the remainder of the word by repeatedly applying the second rule. Similarly, the word `goodbye' needs just one keystroke, because after pressing the initial `g' the system will automatically fill in the entire word. In this example, the average number of keystrokes needed to type a word in the dictionary is then (3 + 2 + 2 + 1)/4 = 2.00.
Your task is, given a dictionary, to calculate the average number of keystrokes needed to type a word in the dictionary with the new cellphone system.
Input
Each test case is described using several lines. The first line contains an integer N representing the number of words in the dictionary ( 1N105). Each of the next N lines contains a non-empty string of at most 80 lowercase letters from the English alphabet, representing a word in the dictionary. Within each test case all words are different, and the sum of the lengths of all words is at most 106.Output
For each test case output a line with a rational number representing the average number of keystrokes needed to type a word in the dictionary. The result must be output as a rational number with exactly two digits after the decimal point, rounded if necessary.Sample Input
4 hello hell heaven goodbye 3 hi he h 7 structure structures ride riders stress solstice ridiculous
Sample Output
2.00 1.67 2.71
吐槽:有一年没写过字典树了,看以前的代码竟然感到很陌生,更可笑的是指针都不知道怎么用了。真是学得不如忘得快,但是好好看看,就很快懂了。
题目大意:给你n个不重复的字符串,每次敲一个字母,有相同前缀的字母都会自动出来,类似手机输入法。问你打出所有字符串平均需要敲多少下。如第一组样例。
hello 只需要敲3次,一次是h,一次是l,一次是o。 hell只需要敲2次,一次是h,一次是l。heaven需要敲2次,一次是h,一次是a。goodbye需要敲1次,即g。所以全部敲完是8次,平均值是2.00。
解题思路:用字典树模拟过程。我们在每个结点记录重复度rep,该结点下面有多少个分叉cross,是否是字符串结尾flag。对于分叉大于1的结点,我们需要加上该结点的重复度,表示需要在该结点下面的那些不同的字符处敲键盘。如果该结点同时是串尾的话,则需要减1,因为对于当前这个串,不需要在下面多敲一次就已经得到了。对于分叉不大于1的结点,我们判断它是否是串尾,如果是串尾,那么我们只需要加上重复度-1即可。最后加上串的个数n,表示对于每个字串,都需要敲1次最开始的那个字母。
#include<bits/stdc++.h> using namespace std; struct NODE { int rep; int cross; bool flag; NODE *next[26]; }; typedef NODE Trie; NODE *newnode(){ Trie *tmp; tmp= new Trie; for(int i=0;i<26;i++) tmp->next[i]=NULL; tmp->flag=0; tmp->cross=0; tmp->rep=0; return tmp; } void Insert ( Trie *rt, char *s ) { int len = strlen ( s ); int idx; for ( int i = 0; i < len; i++ ) { idx = s[i] - 'a'; if(rt->next[idx] == NULL) { rt->next[idx] = newnode() ; rt->cross++; } rt=rt->next[idx]; rt->rep++; } rt->flag=1; } double dfs(Trie *rt){ double ret=0; for(int i=0;i<26;i++){ if(rt->next[i]!=NULL){ ret+=dfs(rt->next[i]); } } if(rt->cross>1){ ret+=rt->rep; if(rt->flag==1){ ret--; } }else if(rt->flag==1){ ret+=rt->rep-1; } delete rt; return ret; } int main() { int n; char str[100]; while ( scanf ( "%d", &n ) != EOF ) { Trie *root; root=newnode(); for ( int i = 0; i < n; i++ ) { scanf ( "%s", str ); Insert ( root, str ); } double ans=dfs(root); printf("%.2lf ",(n+ans)/n*1.0); } return 0; }