- 浏览: 199170 次
- 性别:
- 来自: 广州
文章分类
最新评论
T9
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 674 Accepted Submission(s): 271
This led manufacturers of mobile phones to try and find an easier way to enter text on a mobile phone. The solution they developed is called T9 text input. The "9" in the name means that you can enter almost arbitrary words with just nine keys and without pressing them more than once per character. The idea of the solution is that you simply start typing the keys without repetition, and the software uses a built-in dictionary to look for the "most probable" word matching the input. For example, to enter "hello" you simply press keys 4, 3, 5, 5, and 6 once. Of course, this could also be the input for the word "gdjjm", but since this is no sensible English word, it can safely be ignored. By ruling out all other "improbable" solutions and only taking proper English words into account, this method can speed up writing of short messages considerably. Of course, if the word is not in the dictionary (like a name) then it has to be typed in manually using key repetition again.
Figure 8: The Number-keys of a mobile phone.
More precisely, with every character typed, the phone will show the most probable combination of characters it has found up to that point. Let us assume that the phone knows about the words "idea" and "hello", with "idea" occurring more often. Pressing the keys 4, 3, 5, 5, and 6, one after the other, the phone offers you "i", "id", then switches to "hel", "hell", and finally shows "hello".
Write an implementation of the T9 text input which offers the most probable character combination after every keystroke. The probability of a character combination is defined to be the sum of the probabilities of all words in the dictionary that begin with this character combination. For example, if the dictionary contains three words "hell", "hello", and "hellfire", the probability of the character combination "hell" is the sum of the probabilities of these words. If some combinations have the same probability, your program is to select the first one in alphabetic order. The user should also be able to type the beginning of words. For example, if the word "hello" is in the dictionary, the user can also enter the word "he" by pressing the keys 4 and 3 even if this word is not listed in the dictionary.
Each scenario begins with a line containing the number w of distinct words in the dictionary (0<=w<=1000). These words are given in the next w lines. (They are not guaranteed in ascending alphabetic order, although it's a dictionary.) Every line starts with the word which is a sequence of lowercase letters from the alphabet without whitespace, followed by a space and an integer p, 1<=p<=100, representing the probability of that word. No word will contain more than 100 letters.
Following the dictionary, there is a line containing a single integer m. Next follow m lines, each consisting of a sequence of at most 100 decimal digits 2-9, followed by a single 1 meaning "next word".
For every number sequence s of the scenario, print one line for every keystroke stored in s, except for the 1 at the end. In this line, print the most probable word prefix defined by the probabilities in the dictionary and the T9 selection rules explained above. Whenever none of the words in the dictionary match the given number sequence, print "MANUALLY" instead of a prefix.
Terminate the output for every number sequence with a blank line, and print an additional blank line at the end of every scenario.
2 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
Scenario #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
这题是一道很好的字典树,一个模拟手机输入法的算法,要用到深搜来解决输出哪个频数最多的单词。第一次写,写了很长时间,现在看回来,发现不过如此,链表不是很熟悉,要多写多练习才行啊!
链接: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;
}
发表评论
-
poj 2230 Watchcow (欧拉回路+dfs)
2012-01-18 23:38 1956Watchcow Time Limit : 6000/30 ... -
poj 2337 Catenyms(并查集+dfs+欧拉回路)
2012-01-18 17:21 2245Catenyms Time Limit : 2000/10 ... -
poj 2513 Colored Sticks (字典树+并查集+欧拉回路)
2012-01-17 20:20 3583Colored Sticks Time Limit : 1 ... -
hdu 1247 Hat’s Words(字典树+分段判断)
2011-10-04 21:28 1821Hat’s Words Time Limit: 2000/1 ... -
ZOJ 1109 Language of FatMouse(赤裸裸的字典树)
2011-10-04 21:18 1952Language of FatMouse Time Lim ... -
hdu 1075 What Are You Talking About(字典树)
2011-10-04 11:03 2054What Are You Talking About Tim ... -
hdu 1254 推箱子(广搜中有深搜!爽!)
2011-08-04 20:20 3633推箱子 Time Limit: 2000/1000 MS ( ... -
hdu 1426 Sudoku Killer(dfs)
2011-07-31 16:47 855Sudoku Killer Time Limit: 2000 ... -
hud 1175 连连看(dfs)
2011-07-31 16:37 891连连看 Time Limit: 20000/10 ... -
hdu 2553 N皇后问题 (经典的dfs)
2011-07-31 11:49 5885N皇后问题 Time Limit: 2000/1000 MS ... -
hdu 1241 Oil Deposits (最经典的dfs)
2011-07-31 11:48 9470Oil Deposits Time Limit: 20 ... -
hdu 1258 Sum It Up
2011-07-30 19:24 1074Sum It Up Time Limit: 2000/100 ... -
hdu 1010 Tempter of the Bone
2011-07-30 18:25 1078Tempter of the Bone Time Limit ... -
hdu 2553 N皇后问题 (经典的dfs)
2011-07-30 18:14 7N皇后问题 Time Limit: 2000/1000 MS ... -
hdu 1241 Oil Deposits (最经典的dfs)
2011-07-30 17:52 7Oil Deposits Time Limit: 20 ... -
hud 1251 统计难题
2011-07-19 22:22 1284统计难题 Time Limit: 4000/2000 M ...
相关推荐
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
acm hdu as easy as a+b
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
hdu 1166线段树代码
hdu 1695 GCD(欧拉函数+容斥原理).docx
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
hdu 1166线段树
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
搜索 dfs 解题代码 hdu1241
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce