HDU 1298（字典树+dfs）

素颜马尾好姑娘i 2022-09-20 12:43 108阅读 0赞

题意:给一个T，表示输入数据的组数。给一个n，表示字典的大小。接下来有n行，每行有一个字符串和一个数字，数字表示为这个字符串的权值。接下来给一个m，表示手机按键的串号，结尾1表示当前输入结束，进行下一个字符。输出每一步按键应该出现的字符串。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    
    struct Trie
    {
        int count;
        Trie* next[26];
        Trie() : count(0)
        {
            memset(next, NULL, sizeof (next));
        }
    };
    
    int _max;
    const int phone[8][4] = { {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {9, 10, 11}, {12, 13, 14}, {15, 16, 17, 18}, {19, 20, 21}, {22, 23, 24, 25} }; 
    const int num[8] = { 3, 3, 3, 3, 3, 4, 3, 4 };  
    
    void insertTrie(Trie* root, char* s, int p)
    {
        Trie* t = root;
        int i = 0, n;
        while (s[i])
        {
            n = s[i++] - 'a';
            if (t->next[n] == NULL)
                t->next[n] = new Trie;
            t = t->next[n];
            t->count += p;
        }
    
    }
    
    void freeTrie(Trie* root)
    {
        if (root)
            for (int i = 0; i < 26; ++i)
                if (root->next[i])
                    freeTrie(root->next[i]);
        delete root;
    }
    
    void DFS(int cur, int len, Trie* p, char* s, char* find, char* ans)
    {
        if (cur == len)
        {
            if (p->count > _max)
            {
                _max = p->count;
                for (int i = 0; i < len; ++i)
                    find[i] = ans[i];
                find[len] = '\0';
            }
            return;
        }
        int n = s[cur] - '2';
        for (int i = 0; i < num[n]; ++i)
        {
            int r = phone[n][i];
            if (p->next[r] == NULL)
                continue;
            ans[cur] = 'a' + r;
            DFS(cur + 1, len, p->next[r], s, find, ans);
        }
    }
    
    int main()
    {
        char s[105], ans[105], find[105];
        int t, n, p, m;
        Trie* root;
        scanf("%d", &t);
        for (int _t = 1; _t <= t; ++_t)
        {
            printf("Scenario #%d:\n",_t);
            scanf("%d", &n);
            root = new Trie;
            while (n--)
            {
                scanf("%s %d", s, &p);
                insertTrie(root, s, p);
            }
            scanf("%d", &m);
            while (m--)
            {
                scanf("%s", s);
                for (int i = 1; s[i-1] != '1'; ++i)
                {
                    _max = 0;
                    DFS(0, i, root, s, find, ans);
                    if (_max > 0)
                        printf("%s\n", find);
                    else printf("MANUALLY\n");
                }
                printf("\n");
            }
            printf("\n");
            freeTrie(root);
        }
        return 0;
    }