Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 674????Accepted Submission(s): 271
?
?
Input The first line contains the number of scenarios.?
Output The output for each scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1.?
Sample Input2 5 hell 3 hello 4 idea 8 next 8 super 3 2 435561 43321 7 another 5 contest 6 follow 3 give 13 integer 6 new 14 program 4 5 77647261 6391 4681 26684371 77771
?
Sample OutputScenario #1: i id hel hell hello i id ide idea Scenario #2: p pr pro prog progr progra program n ne new g in int c co con cont anoth anothe another p pr MANUALLY MANUALLY? ????????????题目大意:先给出你几个单词的按键频数,然后给出你输入的数字,按这些数字的输入来输出最高频数的单词,没有就输出MANUALLY。
???????????这题是一道很好的字典树,一个模拟手机输入法的算法,要用到深搜来解决输出哪个频数最多的单词。第一次写,写了很长时间,现在看回来,发现不过如此,链表不是很熟悉,要多写多练习才行啊!
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1298
代码:
?#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
using namespace std;
char map[10][5];
char res[105], str[105];
int MAX;
void set() //定义map[][]
{
strcpy(map[0], "");
strcpy(map[1], "");
strcpy(map[2], "abc");
strcpy(map[3], "def");
strcpy(map[4], "ghi");
strcpy(map[5], "jkl");
strcpy(map[6], "mno");
strcpy(map[7], "pqrs");
strcpy(map[8], "tuv");
strcpy(map[9], "wxyz");
}
struct node //结点结构
{
int val; //频率
char ch[105]; //字符
node *next[26]; //链表
};
node *root, memory[100005];
int cnt;
node* create()
{
node *p = &memory[cnt++];
p->val = 0;
int i;
for(i = 0; i < 26; i++)
{
p->next[i] = NULL;
}
return p;
}
void insert(char *s, int val)
{
node *p = root;
char str[105];
int i, k;
for(i = 0; s[i]; i++)
{
k = s[i] - 'a';
if(p->next[k] == NULL)
{
p->next[k] = create();
}
p = p->next[k];
p->val += val; //结点频率相加
str[i] = s[i];
str[i+1] = 0;
strcpy(p->ch, str); //结点保存该点的字符串
}
}
void dfs(node *p, int cur, int op) //深搜字典树(结点,当前位置,目标)
{
if(cur == op) //当前位置 == 目标位置
{
if(p->val > MAX) //找频率最大的那个字符串
{
strcpy(res, p->ch);
MAX = p->val;
}
return;
}
int i, k, l, len;
k = str[cur+1] - '0'; //char数字->int数字
len = strlen(map[k]); //map[k]为k键包含的字符
for(i = 0; i < len; i++)
{
l = map[k][i] - 'a'; //将字符->整型
if(p->next[l] == NULL) continue; //若为空,continue
else dfs(p->next[l], cur+1, op); //否则,继续深搜
}
}
int main()
{
int i, t, n, m, val, len, zz = 1;
char sh[105];
set();
scanf("%d", &t);
while(t--)
{
memset(memory, NULL, sizeof(memory));
cnt = 0;
root = create();
scanf("%d", &n);
for(i = 0; i < n; i++)
{
scanf("%s %d", sh, &val);
insert(sh, val); //将字符串插入字典树中
}
printf("Scenario #%d:\n", zz++);
scanf("%d", &m);
while(m--)
{
scanf("%s", str);
len = strlen(str);
for(i = 0; str[i] != '1'; i++)
{
MAX = -1;
dfs(root, -1, i);
if(MAX != -1) printf("%s\n", res);
else printf("MANUALLY\n");
}
if(m != 0) printf("\n");
}
printf("\n\n");
}
return 0;
}
?
?
????????