#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <list>
#include <map>
using namespace std;
int key[]={0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,5,6,6,6,7,7,7,7};
struct node
{
    string word;
    int pri;
};
vector<node>bod[9];
list<node>buf;
list<node>::iterator itr,itr2;
map<string,int>best;
int main() 
{
    int i,m,n,j,k,l,t,now,let,o,p,maxpri;
    bool flag;
    string cmd,ccmd,maxstr;
    string out;
    node nd;
    cin>>t;
    for (o=1;o<=t;o++)
    {
        cout<<"Scenario #"<<o<<":"<<endl;
        cin>>n;
        for (i=0;i<8;i++) bod[i].clear();
        for (i=0;i<n;i++) 
        {
            cin>>nd.word>>nd.pri;
            bod[key[nd.word[0]-'a']].push_back(nd);
        }
        cin>>n;
        for (k=0;k<n;k++)
        {
            cin>>cmd;
            now=0;
            let=cmd[0]-'2';
            buf.clear();
            for (i=0;i<bod[let].size();i++) buf.push_back(bod[let][i]);
            for (i=0;i<cmd.length()-1;i++)
            {
                if (buf.size())
                {
                    best.clear();
                    itr=buf.begin();
                    maxpri=0;
                    while (itr!=buf.end())
                    {
                        itr2=itr;
                        itr++;
                        ccmd="";
                        if (key[(*itr2).word[i]-'a']!=cmd[i]-'2') buf.erase(itr2);
                        else
                        {
                            for (j=0;j<=i;j++)
                                ccmd+=(*itr2).word[j];
                                if (best.find(ccmd)==best.end()) best[ccmd]=(*itr2).pri;
                                else best[ccmd]+=(*itr2).pri;
                                if (best[ccmd]>maxpri)
                                {
                                    maxpri=best[ccmd];
                                    maxstr=ccmd;
                                }
                        }
                    }
                    if (buf.size()) cout<<maxstr<<endl; else cout<<"MANUALLY"<<endl;
                }else cout<<"MANUALLY"<<endl;
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

• 过了。。竟然没有考虑只有一个1的情况，，还有，NetBean竟然不提示访问数组超界或者除0的错误。。 (0) hysramp 2008-02-02 09:23:37
  • 这道题，厄，当年说要写结果硬是拖了好久都没把题读完过。。 (0) richardxx 2008-02-02 18:21:04
    • 阿哈你居然出现了。。题也不算太长。。看起来长得有点吓人 (0) hysramp 2008-02-04 12:05:35
      • 偶长期混迹POJ未曾间断....这题是不是用trie来搞的？ (0) richardxx 2008-02-04 15:15:05
        • Re:偶长期混迹POJ未曾间断....这题是不是用trie来搞的？ (38) hysramp 2008-02-05 12:32:54
        • 偶用了两个trie混过去的..... (0) DayDream 2008-02-05 20:25:19