首页 > 代码库 > USACO 4.3 Letter Game （字典树）
USACO 4.3 Letter Game （字典树）
IOI 1995
Figure 1: Each of the 26 lowercase letters and its value
Letter games are popular at home and on television. In one version of the game, every letter has a value, and you collect letters to form one or more words giving the highest possible score. Unless you have `a way with words‘, you will try all the words you know, sometimes looking up the spelling, and then compute the scores. Obviously, this can be done more accurately by computer.
Given the values in Figure 1, a list of words, and the letters collected: find the highest scoring words or pairs of words that can be formed.
PROGRAM NAME: lgame
INPUT FORMAT
One line with a string of lowercase letters (from `a‘ to `z‘). The string consists of at least 3 and at most 7 letters in arbitrary order.
SAMPLE INPUT (file lgame.in)
prmgroa
DICTIONARY FORMAT
At most 40,000 lines, each containing a string of at least 3 and at most 7 lowercase letters. At the end of this file is a line with a single period (`.‘). The file is sorted alphabetically and contains no duplicates.
SAMPLE DICTIONARY (file lgame.dict)
profile program prom rag ram rom .
OUTPUT FORMAT
On the first line, your program should write the highest possible score, and on each of the following lines, all the words and/or word pairs from file lgame.dict with this score. Sort the output alphabetically by first word, and if tied, by second word. A letter must not occur more often in an output line than in the input line. Use the letter values given in Figure 1.
When a combination of two words can be formed with the given letters, the words should be printed on the same line separated by a space. The two words should be in alphabetical order; for example, do not write `rag prom‘, only write `prom rag‘. A pair in an output line may consist of two identical words.
SAMPLE OUTPUT (file lgame.out)
This output uses the tiny dictionary above, not the lgame.dict dictionary.
24 program prom rag
——————————————————————————题解
一道查字典的题
用了一堆以前没用过的东西或不熟练的东西……
总结一下
string substr(int pos = 0,int n = npos) const;//返回pos开始的n个字符组成的字符串,如果n很大就返回pos之后所有的字符
string &append(int n,char c); //在当前字符串结尾添加n个字符c
string &erase(int pos = 0, int n = npos); //删除pos开始的n个字符，返回修改后的字符串
vector的unique操作
1 vector<pss >::iterator iter=unique(astr.begin(),astr.end()); 2 astr.erase(iter,astr.end());
以及【捂脸】文件读入读出（来自usaco）
1 FILE *fin = fopen ("test.in", "r"); 2 FILE *fout = fopen ("test.out", "w"); 3 int a, b; 4 fscanf (fin, "%d %d", &a, &b); 5 fprintf (fout, "%d\n", a+b);
1 /* 2 ID: ivorysi 3 LANG: C++ 4 TASK: lgame 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <cstring> 9 #include <algorithm> 10 #include <queue> 11 #include <set> 12 #include <vector> 13 #include <string.h> 14 #define siji(i,x,y) for(int i=(x);i<=(y);++i) 15 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j) 16 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i) 17 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j) 18 #define inf 0x7fffffff 19 #define ivorysi 20 #define mo 97797977 21 #define hash 974711 22 #define base 47 23 #define pss pair<string,string> 24 #define MAXN 30005 25 #define fi first 26 #define se second 27 #define pii pair<int,int> 28 using namespace std; 29 struct node { 30 node *le[28]; 31 int end; 32 node() { 33 memset(le,0,sizeof(le)); 34 end=0; 35 } 36 }*root; 37 int val[26]= {2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7}; 38 char word[10],len; 39 int used[10],ans; 40 vector< pss > astr; 41 void ins(char *s){ 42 int l=strlen(s+1); 43 node *p=root; 44 siji(i,1,l) { 45 if(p->le[s[i]-‘a‘]==0) { 46 p->le[s[i]-‘a‘]=new node; 47 } 48 p=p->le[s[i]-‘a‘]; 49 } 50 p->end=1; 51 } 52 void init() { 53 char str[10]; 54 scanf("%s",word+1); 55 len=strlen(word+1); 56 root=new node; 57 FILE *fin = fopen ("lgame.dict", "r"); 58 while(fscanf(fin,"%s",str+1) && str[1]!=‘.‘) { 59 ins(str); 60 } 61 } 62 int srch(string str) { 63 if(str.length()==0) return 0; 64 node *p=root; 65 int gz=0; 66 //____ 67 //if(str=="ag") gz=1; 68 //_____ 69 int flag=1; 70 int res=0; 71 //if(gz) printf("%d\n",str.length()); 72 xiaosiji(i,0,str.length()) { 73 //if(gz)printf("%d %d %d\n",i,flag,res); 74 /*if(gz) { 75 printf("-----------\n"); 76 siji(i,0,25) { 77 printf("%d %c\n",p->le[i],i+‘a‘); 78 } 79 }*/ 80 if(p->le[str[i]-‘a‘]==0) { 81 flag=-1000; 82 break; 83 } 84 else { 85 p=p->le[str[i]-‘a‘]; 86 res+=val[str[i]-‘a‘]; 87 88 } 89 } 90 if(p->end == 0) flag=-1000; 91 return flag*res; 92 93 } 94 void calc(string str,int l) { 95 xiaosiji(i,0,l) { 96 int temp=srch(str.substr(0,i+1))+srch(str.substr(0+i+1,233)); 97 if(temp>ans) { 98 astr.clear(); 99 astr.push_back(make_pair(str.substr(0,i+1),str.substr(0+i+1,233))); 100 int k=astr.size(); 101 if(astr[k-1].fi>astr[k-1].se && astr[k-1].se!=""){ 102 swap(astr[k-1].fi,astr[k-1].se); 103 } 104 ans=temp; 105 } 106 else if(temp==ans) { 107 astr.push_back(make_pair(str.substr(0,i+1),str.substr(0+i+1,233))); 108 int k=astr.size(); 109 if(astr[k-1].fi>astr[k-1].se && astr[k-1].se!=""){ 110 swap(astr[k-1].fi,astr[k-1].se); 111 } 112 } 113 } 114 } 115 void dfs(string str,int l) { 116 if(l>len) return; 117 siji(i,1,len) { 118 if(!used[i]) { 119 str.append(1,word[i]); 120 used[i]=1; 121 calc(str,l+1); 122 dfs(str,l+1); 123 used[i]=0; 124 str.erase(l,1); 125 } 126 } 127 } 128 void solve() { 129 init(); 130 dfs("",0); 131 sort(astr.begin(),astr.end()); 132 vector<pss >::iterator iter=unique(astr.begin(),astr.end()); 133 astr.erase(iter,astr.end()); 134 printf("%d\n",ans); 135 xiaosiji(i,0,astr.size()) { 136 cout<<astr[i].fi; 137 if(astr[i].se!="") { 138 cout<<" "<<astr[i].se; 139 } 140 puts(""); 141 } 142 } 143 int main(int argc, char const *argv[]) 144 { 145 #ifdef ivorysi 146 freopen("lgame.in","r",stdin); 147 freopen("lgame.out","w",stdout); 148 #else 149 freopen("f1.in","r",stdin); 150 #endif 151 solve(); 152 return 0; 153 }
USACO 4.3 Letter Game （字典树）