hdu 1298 T9

点击打开链接hdu 1298

题意：题目说的是在那遥远的星球有一款叫诺基亚的手机，键盘采用题目的图的样式。给定n个单词的出现的概率，规定是相加的比如hell出现为4，hello概率为3则hell的概率为7。现在给定m次输入的格式，根据概率问每一次输入能够得到的字符串是什么

思路：我们把n个单词建立成一棵字典树，然后我们对每一次的输入进行搜索，因为一个数字对应有好几种的可能值，然后把概率最大的字符串保存为ans即可
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1010;
const int N = 110;
const int M = 26;

struct Node{
    int mark;
    Node* child[M];
};
Node node[MAXN*N];
Node* root;

int pos , maxVal;
char ans[N];
int map[] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,9,9,9,9};

Node* newNode(){
    node[pos].mark = 0;
    for(int i = 0 ; i < M ; i++)
        node[pos].child[i] = NULL;
    return &node[pos++];
}

void insert(char *str , int p){
    Node* s = root;
    int len = strlen(str);
    for(int i = 0 ; i < len ; i++){
        int num = str[i]-'a';
        if(s->child[num] == NULL)
            s->child[num] = newNode();
        s = s->child[num]; 
        s->mark += p;
    }
}

void search(Node* s , char* str , char *tmp , int pos , int len){
    if(s == NULL)
        return;
    if(pos == len){
        if(s->mark > maxVal){
            maxVal = s->mark;
            memcpy(ans , tmp , sizeof(ans));
        }
        else if(s->mark == maxVal){
            if(strcmp(ans , tmp) > 0)
               memcpy(ans , tmp , sizeof(ans));
        }
        return; 
    }
    int num = str[pos]-'0';
    for(int i = 0 ; i < M ; i++){
        if(map[i] == num){
            tmp[pos] = i+'a';
            search(s->child[i],str,tmp,pos+1,len);
            tmp[pos] = '\0';
        }
    }
}

void solve(){
    int n;
    char str[N];
    char tmp[N];
    char tmpAns[N];
    scanf("%d" , &n);
    while(n--){
        scanf("%s" , str);
        int len = strlen(str)-1;
        for(int i = 0 ; i < len ; i++){
            memcpy(ans , "MANUALLY" , sizeof(ans));            
            memcpy(tmp , str , sizeof(tmp));
            tmp[i+1] = '\0';
            maxVal = 0;
            memset(tmpAns , '\0' , sizeof(tmpAns));
            search(root , tmp , tmpAns , 0 , i+1);
            printf("%s\n" , ans);
        }
        puts("");
    }
}

int main(){
    int cas , m , p;
    int Case = 1;
    char str[N];
    scanf("%d" , &cas);
    while(cas--){
        printf("Scenario #%d:\n" , Case++);
        pos = 0;
        root = newNode();
        scanf("%d" , &m);
        for(int i = 1 ; i <= m ; i++){
            scanf("%s %d" , str , &p);
            insert(str , p);
        }
        solve();
        puts("");
    }
    return 0;
}