学步园

题目很简单，意思也很明显。不过感觉这个题过的很顺，代码也还算简单。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>

#define pb push_back

using namespace std;

vector<char> vec[12];
struct Node {
    string s;
    int p;
    Node() {}
    Node (string _s, int _p) : s(_s), p(_p) {}
};
vector<Node> dic;
map<string, int> mp, mpp;
map<string, int>::iterator it, itt;
map< string, vector<Node> > res, ress;
map< string, vector<Node> >::iterator it1;
int n, m;

void init()
{
    for(int i = 0; i <= 9; i++) vec[i].clear();
    vec[2].pb('A'), vec[2].pb('B'), vec[2].pb('C');
    vec[3].pb('D'), vec[3].pb('E'), vec[3].pb('F');
    vec[4].pb('G'), vec[4].pb('H'), vec[4].pb('I');
    vec[5].pb('J'), vec[5].pb('K'), vec[5].pb('L');
    vec[6].pb('M'), vec[6].pb('N'), vec[6].pb('O');
    vec[7].pb('P'), vec[7].pb('Q'), vec[7].pb('R'), vec[7].pb('S');
    vec[8].pb('T'), vec[8].pb('U'), vec[8].pb('V');
    vec[9].pb('W'), vec[9].pb('X'), vec[9].pb('Y'), vec[9].pb('Z');
    for(int i = 2; i <= 9; i++) {
        for(int j = 0; j < (int)vec[i].size(); j++)
            vec[i][j] += 32;
    }
}

string gao(int id, const string s)
{
    int t = s[id] - '0';
    mpp.clear();
    ress.clear();
    for(it = mp.begin(); it != mp.end(); it++) {
        string first = it->first;
        it1 = res.find(first);
        vector<Node> v = it1->second;
        for(int i = 0; i < (int)v.size(); i++) {
            for(int j = 0; j < (int)vec[t].size(); j++) {
                string tmp = first + vec[t][j];
                if((int)v[i].s.size() > id && v[i].s[id] == vec[t][j]) {
                    itt = mpp.find(tmp);
                    if(itt == mpp.end()) {
                        mpp[tmp] = v[i].p;
                        vector<Node> vv;
                        vv.clear();
                        vv.push_back(v[i]);
                        ress[tmp] = vv;
                    }
                    else {
                        int tt = itt->second;
                        mpp.erase(itt);
                        mpp[tmp] = v[i].p + tt;
                        it1 = ress.find(tmp);
                        vector<Node> vv = it1->second;
                        ress.erase(it1);
                        vv.push_back(v[i]);
                        ress[tmp] = vv;
                    }
                }
            }
        }
    }
    mp.clear();
    res.clear();
    for(it = mpp.begin(); it != mpp.end(); it++) mp[it->first] = it->second;
    for(it1 = ress.begin(); it1 != ress.end(); it1++) res[it1->first] = it1->second;
    int maxx = -1;
    string tmp = "MANUALLY";
    for(it = mp.begin(); it != mp.end(); it++) {
        if(it->second > maxx) {
            maxx = it->second;
            tmp = it->first;
        }
    }
    return tmp;
}

int main()
{
    int t;
    scanf("%d", &t);
    init();
    int cas = 1;
    while(t--) {
        dic.clear();
        printf("Scenario #%d:\n", cas++);
        scanf("%d", &n);
        string s;
        int p;
        for(int i = 0; i < n; i++) {
            cin >> s >> p;
            dic.push_back(Node(s, p));
        }
        scanf("%d", &m);
        for(int i = 0; i < m; i++) {
            cin >> s;
            int len = s.size();
            if(s[len - 1] == '1') len--;
            bool f = true;
            mp.clear();
            res.clear();
            for(int j = 0; j < len; j++) {
                string r = "MANUALLY";
                if(j == 0) {
                    mp[""] = 0;
                    res[""] = dic;
                }
                if(f) r = gao(j, s);
                if(r == "MANUALLY") f = false;
                cout << r << endl;
            } 
            puts("");
        }
        puts("");
    }
    return 0;
}