USACO Name That Number：電話鍵盤映射字典查找

問題描述

標準電話鍵盤數字 2-9 對應字母（如 2:ABC, 3:DEF...）。給定字典文件 dict.txt（含 ~4600 單詞），輸入一串數字（≤12 位，對應 long long），輸出字典中所有按鍵映射匹配該數字的單詞，按字典順序；無則輸出 NONE。

解法：預處理字典建立數值映射

• 讀入字典每個單詞，按鍵盤映射計算其對應數值（如 BETTER → 238837），存入結構體數組 {word, value}。
• 查詢時讀入數字 N，遍歷字典數組，value == N 輸出單詞。
• 字典量小（4600），線性掃描極快，無需複雜索引。

鍵盤映射表

map mp = {
    {'A',2},{'B',2},{'C',2},
    {'D',3},{'E',3},{'F',3},
    {'G',4},{'H',4},{'I',4},
    {'J',5},{'K',5},{'L',5},
    {'M',6},{'N',6},{'O',6},
    {'P',7},{'R',7},{'S',7}, // Q,Z 無映射
    {'T',8},{'U',8},{'V',8},
    {'W',9},{'X',9},{'Y',9}
};

代碼框架

struct DictEntry { char word[20]; long long val; } dict[5000];
int dictSize=0;
void preprocess() {
    FILE* f = fopen("dict.txt","r");
    char w[20];
    while(fscanf(f,"%s",w)==1) {
        long long v=0;
        for(char* c=w; *c; c++) v = v*10 + mp[*c];
        strcpy(dict[dictSize].word, w);
        dict[dictSize].val = v;
        dictSize++;
    }
    fclose(f);
}
int main() {
    preprocess();
    long long N;
    while(scanf("%lld",&N)!=EOF) {
        bool found=false;
        for(int i=0;i