hdu1298之经典字符串 - c++编程基础

n 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.

Sample Input
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

Sample Output
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
题意:首先给定n组字符串s和数字a,表示该字符串s输入过a次,

接下来q次输入,每次输入表示按键顺序（使用手机输入发那种）,问每次按键可能出现的字符串,按使用频率高的输出,若没有则输出MANUALLY

分析:用字典树存使用的字符串和其前缀,并且记录使用的频率,然后对每次的按键进行枚举可能的字符查询即可

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define INF 99999999   
using namespace std;  
  
const int MAX=100+10;  
int m[10]={0,0,3,3,3,3,3,4,3,4};//表示按键i有几个字符   
char ch[10][5]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};   
char s[MAX];  
string temp;  
int sum;  
  
struct TrieNode{  
    int num;//出现频率   
    TrieNode *next[26];  
    TrieNode(){  
        num=0;  
        memset(next,0,sizeof next);  
    }   
}root;  
  
void InsertNode(char *a,int num){  
    int k=0;  
    TrieNode *p=&root;  
    while(a[k]){  
        if(!p->next[a[k]-'a'])p->next[a[k]-'a']=new TrieNode;  
        p=p->next[a[k++]-'a'];  
        p->num+=num;  
    }  
}  
  
void SearchTrie(int k,int len,TrieNode *p,string a){  
    if(k == len){  
        if(p->num > sum){  
            sum=p->num;  
            temp=a;  
        }  
    }  
    int t=s[k]-'0';  
    for(int i=0;inext[ch[t][i]-'a'])SearchTrie(k+1,len,p->next[ch[t][i]-'a'],a+ch[t][i]);  
    }  
}  
  
void Free(TrieNode *p){  
    for(int i=0;i<26;++i)if(p->next[i])Free(p->next[i]);  
    delete p;  
}  
  
int main(){  
    int t,n,num=0,w;  
    cin>>t;  
    while(t--){  
        cout<<"Scenario #"<<++num<<":\n";  
        cin>>n;  
        for(int i=0;i>s>>w;  
            InsertNode(s,w);  
        }  
        cin>>n;  
        for(int i=0;i>s;  
            int len=strlen(s);  
            for(int j=1;j
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 99999999
using namespace std;

const int MAX=100+10;
int m[10]={0,0,3,3,3,3,3,4,3,4};//表示按键i有几个字符
char ch[10][5]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 
char s[MAX];
string temp;
int sum;

struct TrieNode{
	int num;//出现频率
	TrieNode *next[26];
	TrieNode(){
		num=0;
		memset(next,0,sizeof next);
	} 
}root;

void InsertNode(char *a,int num){
	int k=0;
	TrieNode *p=&root;
	while(a[k]){
		if(!p->next[a[k]-'a'])p->next[a[k]-'a']=new TrieNode;
		p=p->next[a[k++]-'a'];
		p->num+=num;
	}
}

void SearchTrie(int k,int len,TrieNode *p,string a){
	if(k == len){
		if(p->num > sum){
			sum=p->num;
			temp=a;
		}
	}
	int t=s[k]-'0';
	for(int i=0;inext[ch[t][i]-'a'])SearchTrie(k+1,len,p->next[ch[t][i]-'a'],a+ch[t][i]);
	}
}

void Free(TrieNode *p){
	for(int i=0;i<26;++i)if(p->next[i])Free(p->next[i]);
	delete p;
}

int main(){
	int t,n,num=0,w;
	cin>>t;
	while(t--){
		cout<<"Scenario #"<<++num<<":\n";
		cin>>n;
		for(int i=0;i>s>>w;
			InsertNode(s,w);
		}
		cin>>n;
		for(int i=0;i>s;
			int len=strlen(s);
			for(int j=1;j

hdu1298之经典字符串 (二)