Beyond the Void
BYVoid
USACO 4.3.4 Letter Game 字母遊戲 lgame
本文正體字版由OpenCC轉換

這個題要仔細讀,理解題意。起初我理解得不對,以爲是輸出的每個結果都必須是輸入的一個排列,不能多也不能少。這種理解不正確。汗,我一直以爲樣例居然是錯的,其實使用的字典不一樣。

這道題正確的理解應該是,在結果的單詞或詞組構所成的字母中,每個字母出現的頻數不大於輸入的字符串中每個字母的頻數。也就是例如輸入是 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;
}

上次修改時間 2017-05-22

相關日誌