讨论 / PID211 [JLOI2008]CODES 为什么只有50分
drcool 2013-12-18 06:45:38
点我顶贴 收藏 删除
#include <stdio.h>

#include <string.h>

#include <stdlib.h>

struct tx{

char s[24];

int len;

};

struct tx T[20];

int n;

char test[4096];

char cans[4096];

int clen=4095;

char visit[2][20];

int compare( const void *arg1, const void *arg2 )

{

struct tx *A=arg1, *B=arg2;

int i,len=A->len;

if(len<B->len)

len=B->len;

for(i=0;i<len;i++)

if(A->s[i]-B->s[i]) return A->s[i]-B->s[i];

return 0;

}

void dfs(int id, int from,int end)

{

int i,j,x=end-from+1;

for(i=0;i<n;i++)

{

if(!visit[id][i])

{

if(T[i].len>x)

{

if(!memcmp(T[i].s,test+from,x)) //有部分匹配

{

if(end+1+T[i].len-x<=clen)

{

visit[id][i]=1;

memcpy(test+from,T[i].s,T[i].len);

dfs(id^1,end+1,end+T[i].len-x);

visit[id][i]=0;

}

}

}

else if(!memcmp(T[i].s,test+from,T[i].len))

{

if(x==T[i].len) //找到了匹配

{

visit[id][i]=1;

if(memcmp(visit[0],visit[1],n))

{

for(j=0;j<clen;j++)

if(test[j]<cans[j])

{

clen=end+1;

memcpy(cans,test,clen);

break;

}

visit[id][i]=0;

//return;

}

else

visit[id][i]=0; //否则就是重复的排列

}

else //只有部分匹配

{

visit[id][i]=1;

dfs(id,from+T[i].len,end);

visit[id][i]=0;

}

}

}

}

}

int main()

{

int i;

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%s",T[i].s);

T[i].len=strlen(T[i].s);

}

qsort(T,n,sizeof(struct tx),compare);

memset(cans,'1',4095);

for(i=0;i<n;i++)

{

if(T[i].len<=clen)

{

memset(visit,0,sizeof(visit));

memcpy(test,T[i].s,T[i].len);

visit[0][i]=1;

dfs(1,0,T[i].len-1);

}

}

printf("%d\n",clen);

cans[clen]=0;

printf("%s",cans);

}

查看更多回复
提交回复