首页 > 代码库 > USACO 4.3 Letter Game (字典树)

USACO 4.3 Letter Game (字典树)

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 (字典树)