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;
}