Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

A research team is developing a new technology to save time when typing text messages in mobiledevices. They are working on a new model that has a complete keyboard, so users can type any singleletter by pressing the corresponding key. In this way, a user needs P keystrokes to type a word oflength P.

However, this is not fast enough. The team is going to put together a dictionary of the commonwords that a user may type. The goal is to reduce the average number of keystrokes needed to typewords that are in the dictionary. During the typing of a word, whenever the following letter is uniquelydetermined, the cellphone system will input it automatically, without the need for a keystroke. To bemore precise, the behavior of the cellphone system will be determined by the following rules:

1. The system never guesses the first letter of a word, so the first letter always has to be inputmanually by pressing the corresponding key.
2. If a non-empty succession of letters c₁c₂...c_n has been input, and there is a letter c such thatevery word in the dictionary which starts with c₁c₂...c_n also starts with c₁c₂...c_nc, then thesystem inputs c automatically, without the need of a keystroke. Otherwise, the system waits forthe 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 startswith `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 systemcannot guess, because it is possible that the word is over, or it is also possible that the user may wantto 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' thesystem 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' thesystem will automatically fill in the entire word. In this example, the average number of keystrokesneeded 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 aword 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 thenumber of words in the dictionary (1N10⁵). Each of the next N lines contains a non-emptystring 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 10⁶.

Output 

For each test case output a line with a rational number representing the average number of keystrokesneeded to type a word in the dictionary. The result must be output as a rational number with exactlytwo 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

---

建出一個 Trie，對每個到葉節點的路徑紀錄其分支度大於1的個數，加總即可。

#include <stdio.h>
#include <string.h>
struct Trie {
    bool n;
    int link[26], cnt, b;
} Node[1048576];
int TrieSize;
int insertTrie(const char *str) {
    static int i, idx;
    idx = 0;
    for(i = 0; str[i]; i++) {
        if(!Node[idx].link[str[i]-'a']) {
            TrieSize++;
            memset(&Node[TrieSize], 0, sizeof(Node[0]));
            Node[idx].link[str[i]-'a'] = TrieSize;
            Node[idx].b++;
        }
        Node[idx].cnt++;
        idx = Node[idx].link[str[i]-'a'];

    }
    Node[idx].n = true, Node[idx].b++;
    return 0;
}
int ans;
void dfs(int nd, int dep, int cc) {
    if(Node[nd].n == true) {
        ans += cc;
    }
    int i, plus;
    plus = Node[nd].b != 1;
    for(i = 0; i < 26; i++) {
        if(Node[nd].link[i]) {
            dfs(Node[nd].link[i], dep+1, cc+plus);
        }
    }
}
char str[100];
int main() {
    int n, on;
    while(scanf("%d ", &n) == 1) {
        on = n;
        TrieSize = 0;
        memset(&Node[0], 0, sizeof(Node[0]));
        while(n--) {
            gets(str);
            insertTrie(str);
        }
        ans = 0;
        for(int i = 0; i < 26; i++)
            if(Node[0].link[i])
                dfs(Node[0].link[i], 1, 1);
        printf("%.2lf\n", (double)ans/on);
    }
    return 0;
}