hdu1298 T9

一个tire树+dfs的题目

题目链接

题意简述

T9输入法就是把九键输入做一个化简,本来输入C的话需要点2三次,所以输入HELLO需要重复很多次,而现在输入435561就会根据权重自动匹配到HELLO,题目给定$n$个字符串和对应的权重当作字典,在给定$m$次询问每次询问一个输入序列求最有可能出现的字符,假如无法匹配上就输出MANUALLY

题解

这是一个tire+dfs的题,首先在插入每个字符串的时候对每个前缀的tire节点都加上权重,然后对于操作序列进行dfs,这道题整体不难,不过写起来还有不少细节需要注意,网上找到的题解基本都是数组,而且对于按键对应数组基本也是存一个字符数组,这里提供tire树数组写法和一种不一样的按键对应过于丑陋因为键盘的数字和字母顺序表是对应的而且除了最后三个都是每三个一连续所以我们只要对后三个特判一下计算方式就好

AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
const int maxn=100050;
int T,n,m,maxx;
int tire[maxn][30],cnt[maxn],num;
string s,temp;
char ans[maxn],t[maxn];
void insert(string s,int x)
{
	int p=0;
	for(int i=0;i<s.size();i++)
	{
		if(tire[p][s[i]-'a']) p=tire[p][s[i]-'a'];
		else
		{
			tire[p][s[i]-'a']=++num;
			p=num;
		}
		cnt[p]+=x;
	}
}
void dfs(int d,int ed,int sum,int p)
{
	if(d==ed)
	{
		if(sum>maxx)
		{
			maxx=sum;
			memset(ans,0,sizeof(ans));
			for(int i=0;i<ed;i++) ans[i]=t[i];
		}
		return ;
	}
	int tt=temp[d]-'0'-1,q;
	if(tt==6) tt=(tt-1)*3,q=4;
	else if(tt==7) tt=19,q=3;
	else if(tt==8) tt=22,q=4;
	else tt=(tt-1)*3,q=3;
	for(int i=tt;i<tt+q;i++)
	{
		if(tire[p][i])
		{
			t[d]='a'+i;
			dfs(d+1,ed,cnt[tire[p][i]],tire[p][i]);
			t[d]=0;
		}
		else continue;
	}
	return ;
}
int main()
{
	cin>>T;
	for(int tim=1;tim<=T;tim++)
	{
		cout<<"Scenario #"<<tim<<":"<<endl;
		memset(tire,0,sizeof(tire));
		memset(cnt,0,sizeof(cnt));num=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>s>>x;
			insert(s,x);
		}
		cin>>m;
		while(m--)
		{
			cin>>s;
			for(int i=0;s[i]!='1';i++)
			{
				memset(t,0,sizeof(t));maxx=0;
				memset(ans,0,sizeof(ans));
				temp=s.substr(0,i+1);
				dfs(0,i+1,0,0);
				if(!maxx) cout<<"MANUALLY"<<endl;
				else
				{
					for(int j=0;j<i+1;j++) cout<<ans[j];
					cout<<endl;
				}
			}
			if(m!=0) cout<<endl;
		}
		cout<<endl<<endl;
	}
	return 0;
}