http://acm.hdu.edu.cn/showproblem.php?pid=1298
//1254514 2009-04-10 15:46:40 Accepted 1298 0MS 600K 2448 B C++ no way
#include<iostream>
#include<string>
using namespace std;
int i,maxs;
char tel[103];
char seStr[28];
char putss[28];
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) char key[10][5] = { {""}, {""}, {"abc1"}, {"def1"},
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {"ghi1"}, {"jkl1"}, {"mno1"},
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {"pqrs"}, {"tuv1"}, {"wxyz"}};
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct dictree
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
struct dictree *child[26];
int num;
dictree()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(i=0;i<26;i++)
child[i] = NULL;
num = 0;
}
~dictree()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
for(i=0;i<26;i++)
if(child[i] != NULL)
delete child[i];
}
}*dicTree;
dictree *root;
int find(char ch[])//查找单词出现的频率
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
dictree *p = root;
int k=0,mins = 1000000;
while(1)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(ch[k]=='\0' || p->child[ch[k]-'a']==NULL)
break;
p = p->child[ch[k]-'a'];
if(mins > p->num)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
mins = p->num;
if(mins <= maxs)
return -1;
}
k++;
}
if(ch[k] != '\0')
return -1;
return mins;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void dfs(int p,int t,int k)//深搜,t-界限,p-串中位置
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int j;
if(p>t)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
seStr[k]='\0';
int m = find(seStr);
if(m > maxs)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
strcpy(putss,seStr);
maxs = m;
}
return ;
}
for(j=0;j<4;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(key[tel[p]-'0'][j] != '1')
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
seStr[k] = key[tel[p]-'0'][j];
seStr[k+1]='\0';
if(find(seStr) <= maxs) //该剪枝非常重要
continue;
dfs(p+1,t,k+1);
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void insert(char *s,int r) //构建字典树
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
struct dictree *now = root;
while(*s)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(now->child[*s-'a'] == NULL)
now->child[*s-'a'] = new dictree;
now = now->child[*s-'a'];
now->num += r;
s++;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
void Delete(dicTree &pt)
{
if(pt)
{
for(i=0;i<26;i++)
Delete(pt->child[i]);
}
free(pt);
pt = NULL;
}
*/
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int j,n,r,t,cas=1;
char tmp[103];
cin>>t;
while(t--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
cin>>n; //单词的个数
root = new dictree;
while(n--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%s%d",tmp,&r);
insert(tmp,r);
}
cin>>n; //电话串的个数
cout<<"Scenario #"<<cas++<<":"<<endl;
while(n--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%s",tel);
int len = strlen(tel);
for(j=0;j<len;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
if(tel[j] == '1')//结束符
break;
if(j>25)//大于26个就没必要做了,肯定是没这个串
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf("MANUALLY\n");
continue;
}
maxs = -1;
dfs(0,j,0);
if(maxs == -1)
printf("MANUALLY\n");
else
printf("%s\n",putss);
}
printf("\n");
}
printf("\n");
//Delete(root);
}
return 0;
}
|