USACO Section 4.3 Letter Game - 简单枚举

本来是1A的...就因为不知怎么USACO不认识gets..给报了次Compile error...这题算是简单的...

首先我为了方便判断一个字符串是不是由所给的字符组成(不一定全部用上)..那么用一个26位的int数组h [ ] 先记录所给的字符个数...如aabb那么h [ ] = { 2,2,0,0....0 }..假设这里来一个字符串...那么就把 h [ ] 的信息先转移给另一个一样的串 ( 因为h要重复利用的 ) p [ ]...从字符串第一位开始扫到最有一位..若其某位在p [ ] 记录出现次数非0.则通过这位..p [ ]的这一位计数-1...在p [ ] 记录出现次数为0...则说明在所给的字符不能组成这个字符串..此串不符合所需...

因为不论是字典里的每个字符的长度或者值都会进行很多次运算...为了避免过多重复计算..我在输入的时候就将所有字符串的长度记在len[ ] 里...将所有字符串所产生的值记录在M [ ] 里了..

从字典的第一个数开始枚举..并判断其是由所给字符组成(不一定要全部用上..)..如果通过..就看其单独做为一个或者和另一个组合...因为题目所给的字符串只会在3~7长度..所以要么就是一个..要么就是两个组成一个...每次都判断下当前所得到的权值是否比前面所得到的大..大的话就更新..记录..计数器清1...若相等则计数器+1..并记录串...

题目所给的权值计算也是可以用上的...比如说扫到一个串如果其权值大于了所给的字符集合的最大权值..那么肯定就不需要再进一步判断其合法性了...

Program:

/* ID: zzyzzy12 LANG: C++ TASK: lgame */ #include<iostream> #include<istream> #include<stdio.h> #include<string.h> #include<math.h> #include<stack> #include<map> #include<algorithm> #include<queue> #define oo 1000000000 #define ll long long #define pi (atan(2)+atan(0.5))*2 using namespace std; struct node { int s[26]; }h,p,q; int w[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}; int l,num,m,len[40000],M[40000],temp,ansnum,MaxM; char s[10],dict[40000][9],ans[501][10]; void Find2(int z) { int i,j; for (i=z+1;i<=num;i++) if (M[i]<=m) { q=p; for (j=0;j<len[i];j++) if (!q.s[dict[i][j]-'a']) goto B; else q.s[dict[i][j]-'a']--; if (M[i]+M[temp]>MaxM) { MaxM=M[i]+M[temp]; ansnum=1; strcpy(ans[1],dict[temp]); ans[1][len[temp]]=' '; strcpy(ans[1]+len[temp]+1,dict[i]); }else if (M[i]+M[temp]==MaxM) { ansnum++; strcpy(ans[ansnum],dict[temp]); ans[ansnum][len[temp]]=' '; strcpy(ans[ansnum]+len[temp]+1,dict[i]); } B: ; } } void getanswer() { int i,j; m=0; memset(h.s,0,sizeof(h.s)); for (i=0;i<l;i++) { m+=w[s[i]-'a']; h.s[s[i]-'a']++; } ansnum=0; MaxM=0; for (i=1;i<=num;i++) if (len[i]<=l && M[i]<=m) { p=h; for (j=0;j<len[i];j++) if (!p.s[dict[i][j]-'a']) goto A; else p.s[dict[i][j]-'a']--; if (M[i]>MaxM) { MaxM=M[i]; ansnum=1; strcpy(ans[1],dict[i]); }else if (M[i]==MaxM) strcpy(ans[++ansnum],dict[i]); if (l-len[i]>=3) { temp=i; m-=M[i]; Find2(i); m+=M[i]; } A: ; } return; } int main() { int i; freopen("lgame.dict","r",stdin); num=0; do { scanf("%s",dict[++num]); }while (dict[num][0]!='.'); num--; for (i=1;i<=num;i++) { len[i]=strlen(dict[i]); M[i]=0; for (m=0;m<len[i];m++) M[i]+=w[dict[i][m]-'a']; } fclose(stdin); freopen("lgame.in","r",stdin); freopen("lgame.out","w",stdout); scanf("%s",s); l=strlen(s); getanswer(); printf("%d\n",MaxM); for (i=1;i<=ansnum;i++) printf("%s\n",ans[i]); return 0; }