USACO 4.3.4 Letter Game 字母游戏 lgame
这个题要仔细读，理解题意。起初我理解得不对，以为是输出的每个结果都必须是输入的一个排列，不能多也不能少。这种理解不正确。汗，我一直以为样例居然是错的，其实使用的字典不一样。
这道题正确的理解应该是，在结果的单词或词组构所成的字母中，每个字母出现的频数不大于输入的字符串中每个字母的频数。也就是例如输入是 aaa，字典中有单词 a,aa,aaa,aaaa，其中a,aa,aaa都是符合条件的解，但只有aaa才是要输出的最优解。
理解题意以后编程不难，直接枚举每种可行解，单词可以在O(n)内解决，词组要O(N^2)。但是对于40000个单词但是太多了。可以发现，大多数单词都是用不到的，而所以我们可以在读入字典的时候直接去除非可行解的单词，即该单词有输入字串中未出现的字母，或者在该单词中的字母中，有频数大于输入字串所含该字母频数的（例：输入字串为aabb，该单词为aaa，其中a的频数大于输入字串，必定无法有输入字串构成）。
这样优化可以去掉绝大部分的冗余，使得程序能够在很快的时间内算出结果。
所后别忘了对结果排序，可以把单词当作一个第二个单词为空串的词组，按字典顺序排序即可。
USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: lgame LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.000 secs, 3476 KB] Test 2: TEST OK [0.000 secs, 3476 KB] Test 3: TEST OK [0.000 secs, 3476 KB] Test 4: TEST OK [0.011 secs, 3472 KB] Test 5: TEST OK [0.011 secs, 3476 KB] Test 6: TEST OK [0.000 secs, 3476 KB] Test 7: TEST OK [0.011 secs, 3472 KB] Test 8: TEST OK [0.011 secs, 3476 KB] Test 9: TEST OK [0.011 secs, 3476 KB] Test 10: TEST OK [0.011 secs, 3472 KB] Test 11: TEST OK [0.011 secs, 3472 KB] Test 12: TEST OK [0.011 secs, 3472 KB] All tests OK. Your program ('lgame') produced all correct answers! This is your submission #2 for this problem. Congratulations!
/*
ID: cmykrgb1
PROG: lgame
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("lgame.in");
ifstream fd("lgame.dict");
ofstream fo("lgame.out");
typedef struct
{
char c[7];
int len;
int score;
}str;
typedef struct
{
char c1[7],c2[7];
int len1,len2;
}Tans;
int uw['z'+1],used['z'+1];
int v['z'+1];
str S[40001];
Tans ans[50];
int N=1,L,acnt;
int Ms=0;
void init()
{
int i;
char c;
bool k;
while (!fi.eof())
{
c=fi.get();
uw[c]++;
}
while (c!='.')
{
memset(used,0,sizeof(used));
L++;
c=fd.get();
if (c=='.')
break;
k=true;
while (c==10 || c==13) c=fd.get();
S[N].len=0;
while (c!=10 && c!=13)
{
S[N].c[ S[N].len++ ]=c;
used[c]++;
if (!uw[c])
k=false;
c=fd.get();
}
S[N].c[ S[N].len ]=0;
for (i='a';i<='z';i++)
if (used[i]>uw[i])
{
k=false;
break;
}
if (k)
N++;
}
N--;
v['q']=v['j']=v['z']=v['x']=7;
v['w']=v['f']=v['k']=v['v']=6;
v['y']=v['p']=v['g']=v['h']=v['b']=v['m']=5;
v['u']=v['d']=v['c']=4;
v['o']=v['l']=3;
v['r']=v['t']=v['a']=v['n']=2;
v['e']=v['i']=v['s']=1;
}
void findans()
{
int i,k,p;
for (i=1;i<=N;i++)
{
for (k=0;k<=S[i].len-1;k++)
S[i].score+=v[ S[i].c[k] ];
if (S[i].score>Ms)
{
Ms=S[i].score;
acnt=1;
for (p=0;p<=S[i].len-1;p++)
ans[acnt].c1[p]=S[i].c[p];
ans[acnt].len1=S[i].len;
ans[acnt].c1[ ans[acnt].len1 ]=0;
}
else if (S[i].score==Ms)
{
acnt++;
for (p=0;p<=S[i].len-1;p++)
ans[acnt].c1[p]=S[i].c[p];
ans[acnt].len1=S[i].len;
ans[acnt].c1[ ans[acnt].len1 ]=0;
}
}
}
void findpair()
{
memset(used,0,sizeof(used));
int i,j,p;
bool K;
int T;
for (i=1;i<=N-1;i++)
{
for (j=i+1;j<=N;j++)
{
T=S[i].score+S[j].score;
for (p=0;p<=S[i].len-1;p++)
used[S[i].c[p]]++;
for (p=0;p<=S[j].len-1;p++)
used[S[j].c[p]]++;
K=true;
for (p='a';p<='z';p++)
if (used[p]>uw[p])
{
K=false;
break;
}
memset(used,0,sizeof(used));
if (!K) continue;
if (T>Ms)
{
Ms=T;
acnt=1;
for (p=0;p<=S[i].len-1;p++)
ans[acnt].c1[p]=S[i].c[p];
ans[acnt].len1=S[i].len;
ans[acnt].c1[ ans[acnt].len1 ]=0;
for (p=0;p<=S[j].len-1;p++)
ans[acnt].c2[p]=S[j].c[p];
ans[acnt].len2=S[j].len;
ans[acnt].c2[ ans[acnt].len2 ]=0;
}
else if (T==Ms)
{
acnt++;
for (p=0;p<=S[i].len-1;p++)
ans[acnt].c1[p]=S[i].c[p];
ans[acnt].len1=S[i].len;
ans[acnt].c1[ ans[acnt].len1 ]=0;
for (p=0;p<=S[j].len-1;p++)
ans[acnt].c2[p]=S[j].c[p];
ans[acnt].len2=S[j].len;
ans[acnt].c2[ ans[acnt].len2 ]=0;
}
}
}
}
void print()
{
fo << Ms << endl;
int i,j;
for (i=1;i<=acnt;i++)
{
for (j=0;j<=ans[i].len1-1;j++)
fo << ans[i].c1[j];
if (ans[i].len2)
{
fo << ' ';
for (j=0;j<=ans[i].len2-1;j++)
fo << ans[i].c2[j];
}
fo <<endl;
}
}
inline int cmp(const void *a,const void *b)
{
int k;
Tans *A=(Tans *)a,*B=(Tans *)b;
k=strcmp(A->c1,B->c1);
if (k!=0) return k;
k=strcmp(A->c2,B->c2);
return k;
}
void sortans()
{
qsort(ans+1,acnt,sizeof(Tans),cmp);
print();
}
int main()
{
init();
findans();
findpair();
sortans();
fi.close();
fd.close();
fo.close();
return 0;
}