USACO Letter Game

这道题的难度比较低。USACO给出的题解使用DFS+Tire解决这个问题的。思路是先构造单词串，然后再用Tire检查单词是否在辞典中。
本人采用了另一种方法：
在读入字典的时候，剔除明显不符合条件的单词，然后枚举得出分数最高的单词（或词组）就可以了。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 char word[40000][10];
006 int wlen[40000];
007 int wcnt[40000][30];
008 int wvalue[40000];
009 long total_word;
010
011 int value[30];
012 int max = 0;
013 int pair[40000][2];
014 long paircnt = 0;
015 char ans[40000][15];
016 long anscnt;
017
018 char str[10];
019 int strcnt[30] = {};
020 int maxlen;
021
022 int valid(char *tmp)
023 {
024     int i;
025     static int ccnt[30];
026     memset(ccnt,0,sizeof(ccnt));
027     for(;*tmp;tmp ++)
028     {
029         ccnt[*tmp - 'a'] ++;
030     }
031     for(i = 0;i <= 'z' - 'a';i ++)
032     {
033         if(ccnt[i] > strcnt[i])    return 0;
034     }
035     return 1;
036 }
037
038 void countchar(char *tmp,int *cntarr)
039 {
040     for(;*tmp;tmp ++)
041         cntarr[*tmp - 'a'] ++;
042 }
043
044 int calcvalue(char *tmp)
045 {
046     int v = 0;
047     for(;*tmp;tmp ++)
048         v += value[*tmp - 'a'];
049     return v;
050 }
051
052 void read_dict()
053 {
054     FILE *dict;
055     dict = fopen("lgame.dict","r");
056     long i;
057     char tmp[10];
058     for(i = 0;i < 40000;)
059     {
060         fscanf(dict,"%s",tmp);
061         if(strcmp(tmp,".") == 0)    break;
062         if(strlen(tmp) <= maxlen && valid(tmp))
063         {
064             memcpy(word[i],tmp,sizeof(tmp));
065             wlen[i] = strlen(tmp);
066             countchar(tmp,wcnt[i]);
067             wvalue[i] = calcvalue(tmp);
068             i ++;
069         }
070     }
071     total_word = i;
072     fclose(dict);
073    
074     /*for(i = 0;i < total_word;i ++)
075     {
076         printf("%d %d %s\n",wlen[i],wvalue[i],word[i]);
077     }*/
078 }
079
080 void init_value()
081 {
082     value['a' - 'a'] = 2;
083     value['s' - 'a'] = 1;
084     value['d' - 'a'] = 4;
085     value['f' - 'a'] = 6;
086     value['g' - 'a'] = 5;
087     value['h' - 'a'] = 5;
088     value['j' - 'a'] = 7;
089     value['k' - 'a'] = 6;
090     value['l' - 'a'] = 3;
091     value['q' - 'a'] = 7;
092     value['w' - 'a'] = 6;
093     value['e' - 'a'] = 1;
094     value['r' - 'a'] = 2;
095     value['t' - 'a'] = 2;
096     value['y' - 'a'] = 5;
097     value['u' - 'a'] = 4;
098     value['i' - 'a'] = 1;
099     value['o' - 'a'] = 3;
100     value['p' - 'a'] = 5;
101     value['z' - 'a'] = 7;
102     value['x' - 'a'] = 7;
103     value['c' - 'a'] = 4;
104     value['v' - 'a'] = 6;
105     value['b' - 'a'] = 5;
106     value['n' - 'a'] = 2;
107     value['m' - 'a'] = 5;
108    
109 }
110
111 void read_str()
112 {
113     scanf("%s",str);
114     //puts(str);
115     maxlen = strlen(str);
116     countchar(str,strcnt);
117 }
118
119 void solve_single()
120 {
121     long i;
122     for(i = 0;i < total_word;i ++)
123         if(wvalue[i] > max)    max = wvalue[i];
124 }
125
126 int check(int *cnt1,int *cnt2)
127 {
128     int i;
129     for(i = 0;i <= 'z' - 'a';i ++)
130     {
131         if(cnt1[i] + cnt2[i] > strcnt[i])    return 0;
132     }
133     return 1;
134 }
135
136 void solve_pair()
137 {
138     long i,j;
139     for(i = 0;i < total_word;i ++)
140         for(j = i;j < total_word;j ++)
141         {
142             if(wvalue[i] + wvalue[j] >= max && check(wcnt[i],wcnt[j]))
143             {
144                 if(wvalue[i] + wvalue[j] > max)
145                 {
146                     max = wvalue[i] + wvalue[j];
147                     paircnt = 1;
148                     pair[0][0] = i;
149                     pair[0][1] = j;
150                 }
151                 else if(wvalue[i] + wvalue[j] == max)
152                 {
153                     pair[paircnt][0] = i;
154                     pair[paircnt][1] = j;
155                     paircnt ++;
156                 }
157             }
158         }
159 }
160
161 int cmp(const void *a,const void *b)
162 {
163     return (int)strcmp((char *)a,(char *)b);
164 }
165
166 void sort()
167 {
168     long i;
169     for(i = 0;i < paircnt;i ++)
170     {
171         strcpy(ans[anscnt],word[pair[i][0]]);
172         strcat(ans[anscnt]," ");
173         strcat(ans[anscnt],word[pair[i][1]]);
174         anscnt ++;
175     }
176     for(i = 0;i < total_word;i ++)
177     {
178         if(wvalue[i] == max)    strcpy(ans[anscnt ++],word[i]);
179     }
180     qsort(ans,anscnt,15,cmp);
181     printf("%d\n",max);
182     for(i = 0;i < anscnt;i ++)
183     {
184         puts(ans[i]);
185     }
186 }
187
188 int main()
189 {
190     freopen("lgame.in","r",stdin);
191     freopen("lgame.out","w",stdout);
192     init_value();
193     read_str();
194     read_dict();
195     solve_single();
196     solve_pair();
197     sort();
198     return 0;
199 }

USACO Street Race

第一问很简单，只需要尝试把各点从图上去除，然后从出发点开始遍历，如果不能到达终点，那么这个点就是“不可避免”的。

第二问困扰了我很长一段时间。题目中是这么说的：

A point S is a splitting point for the well-formed course C if S differs from the start and the finish of C, and the course can be split into two well-formed courses that (1) have no common arrows and (2) have S as their only common point, with S appearing as the finish of one and the start of the other.

最后迫不得已看了NOCOW上的题解，其实上面这些话的意思就是第一天可以到达的点和第二天可以到达的点不能重复。因此，只需要两次遍历就足够了。并且满足第二问限制的点一定满足第一问限制。

不过，为什么是这样的我还没有折腾明白，各位读者如有思路麻烦留言下，谢了。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define MXN 55
005 #define S 0
006 #define F (N-1)
007
008 int adj[MXN][MXN] = {};
009 int N;
010
011 void init()
012 {
013     int tmp;
014     while(1)
015     {
016         while(1)
017         {
018             scanf("%d",&tmp);
019             if(tmp == -2)
020                 break;
021             else if(tmp == -1)
022                 return;
023             else if(N != tmp)  //ignore self loop
024             {
025                 adj[N][tmp] = 1;
026             }
027         }
028         N ++;
029     }
030 }
031
032 int queue[MXN * 10];
033 int head,tail;
034
035 void enqueue(int node)
036 {
037     queue[tail ++] = node;
038 }
039
040 int dequeue()
041 {
042     return queue[head ++];
043 }
044
045 int check_connectivity(int exclude)    //BFS from start
046 {
047     int now,i;
048     int visit[MXN];
049     head = tail = 0;
050     memset(visit,0,sizeof(visit));
051     enqueue(S);
052     visit[S] = 1;
053     while(head < tail)
054     {
055         now = dequeue();
056         for(i = 0;i < N;i ++)
057             if(adj[now][i] && i != exclude && !visit[i])
058             {
059                 enqueue(i);
060                 visit[i] = 1;
061             }
062     }
063     if(visit[F])    return 1;
064     return 0;
065 }
066
067 int have_common_node(int mid)
068 {
069     static _Bool visit[MXN];
070     static int first[MXN],second[MXN];
071     int i,now;
072    
073     head = tail = 0;
074     memset(visit,0,sizeof(visit));
075     memset(first,0,sizeof(first));
076     memset(second,0,sizeof(second));
077     enqueue(S);
078     first[S] = visit[S] = 1;
079     while(head < tail)
080     {
081         now = dequeue();
082         for(i = 0;i < N;i ++)
083         {
084             if(adj[now][i] && !visit[i] && i != mid)
085             {
086                 enqueue(i);
087                 visit[i] = 1;
088                 first[i] = 1;
089             }
090         }
091     }
092    
093     memset(visit,0,sizeof(visit));
094     head = tail = 0;
095     enqueue(mid);
096     second[mid] = visit[mid] = 1;
097     while(head < tail)
098     {
099         now = dequeue();
100         for(i = 0;i < N;i ++)
101         {
102             if(adj[now][i] && !visit[i])
103             {
104                 enqueue(i);
105                 visit[i] = 1;
106                 second[i] = 1;
107             }
108         }
109     }
110     fprintf(stderr,"\n%d:\n",mid);
111     for(i = 0;i < N;i ++)
112     {
113         fprintf(stderr,"%d: %d %d\n",i,first[i],second[i]);
114     }
115    
116     for(i = 0;i < N;i ++)
117     {
118         if(i == mid)    continue;
119         if(first[i] && second[i])    return 1;
120     }
121     return 0;
122 }
123
124 int main()
125 {
126     freopen("race3.in","r",stdin);
127     freopen("race3.out","w",stdout);
128     int i;
129     int ucnt = 0,scnt = 0;
130     int unavoid[MXN] = {};
131     int split[MXN] = {};
132     init();
133     //try unavoidable nodes
134     for(i = 0;i < N;i ++)
135     {
136         if(i == S || i == F)    continue;
137         if(check_connectivity(i) == 0)
138         {
139             unavoid[ucnt ++] = i;
140             if(have_common_node(i) == 0)
141                 split[scnt ++] = i;
142         }
143     }
144     printf("%d",ucnt);
145     for(i = 0;i < ucnt;i ++)
146         printf(" %d",unavoid[i]);
147     printf("\n");
148     printf("%d",scnt);
149     for(i = 0;i < scnt;i ++)
150         printf(" %d",split[i]);
151     printf("\n");
152    
153     return 0;
154 }