USACO 4.3.4 Letter Game
中文题目
这题看清两点,一是每个单词的长度从3-7不等,二是不一定要把原字符串分割完全.注意这两点之后就好办了.我的做法是用一个数组asn[][]记录所有的分割情况,不管是分割了一次还是分割了两次.ans[i][0]表示分割了几次,如果是1的话那么还可以分割一次,如果是2的话,那么剩下的就不可以背分割了,ans[i][1]只有在ans[i][0]==1的情况下才有意义,意义是接下来的这个字符串的长度.这样便于第二次分割时的查找,然后每次从lgame.dict中读入一个字符串,就把ans数组检查一次,而且还把原字符串检查一次,如果产生新的可能符合情况的字符串就加入到ans数组中,这样处理完之后,所有的结果就都在ans数组中了,接下来的事情就是算得分了,用一个数组记录每个字符串的得分,比较得到最大值,再把所有和最大值一样的字符串组复制到一个输出数组中[因为要排序,但是ans数组中的字符串是没有排过序的].最后输出就行了.
代码如下:
/
ID:qcx97811
LANG:C
TASK:lgame
/
#include
#include
#include
#include
char str[12],tmp[12];
int str_len,tmp_len,idx//str_len是input的长度 tmp_len是每次从lgame.dict中读取的长度
//idx是ans的最大下标
char val[28]={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};//每个字符的value
char ans[5006][20],pri[102][16];//ans存可能的结果 pri存结果并排序
void output()
{
char ans_val[5006];
int i,j,k,max
int seg
max=0
memset(ans_val,0,sizeof(ans_val));
//计算value值
for(i=0i<idx;i++)
{
if(1 == ans[i][0])
{//一个部分
for(j=0j<ans[i][1];j++)
{
ans_val[i]+=val[ans[i][j+2]-‘a’];
}
}
else
{//两个部分
for(j=2‘\0’ != ans[i][j];j++)
{
if(‘ ‘ == ans[i][j])
continue
k=ans[i][j]-‘a’
ans_val[i]+=val[k];
}
}
if(max<ans_val[i])
max=ans_val[i];
}
printf(“%d\n“,max);
seg=0//把所有value==max的都复制到pri数组中 并排序
for(i=0i<idx;i++)
{
if(ans_val[i]==max)
{
if(1 == ans[i][0])
{
for(j=0j<ans[i][1];j++)
pri[seg][j]=ans[i][j+2];
pri[seg][j]=‘\0’
}
else
{
for(j=2‘\0’ != ans[i][j];j++)
pri[seg][j-2]=ans[i][j];
pri[seg][j]=‘\0’
}
seg++
}
}
//排序
#if 1
for(i=0i<seg-1;i++)
{
k=i
for(j=seg-1j>;i;j–)
{
if(strcmp(pri[k],pri[j])>0)
{
k=j
}
}
if(k!=i)
{
j=0
do
{
ans_val[j]=pri[i][j];
j++
}while(ans_val[j]!=‘\0’);
j=0
do
{
pri[i][j]=pri[k][j];
j++
}while(pri[i][j]!=‘\0’);
j=0
do
{
pri[k][j]=ans_val[j];
j++
}while(pri[k][j]!=‘\0’);
}
}
#endif
//最后输出
for(i=0i<seg;i++)
{
j=0
while(pri[i][j] != ‘\0’)
{
printf(“%c”,pri[i][j]);
j++
}
printf(“\n“);
}
}
void print()
{//用于调试
int i
printf(“——-print——-\n“);
for(i=0i<idx;i++)
printf(“%d::%d::%s\n“,ans[i][0],ans[i][1],ans[i]+2);
printf(“——-print——-\n“);
}
int main(void)
{
freopen(“lgame.in”,“r”,stdin);
freopen(“lgame.out”,“w”,stdout);
int i,j,k
char f
char used[16];
scanf(“%s”,str);
str_len=strlen(str);
freopen(“lgame.dict”,“r”,stdin);
while(1)
{
scanf(“%s”,tmp);
if(‘.’ == tmp[0])
break
tmp_len=strlen(tmp);
memset(used,0,sizeof(used));
//首先从原字符串找
for(i=0i<tmp_len;i++)
{
for(j=0j<str_len;j++)
{
if(0==used[j]&str[j]==tmp[i])
{//str[j] == tmp[i]
used[j]=1
break
}
}
if(j==str_len)//find a char equals with tmp[i]
break
}
if(i==tmp_len)
{//all the char can be found in str
ans[idx][0]=1
ans[idx][1]=tmp_len
for(i=0i<tmp_len;i++)
{
ans[idx][i+2]=tmp[i];
}
for(i=tmp_len+2,j=0j<str_len;j++)
{
if(0==used[j])
ans[idx][i++]=str[j];
}
ans[idx][i]=‘\0’
idx++
}
//接下来从那些还只被分了一份的里面找
for(j=0j<idx;j++)
{
memset(used,0,sizeof(used));
if(ans[j][0]>1)
continue
for(i=0i<tmp_len;i++)
{
for(k=ans[j][1]+2k<str_len+2;k++)
{
if(0==used[k]&tmp[i]==ans[j][k])
{
used[k]=1
break
}
}
if(k==(str_len+2))
{
break
}
}
if(i==tmp_len)
{
ans[idx][0]=2//标志 表示已被分割了两次
ans[idx][1]=2//这句可不加
for(i=2i<ans[j][1]+2;i++)
{
ans[idx][i]=ans[j][i];
}
ans[idx][ans[j][1]+2]=‘ ‘//在两部分之间加上一个空格 用于排序和输出
for(i=ans[j][1]+3,k=0k<tmp_len;k++)
{
ans[idx][i++]=tmp[k];
}
ans[idx][i]=‘\0’
idx++
}
}
}
output();
#if 0
print();
#endif
return 0
}
ID:qcx97811
LANG:C
TASK:lgame
/
#include
#include
#include
#include
char str[12],tmp[12];
int str_len,tmp_len,idx//str_len是input的长度 tmp_len是每次从lgame.dict中读取的长度
//idx是ans的最大下标
char val[28]={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};//每个字符的value
char ans[5006][20],pri[102][16];//ans存可能的结果 pri存结果并排序
void output()
{
char ans_val[5006];
int i,j,k,max
int seg
max=0
memset(ans_val,0,sizeof(ans_val));
//计算value值
for(i=0i<idx;i++)
{
if(1 == ans[i][0])
{//一个部分
for(j=0j<ans[i][1];j++)
{
ans_val[i]+=val[ans[i][j+2]-‘a’];
}
}
else
{//两个部分
for(j=2‘\0’ != ans[i][j];j++)
{
if(‘ ‘ == ans[i][j])
continue
k=ans[i][j]-‘a’
ans_val[i]+=val[k];
}
}
if(max<ans_val[i])
max=ans_val[i];
}
printf(“%d\n“,max);
seg=0//把所有value==max的都复制到pri数组中 并排序
for(i=0i<idx;i++)
{
if(ans_val[i]==max)
{
if(1 == ans[i][0])
{
for(j=0j<ans[i][1];j++)
pri[seg][j]=ans[i][j+2];
pri[seg][j]=‘\0’
}
else
{
for(j=2‘\0’ != ans[i][j];j++)
pri[seg][j-2]=ans[i][j];
pri[seg][j]=‘\0’
}
seg++
}
}
//排序
#if 1
for(i=0i<seg-1;i++)
{
k=i
for(j=seg-1j>;i;j–)
{
if(strcmp(pri[k],pri[j])>0)
{
k=j
}
}
if(k!=i)
{
j=0
do
{
ans_val[j]=pri[i][j];
j++
}while(ans_val[j]!=‘\0’);
j=0
do
{
pri[i][j]=pri[k][j];
j++
}while(pri[i][j]!=‘\0’);
j=0
do
{
pri[k][j]=ans_val[j];
j++
}while(pri[k][j]!=‘\0’);
}
}
#endif
//最后输出
for(i=0i<seg;i++)
{
j=0
while(pri[i][j] != ‘\0’)
{
printf(“%c”,pri[i][j]);
j++
}
printf(“\n“);
}
}
void print()
{//用于调试
int i
printf(“——-print——-\n“);
for(i=0i<idx;i++)
printf(“%d::%d::%s\n“,ans[i][0],ans[i][1],ans[i]+2);
printf(“——-print——-\n“);
}
int main(void)
{
freopen(“lgame.in”,“r”,stdin);
freopen(“lgame.out”,“w”,stdout);
int i,j,k
char f
char used[16];
scanf(“%s”,str);
str_len=strlen(str);
freopen(“lgame.dict”,“r”,stdin);
while(1)
{
scanf(“%s”,tmp);
if(‘.’ == tmp[0])
break
tmp_len=strlen(tmp);
memset(used,0,sizeof(used));
//首先从原字符串找
for(i=0i<tmp_len;i++)
{
for(j=0j<str_len;j++)
{
if(0==used[j]&str[j]==tmp[i])
{//str[j] == tmp[i]
used[j]=1
break
}
}
if(j==str_len)//find a char equals with tmp[i]
break
}
if(i==tmp_len)
{//all the char can be found in str
ans[idx][0]=1
ans[idx][1]=tmp_len
for(i=0i<tmp_len;i++)
{
ans[idx][i+2]=tmp[i];
}
for(i=tmp_len+2,j=0j<str_len;j++)
{
if(0==used[j])
ans[idx][i++]=str[j];
}
ans[idx][i]=‘\0’
idx++
}
//接下来从那些还只被分了一份的里面找
for(j=0j<idx;j++)
{
memset(used,0,sizeof(used));
if(ans[j][0]>1)
continue
for(i=0i<tmp_len;i++)
{
for(k=ans[j][1]+2k<str_len+2;k++)
{
if(0==used[k]&tmp[i]==ans[j][k])
{
used[k]=1
break
}
}
if(k==(str_len+2))
{
break
}
}
if(i==tmp_len)
{
ans[idx][0]=2//标志 表示已被分割了两次
ans[idx][1]=2//这句可不加
for(i=2i<ans[j][1]+2;i++)
{
ans[idx][i]=ans[j][i];
}
ans[idx][ans[j][1]+2]=‘ ‘//在两部分之间加上一个空格 用于排序和输出
for(i=ans[j][1]+3,k=0k<tmp_len;k++)
{
ans[idx][i++]=tmp[k];
}
ans[idx][i]=‘\0’
idx++
}
}
}
output();
#if 0
print();
#endif
return 0
}
