poj 1451.txt

poj 1451的代码和方法说明,个人原创

#include<iostream>
#include<vector>
using namespace std;
int map[10][5]={{0},{0},{3,0,1,2,0},{3,3,4,5,0},{3,6,7,8,0},{3,9,10,11,0},{3,12,13,14,0},{4,15,16,17,18},
{3,19,20,21},{4,22,23,24,25}};//把数字键和它们对应的字符的as2码-'a'的值建立映射

class ty
{
public:
ty *next [26];
ty *father;
int value;
char t;
ty()
{
   memset(next,0,sizeof(next));
   father=0;
   value=0;
}
};//字典树数据结构
ty *root;
void output(ty *ee)
{
if(ee==root)
   return;
output(ee->father);
printf("%c",ee->t+'a');
}

void add(ty *ee,int t)//以ee为尾节点,一直回溯到根,每点的值都加上t
{
   if(ee==root)
   return;
add(ee->father,t);
ee->value+=t;
}

vector<ty *> ww;
char ch[150],pp;
int n,m,cas,kk,uu,rr;
int main()
{
cin>>cas;
int cas1=0;
while(cas--)
{cas1++;
root=new ty;
     
   cin>>n;
   int i,j,k;
   for(i=1;i<=n;i++)
   {
    scanf("%s",ch);
    cin>>k;
    j=0;
    ty *oo=root;
    while(ch[j])
    {
     if(oo->next[ch[j]-'a']==0)//如果对应的字符没有分配地址,那么新分配一个
     {   
      oo->next[ch[j]-'a']=new ty;
      oo->next[ch[j]-'a']->father=oo;
      oo->next[ch[j]-'a']->t= ch[j]-'a';
     // add(oo->next[ch[j]-'a'],k);
     
     }
   // if(k>oo->value)
    // {
    //   oo->value=k;
    // }
    
     oo=oo->next[ch[j++]-'a'];
    }
    add(oo,k);
   }
   cin>>m;
printf("Scenario #%d:\n",cas1);
   for(i=1;i<=m;i++)
   { getchar();
    ww.clear();
   ww.push_back(root);
   int min=-10000000;
   ty *ee=root;

    while((pp=getchar())!='1')
    { 
     if(ee==0)//如果前一次都没有找到,那么这次也不用找了
     {
      cout<<"MANUALLY\n";
      continue;
     }
     ee=0;

    
     uu=pp-'0';
     kk=map[uu][0];
     min=-10000000;
     int cs=ww.size();
     for(j=0;j<cs;j++)
     {
      int ff=0;
      for(k=1;k<=kk;k++)
      {
       if(ww[j]->next[map[uu][k]])
       {
        ff=1;
        ww.push_back(ww[j]->next[map[uu][k]]);
        if(ww[j]->next[map[uu][k]]->value>min)//如果有更大的值,那么更新ee
        {
                               min=ww[j]->next[map[uu][k]]->value;
          ee=ww[j]->next[map[uu][k]];
        }

       }
      }
     // if(ff==0)
     // {
       ww.erase(ww.begin()+j);//当一点全部搜过了,就把它从队列中删除
       j--;
       cs--;
     // }
     }
   
                  if(ee==0)//如果ee指向0地址单元,说明没有在字典树中找到匹配
     {
      cout<<"MANUALLY\n";
      continue;
     }
      else
      {   output(ee);
      cout<<endl;
      }

    }
    


cout<<endl;


                  
    }//for
   cout<<endl;
   }//while
return 0;
}