这是题目
Description
写下这题目的时间是11.24,美国时间也是11.24,以此题祝远在美帝的PKKJ彭教主生日快乐。
生日嘛,自然少不了生日礼物的啦。这天彭教主收到来自中国的一份神秘的生日礼物(传说中是个漂亮的MM o(∩_∩)o 哈哈)。可是礼物却被一个密码锁锁了
起来(pkkj大叫一声:坑爹啊,哪个家伙这么缺德~-_-b)。在礼物箱上还附着一张纸条:嘿嘿~想知道密码吗?那就把下面的题目解出来,答案就是密码啦!
对于一个字符串,定义它的前缀就是指字符串的任意首部。例如字符串abc的前缀有空串,a,ab,abc。
对于一个字符串集合,如果集合中任一个元素都不是其他元素的前缀的话,我们称之为完美非前缀集合。举个例子:{”happy”, “birthday”, “to”,
“pkkj”}就是一个完美非前缀集合,而{“happy”, “hat”, “h”}就不是完美非前缀集合。
现在问题来了,给你一个字符串集合,你要找出一个该集合的子集,使得该子集是一个完美非前缀集合,且包含最多的元素。问你这个完美非前缀子集最多包含
多少个元素?
由于彭教主一心只想着礼物里面的神秘MM,正所谓一心不能二用,所以他想让你帮他来解决这个难题。
Input
第一行只有一个正整数T,表示题目共有T组数据
对于每组数据,输入一个整数n ( 0< n <= 50 ),
接下来有n行,每行输入一个字符串,字符串由小写字母(’a’~’z’)组成,且长度不超过50.
Output
对于每组数据每行输出一个整数,代表一个完美非前缀子集最多包含多少个元素。
Sample Input
2
4
happy
birthday
to
pkkj
4
happy
hat
h
ha
Sample Output
4
2
Hint
对于第一组数据:该集合本身就是一个完美非前缀集合,所以包含最多元素的完美非前缀子集就是它本身,一共有4个元素
对于第二组数据,{”happy”,”hat”}是其中一个的包含最多元素的完美非前缀子集,其元素个数为2
我的思路是:先把字符串排序,然后第一个与后面的字符串比较,是前缀的话个数减一,第二个也是这样,依次类推。。
下面是我写的程序:
#include<stdio.h>
#include<string.h>
main()
{
int i,j,k,T,n,t,max;
char st[50][51],s0[51];
scanf(" %d",&T);
for(i=0;i<T;i++)
{
scanf(" %d",&n);
fflush(stdin);
for(j=0;j<n;j++)
gets(st[j]);
max=n;
for(j=0;j<n-1;j++)
{
t=j;
for(k=j+1;k<n;k++)
if(strcmp(st[t],st[k])>0) t=k;
if(i!=t)
{
strcpy(s0,st[t]);
strcpy(st[t],st[j]);
strcpy(st[j],s0);
}
}
for(j=0;j<n-1;j++)
for(k=j+1;k<n;k++)
if(strstr(st[k],st[j])==st[k]) {max--;break;}
printf("%d\n",max);
}
return 0;
}
不知道我这个程序有什么问题,总是AC不了,求各方英雄前来解求
å
³äºæ´ä½è¾å
¥è¾åºè¿ä¸ªæ¯æ²¡è¦æ±çï¼ï¼ä¹åæå¾å¤é¢æé½æ¯è¿æ ·åçã
ææé£ä¸ªâiâæ¹åâjâæ交åä¹ä¸æ ·waäºããåºè¯¥æ¯æä»ä¹ç¹æ®æ
åµå¯¼è´waç
é£ä½ ççæ没æä»ä¹æ¢è¡ç¬¦æè
ç©ºæ ¼ä¹ç±»çè¦æ±ã
ç±»ACM太æäºï¼æ ¼å¼æ§å¶å¤ªä¸¥æ ¼ã