hdu 1298 T9

字典树+DFS。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std; struct shu{ int value, nn[]; }node[];
int n, q, i, ii, v, zz, tott, anss, tt, ttt;
const int INF = 0x7FFFFFFF;
char s[], sc[], vc[], ljb[][]; void ljbb()
{
ljb[][] = ; ljb[][] = 'a'; ljb[][] = 'b'; ljb[][] = 'c';
ljb[][] = ; ljb[][] = 'd'; ljb[][] = 'e'; ljb[][] = 'f';
ljb[][] = ; ljb[][] = 'g'; ljb[][] = 'h'; ljb[][] = 'i';
ljb[][] = ; ljb[][] = 'j'; ljb[][] = 'k'; ljb[][] = 'l';
ljb[][] = ; ljb[][] = 'm'; ljb[][] = 'n'; ljb[][] = 'o';
ljb[][] = ; ljb[][] = 'p'; ljb[][] = 'q'; ljb[][] = 'r'; ljb[][] = 's';
ljb[][] = ; ljb[][] = 't'; ljb[][] = 'u'; ljb[][] = 'v';
ljb[][] = ; ljb[][] = 'w'; ljb[][] = 'x'; ljb[][] = 'y'; ljb[][] = 'z';
} void dfs(int ff, int zzz, int gl)
{
int i;
if (ff == ttt)
{
if (node[zzz].value > anss)
{
anss = node[zzz].value;
sc[gl] = '\0';
strcpy(vc, sc);
}
return;
}
if (s[ff] == '') dfs(ff + , zzz, gl);
for (i = ; i <= ljb[s[ff] - ''][]; i++)
{
if (node[zzz].nn[ljb[s[ff] - ''][i] - 'a'] != -)
{
sc[gl] = ljb[s[ff] - ''][i];
dfs(ff + , node[zzz].nn[ljb[s[ff] - ''][i] - 'a'], gl + );
}
}
} int main()
{
ljbb();
int sb, bs;
scanf("%d", &sb);
for (bs = ; bs <= sb; bs++)
{ scanf("%d", &n);
for (i = ; i <= ; i++)
{
node[i].value = ;
memset(node[i].nn, -, sizeof(node[i].nn));
}
tott = ;
for (ii = ; ii < n; ii++)
{
scanf("%s%d", s, &v);
zz = ;
for (i = ; s[i]; i++)
{
if (node[zz].nn[s[i] - 'a'] == -)
{
node[zz].nn[s[i] - 'a'] = tott;
tott++;
}
zz = node[zz].nn[s[i] - 'a'];
node[zz].value += v;
}
}
scanf("%d", &q);
printf("Scenario #%d:\n", bs);
for (ii = ; ii < q; ii++)
{
scanf("%s", s);
tt = strlen(s);
for (i = ; i < tt; i++)
{
anss = -INF;
ttt = i;
dfs(, , );
if (anss == -INF) printf("MANUALLY\n");
else printf("%s\n", vc);
}
printf("\n");
}
printf("\n");
}
return ;
}
上一篇:javascript中的promise和deferred:实践(二)


下一篇:pgsqls修改表字段长度